AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

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