Nie jesteś zalogowany |
An algebra for languages of infinite thin trees - continuation
- Prelegent(ci)
- Tomasz Idziaszek
- Afiliacja
- Uniwersytet Warszawski
- Termin
- 25 stycznia 2012 14:15
- Pokój
- p. 5870
- Seminarium
- Seminarium „Teoria automatów”
Still there is no satisfactory algebraic framework which deals with
languages of infinite trees. For example, a framework which we used with
Mikołaj to effectively characterize EF logic is an algebra with
infinite number of operations and axioms.
Instead of attacking the problem in its full generality, we focused on a certain class of infinite trees which is an intermediate class between finite trees and general infinite trees. The class is called "thin trees" and contains all trees with countably many infinite paths. It turns out that this class is quite robust. I will present an algebra for this class such that regular languages of thin trees are precisely those which are recognized by a homomorphisms onto finite algebras. I will also show an effective characterization of EF logic in thin trees which, unlike the general case, is given by a finite set of identities.
Instead of attacking the problem in its full generality, we focused on a certain class of infinite trees which is an intermediate class between finite trees and general infinite trees. The class is called "thin trees" and contains all trees with countably many infinite paths. It turns out that this class is quite robust. I will present an algebra for this class such that regular languages of thin trees are precisely those which are recognized by a homomorphisms onto finite algebras. I will also show an effective characterization of EF logic in thin trees which, unlike the general case, is given by a finite set of identities.
