𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A gap property of deterministic tree languages

✍ Scribed by Damian Niwiński; Igor Walukiewicz

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
277 KB
Volume
303
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

We show that a tree language recognized by a deterministic parity automaton is either hard for the co-B uchi level and therefore cannot be recognized by a weak alternating automaton, or is on a very low level in the hierarchy of weak alternating automata. A topological counterpart of this property is that a deterministic tree language is either 1 1 complete (and hence nonBorel), or it is on the level 0 3 of the Borel hierarchy. We also give a new simple proof of the strictness of the hierarchy of weak alternating automata.

📜 SIMILAR VOLUMES

Output String Languages of Compositions
Output String Languages of Compositions of Deterministic Macro Tree Transducers
✍ Joost Engelfriet; Sebastian Maneth 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 376 KB

The composition of total deterministic macro tree transducers gives rise to a proper hierarchy with respect to their output string languages (these are the languages obtained by taking the yields of the output trees). There is a language not in this hierarchy which can be generated by a (quite restr

A characterization of two-way determinis
A characterization of two-way deterministic classes of languages
✍ A.V. Aho; J.D. Ullman 📂 Article 📅 1970 🏛 Elsevier Science 🌐 English ⚖ 731 KB

It is shown that a class of languages is defined by a class of two-way deterministic balloon automata if and only if that class is closed under marked union, marked Kleene closure and the inverse mappings performed by deterministic GSMs that move two ways on the input. Hence, the context sensitive l