Go to main content | Go to main menu | Go to search

Project information
Algebraic Language Theory for Infinite Trees

Investor logo
Project Identification
GA17-01035S
Project Period
1/2017 - 12/2019
Investor / Pogramme / Project type
Czech Science Foundation
  • Standard Projects
MU Faculty or unit
Faculty of Informatics

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.

Publications

Total number of publications: 5

2021

2020

2018

You are running an old browser version. We recommend updating your browser to its latest version.

More info