Přejít k obsahu | Přejít k hlavnímu menu | Přejít k vyhledávání

Informace o projektu
Algebraic Language Theory for Infinite Trees

Logo poskytovatele
Kód projektu
GA17-01035S
Období řešení
1/2017 - 12/2019
Investor / Programový rámec / typ projektu
Grantová agentura ČR
  • Standardní projekty
Fakulta / Pracoviště MU
Fakulta informatiky

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.

Publikace

Počet publikací: 5

2021

2020

2018

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info