Αυτόματα σε άπειρες λέξεις και άπειρα δένδρα:
Creators: name: Τζιτζιλή, Μαρία Γεωργίου
Publisher: name: Aristotle University of Thessaloniki
Year: 2009
Subjects: ω-αυτόματα
Büchi αυτόματα
Muller αυτόματα
Rabin αυτόματα
parity αυτόματα
άπειρα παίγνια
στρατηγικές
άπειρες λέξεις
άπειρα δένδρα
δενδροαυτόματα
ω-automata
Büchi automata
Muller automata
Rabin automata
parity automata
infinite games
strategies
infinite words
infinite trees
tree automata

description: Εισάγουμε τα αυτόματα σε άπειρες λέξεις (ω-Αυτόματα) και ορίζουμε τις ακόλουθες συνθήκες αποδοχής: την Büchi Αποδοχή, τη Muller Αποδοχή, τη Rabin Αποδοχή, την parity συνθήκη και τα αντίστοιχα μη-προσδιοριστά αυτόματα. Έπειτα δείχνουμε πώς μετασχηματίζουμε αυτά τα αυτόματα από τον έναν τύπο στον άλλον και αποδεικνύουμε πως όλα τα μη-προσδιοριστά αυτόματα είναι ισοδύναμα σε εκφραστική δύναμη. Στη συνέχεια, μελετάμε τα προσδιοριστά μοντέλα τέτοιων αυτομάτων. Τα προσδιοριστά Büchi αυτόματα είναι πολύ αδύναμα στο να αναγνωρίζουν ακόμα και πολύ απλές ω-γλώσσες. Μετασχηματίζουμε τα προσδιοριστά Muller αυτόματα σε προσδιοριστά Rabin και parity αυτόματα και δείχνουμε ότι τα προσδιοριστά Muller, Rabin και parity αυτόματα αναγνωρίζουν την ίδια κλάση των ω-γλωσσών , η οποία είναι κλειστή ως προς το συμπλήρωμα. Παρουσιάζουμε επίσης την 1 και την 1’-Αποδοχή, που είναι ασθενείς συνθήκες αποδοχής. Έπειτα, ορίζουμε τους διάφορους τύπους άπειρων παιγνίων και εξηγούμε τι είναι η στρατηγική και η συνθήκη νίκης. Ορίζουμε συνθήκες νίκης για τα παίγνια αναλογικά με τις παραπάνω συνθήκες αποδοχής και δείχνουμε πώς μετασχηματίζονται από το ένα στο άλλο. Εισάγονται επίσης οι έννοιες των «forgetful», «memoryless» στρατηγικών και της καθοριστικότητας και μας βοηθούν να λύσουμε παίγνια με απλές συνθήκες νίκης. Τέλος, μελετάμε τα μη-προσδιοριστά δενδροαυτόματα και ειδικά τα Muller, τα parity και τα Rabin δενδροαυτόματα και αποδεικνύουμε πως όλα αναγνωρίζουν τις ίδιες δενδρογλώσσες. Η μόνη εξαίρεση είναι τα Büchi δενδροαυτόματα, τα οποία είναι πολύ ασθενέστερα στην αναγνώριση. Μελετάμε το πρόβλημα του συμπληρώματος και του κενού για αυτόματα σε άπειρα δένδρα και δείχνουμε: (1) κλειστότητα ως προς το συμπλήρωμα για τις δενδρογλώσσες που γίνονται δεκτές από πεπερασμένα δενδροαυτόματα και (2) αποφασισιμότητα για το πρόβλημα του κενού για τα parity δενδροαυτόματα χρησιμοποιώντας αποτελέσματα για τα άπειρα παίγνια σε πεπερασμένα γραφήματα.
description: We introduce automata on infinite words ( ω-Automata) and define the following acceptance conditions: Büchi Acceptance, Muller Acceptance, Rabin Acceptance, the parity condition and the respective nondeterministic automata. Then we show how to transform these automata from one form to another and we prove that all nondeterministic automata are equivalent in expressive power. Next, we study deterministic models of such automata. Deterministic Büchi automata are too weak for recognizing even very simple ω-languages. We transform deterministic Muller into deterministic Rabin and parity automata and show that deterministic Muller, Rabin and parity automata recognize the same class of ω-languages which is closed under complementation. We introduce also 1 and 1′- acceptance, which are weak acceptance conditions. Then, we define different types of infinite games and explain what a strategy and a winning condition is. We define winning conditions analogously to the above acceptance conditions and show how to transform from one to another. The notions of forgetful, memoryless strategies and determinacy are also introduced and help us solve games with simple winning conditions. In the end we study nondeterninistic tree automata and especially Muller, parity and Rabin tree automata and we prove that they all recognize the same tree languages. The only exception are Büchi tree automata, which are much weaker in recognizing. We study the complementation and the emptiness problem for automata on infinite trees and show: (1) closure under complementation for tree languages acceptable by finite-state tree automata and (2) decicability of the emptiness problem for parity tree automata by utilizing results about infinite games on finite graphs.