Topological Complexity of Sets Defined by Automata and Formulas

University of Warsaw Repository

pl | en
 
 

Show simple item record

dc.contributor.advisor Niwiński, Damian
dc.contributor.author Hummel, Szczepan
dc.date.accessioned 2017-10-31T00:05:44Z
dc.date.available 2017-10-31T00:05:44Z
dc.date.issued 2017-05-23
dc.identifier.uri https://depotuw.ceon.pl/handle/item/2337
dc.description.abstract In this thesis we consider languages of infinite words or trees defined by automata of various types or formulas of various logics. We ask about the highest possible position in the Borel or the projective hierarchy inhabited by sets defined in a given formalism. The answer to this question is called the topological complexity of the formalism.It is shown that the topological complexity of Monadic Second Order Logic extended with the unbounding quantifier (introduced by Bojańczyk to express some asymptotic properties) over ω-words is the whole projective hierarchy. We also give the exact topological complexities of related classes of languages recognized by nondeterministic ωB-, ωS- and ωBS-automata studied by Bojańczyk and Colcombet, and a lower complexity bound for an alternating variant of ωBS-automata.We present the series of results concerning bi-unambiguous languages of infinite trees, i.e. languages recognized by unambiguous parity tree automata whose complements are also recognized by unambiguous parity automata. We give an example of a bi-unambiguous tree language G that is analytic-complete. We present an operation σ on tree languages with the property that σ(L) is topologically harder than any language in the sigma-algebra generated by the languages continuously reducible to L. If the operation is applied to a bi-unambiguous language than the result is also bi-unambiguous. We then show that the application of the operation can be iterated to obtain harder and harder languages. We also define another operation that enables a limit step iteration. Using the operations we are able to construct a sequence of bi-unambiguous languages of increasing topological complexity, of length at least ω square.
dc.description.abstract W niniejszej rozprawie rozważane są języki nieskończonych słów lub drzew definiowane poprzez automaty różnych typów lub formuły różnych logik. Pytamy o najwyższą możliwą pozycję w hierarchii borelowskiej lub rzutowej zajmowaną przez zbiory definiowane w danym formalizmie. Odpowiedź na to pytanie jest nazywana złożonością topologiczną formalizmu.Przedstawiony został dowód, że złożonością topologiczną Logiki Monadycznej Drugiego Rzędu rozszerzonej o kwantyfikator Unbounding (wprowadzony przez Bojańczyka w celu umożliwienia wyrażania własności asymptotycznych) na słowach nieskończonych jest cała hierarchia rzutowa. Obliczone zostały również złożoności topologiczne klas języków rozpoznawanych przez niedeterministyczne ωB-, ωS- i ωBS-automaty rozważane przez Bojańczyka i Colcombet'a, oraz zostało podane dolne ograniczenie złożoności wariantu alternującego ωBS-automatów.Zaprezentowane zostały wyniki dotyczące języków podwójnie jednoznacznych, tzn. języków rozpoznawanych przez jednoznaczne automaty parzystości na drzewach, których dopełnienia również są rozpoznawane przez jednoznaczne automaty parzystości. Podany został przykład podwójnie jednoznacznego języka drzew G, który jest analityczny-zupełny. Została wprowadzona operacja σ na językach drzew taka, że język σ(L) jest topologicznie bardziej złożony niż jakikolwiek język należący do sigma-algebry generowanej przez języki redukujące się w sposób ciągły do języka L. W wyniku zastosowania powyższej operacji do języka podwójnie jednoznacznego otrzymujemy język podwójnie jednoznaczny. Zostało pokazane, że kolejne iteracje aplikacji powyższej operacji dają coraz bardziej złożone języki. Została również wprowadzona druga operacja, która umożliwia krok graniczny iteracji. Używając obydwu powyższych operacji można skonstruować ciąg długości ω kwadrat złożony z języków podwójnie jednoznacznych o coraz większej złożoności.
dc.language.iso en
dc.rights info:eu-repo/semantics/restrictedAccess
dc.subject topological complexity
dc.subject Borel hierarchy
dc.subject projective hierarchy
dc.subject infinite words
dc.subject infinite trees
dc.subject MSO+U
dc.subject ωBS-automata
dc.subject unambiguous automata
dc.subject index hierarchy
dc.subject złożoność topologiczna
dc.subject hierarchia borelowska
dc.subject hierarchia rzutowa
dc.subject słowa nieskończone
dc.subject drzewa nieskończone
dc.subject MSO+U
dc.subject ωBS-automaty
dc.subject automaty jednoznaczne
dc.subject hierarchia indeksu
dc.title Topological Complexity of Sets Defined by Automata and Formulas
dc.title.alternative Złożoność topologiczna zbiorów deniowanych przez automaty i formuły
dc.title.alternative Topological Complexity of Sets Defined by Automata and Formulas
dc.type info:eu-repo/semantics/doctoralThesis
dc.contributor.department Wydział Matematyki, Informatyki i Mechaniki
dc.date.defence 2017-11-30
dc.identifier.apd 8690
dc.description.osid 2192
dc.contributor.email shummel@mimuw.edu.pl

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search Repository


Advanced Search

Browse

My Account

Statistics