An algebra for languages of infinite thin trees - continuation

Speaker(s)

Tomasz Idziaszek

Affiliation

Uniwersytet Warszawski

Date

Jan. 25, 2012, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---