Algebraic methods in the theory of infinite trees

Celem niniejszej rozprawy jest zbadanie algebraicznego podejścia do języków regularnych drzew nieskończonych. Realizacja tego celu przebiegła dwutorowo: poprzez zaproponowanie algebraicznej struktury dla drzew nieskończonych oraz uzyskanie za jej pomocą efektywnej charakteryzacji dla pewnych własności języków. W pierwszej części rozprawy przedstawiam trzy algebry – dwie dla języków drzew cienkich i jedną dla języków dowolnych drzew nieskończonych. Pokazuję również zależność pomiędzy językami regularnymi a językami rozpoznawanymi przez te algebry. Nieskończone drzewo jest cienkie, jeśli zawiera przeliczalnie wiele gałęzi. Cienkie drzewa mogą być traktowane jako pośrednia struktura pomiędzy słowami nieskończonymi a drzewami nieskończonymi. Ponieważ klasa drzew cienkich jest prostsza niż klasa wszystkich drzew, a jednocześnie interesująca i o dobrych własnościach, część wyników rozprawy dotyczy drzew cienkich. Wierzę, że badanie drzew cienkich może nam pomóc lepiej zrozumieć ogólne drzewa nieskończone. Druga część rozprawy dotyczy zastosowań metod algebraicznych opisanych w części pierwszej. Pokazuję jak rozstrzygać, czy dany język regularny cienkich drzew jest przemienny, zamknięty na bisymulację, otwarty w standardowej topologii oraz definiowalny w logice temporalnej EF. Ponadto dla języków dowolnych drzew nieskończonych pokazuję jak rozstrzygać ich definiowalność w logice EF.

In the thesis we explore an algebraic approach to regular languages of infinite trees. We have decided to take a two-pronged approach: to develop a concept of an algebraic structure for infinite trees and to use it to get an effective characterization for some properties of languages. In the first part of the thesis we develop three algebras – two for languages of thin trees, and one for languages of arbitrary infinite trees. We show the correspondence between regular languages and languages recognized by our algebras. An infinite tree is thin if it contains countably many infinite paths. Thin trees can be seen as intermediate structures between infinite words and infinite trees. Since the class of thin trees is simpler than the class of all trees, but at the same time robust and interesting, we focus in the thesis on thin trees. We believe that they are a good stepping stone on the way to understand regular languages of arbitrary infinite trees. In the second part of the thesis we show some applications of the algebraic theory presented in the first part. We show how to decide whether a given regular language of thin trees is commutative, invariant under bisimulation, open in a certain topology, and definable in the temporal logic EF. For languages of arbitrary infinite trees we show how to decide definability in the logic EF.