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.

---