𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Property Testing of Regular Tree Languages

✍ Scribed by Frédéric Magniez; Michel de Rougemont

Publisher
Springer
Year
2007
Tongue
English
Weight
491 KB
Volume
49
Category
Article
ISSN
0178-4617

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A gap property of deterministic tree lan
A gap property of deterministic tree languages
✍ Damian Niwiński; Igor Walukiewicz 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 277 KB

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 i

Regular component decomposition of regul
Regular component decomposition of regular languages
✍ Y.J. Liu 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 198 KB

A language is regular if it can be recognized by a ÿnite automaton. According to the pumping lemma, every inÿnite regular language contains a regular subset of the form uv + w, where u; v; w are words and v is not empty. It is known that every regular language can be expressed as ( i∈I uiv + i wi) ∪