✦ LIBER ✦

A characterization of two-way deterministic classes of languages

✍ Scribed by A.V. Aho; J.D. Ullman

Publisher: Elsevier Science
Year: 1970
Tongue: English
Weight: 731 KB
Volume: 4
Category: Article
ISSN: 0022-0000
DOI: 10.1016/s0022-0000(70)80027-7

No coin nor oath required. For personal study only.

✦ Synopsis

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 languages and various time and tape complexity classes are equivalent to classes of two-way deterministic balloon automata.

📜 SIMILAR VOLUMES

A hierarchy of deterministic languages

✍ Michael A. Harrison; Amiram Yehudai 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 957 KB

A predicative and decidable characteriza

A predicative and decidable characterization of the polynomial classes of languages

✍ S. Caporaso; M. Zito; N. Galesi 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 149 KB

Characterizations of PTIME, PSPACE, the polynomial hierarchy and its elements are given, which are decidable (membership can be decided by syntactic inspection to the constructions), predicative (according to points of view by Leivant and others), and are obtained by means of increasing restrictions

A characterization of the leaf language

A characterization of the leaf language classes

✍ Bernd Borchert; Riccardo Silvestri 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 602 KB

Bovet, Crescenzi, and Silvestri ( 1992 , 1995 ), and independently Vereshchagin ( 1994) , showed that many complexity classes in the polynomial time setting are leaf language classes, i.e. classes which are determined by two disjoint languages. They gave many examples but they did not characteriz

An algebraic characterization of determi

An algebraic characterization of deterministic regular languages over infinite alphabets

✍ Nissim Francez; Michael Kaminski 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 406 KB

We state and prove an inÿnite alphabet counterpart of the classical Myhill-Nerode theorem.

Yield-languages of two-way pushdown tree

Yield-languages of two-way pushdown tree automata

✍ Kai Salomaa 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 476 KB

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