Campus Event Calendar

Event Entry

What and Who

Algebraic Characterization of Hedge Languages

Michael Waldvogel
PhD Applicant
AG 1  
AG Audience

Date, Time and Location

Tuesday, 15 November 2011
30 Minutes
E1 4
Rotunde D1


In automata theory it has always been of interest to find some finite reprensentation of infinite languages. In case of word languages this connection to the field algebra has been achieved with the well-known theorem of Myhill & Nerode. In this work we will examine recognizable hedge languages that are to be considered as a generalization of tree languages over ranked alphabets, whereby recognizability is introduced by some class of automatas. We will see that for these hedge languages some algebraic characterization can be achieved in a similar fashion as in the word case. Besides, this work shows that every hedge automaton is bottom-up determinizable; the smallest algebra saturating some hedge language is of finite index iff that language is recognized by some hedge automaton; and for any hedge language there is a uniquely determined hedge automaton. The presentation will focus on problems that arise with the transition from tree languages over ranked alphabets to hedge languages.


Benjamin Doerr
--email hidden
passcode not visible
logged in users only

Franziska Huth, 11/08/2011 11:00
Franziska Huth, 11/03/2011 16:14 -- Created document.