Algorithmic Model Theory

Automata Theory and Algebraic Language Theory

There is a tight connection between automata and the monadic second-order theories of certain standard structures, like the order of the natural numbers or the infinite binary tree. In particular, Büchi and Rabin have shown that one can obtain decision procedures for these theories by translating formulae into automata. Automata theory has therefore become an essential tool in the investigation of monadic second-order logic.

Besides using monadic second-order logic one can also characterise regular languages algebraically via homomorphisms into finite algebras. This point of view is particularly suited to the classification of fragments of monadic second-order logic and to the development of corresponding decision procedures. There are well-developed algebraic theories for languages of finite and infinite words. For languages of finite trees a preliminary theory has also been developed, but for infinite trees only partial results exists. We are currently actively working on such a theory. The main obstacle in the development of an algebraic language theory in this context are missing combinatorial tools, like Ramseyan factorisation theorems for trees.

A A A | Print Print | Impressum Legal note | Contact Contact
    zum Seitenanfangzum Seitenanfang