You are not logged in | Log in

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.