Informace o projektu

Anotace je dostupná pouze v anglickém jazyce.

Algebraic Language Theory provides an alternative approach for describing regular languages that uses algebraic objects instead of automata. Its advantages are that one can use sophisticated algebraic tools to analyse languages. One area where Algebraic Language Theory has been particularly successful is in devising decision procedures for subclasses of regular languages, i.e., for the question whether a given regular language belongs to the class in question. For instance, a classical result of Schützenberger allows one to decide whether a given language is definable in first-order logic.
So far there are well-developed algebraic theories for languages of finite and infinite words. There are also candidates for languages of finite trees, but the theory for infinite trees is still in its infancy. The goal of this project is to develop an algebraic theory for languages of infinite trees. In a second step, we aim to use the emerging framework for first characterisation results starting with simple logics like EF and ultimately aiming at a characterisation of full first-order logic.