✦ LIBER ✦

A hierarchy of eNCE families of graph languages

✍ Scribed by Changwook Kim

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 846 KB
Volume: 186
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(97)86542-5

No coin nor oath required. For personal study only.

✦ Synopsis

Even though eNCE and its subclasses have been studied intensively, their inclusion relations are not completely known. This paper proves some unknown relations among eNCE families of graph languages which yield, together with other known relations, a solid hierarchy of graph languages that completely determines equivalence, proper inclusion, and incomparability among NLC, NCE, eNLC, eNCE and their boundary, linear and apex subclasses. The bottom level of this hierarchy (i.e., Lin-A-NLC) contains an NP-complete graph language.

📜 SIMILAR VOLUMES

A hierarchy of deterministic languages

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

A geometric hierarchy of languages

✍ Nabil A. Khabbaz 📂 Article 📅 1974 🏛 Elsevier Science 🌐 English ⚖ 543 KB

This paper proves the existence of a hierarchy of languages which is properly contained in the context sensitive languages and which starts with the context-free family. The hierarchy is defined inductively by controlling labeled linear grammars with languages in one family to yield languages in the

McNaughton families of languages

✍ M. Beaudry; M. Holzer; G. Niemann; F. Otto 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 410 KB

In 1988 the Church-Rosser languages were introduced by McNaughton et al. as those languages that are recognized by ÿnite, length-reducing and con uent string-rewriting systems using extra non-terminal symbols. Here we generalize this concept by considering classes of languages that are obtained by o

A hierarchy of deterministic context-fre

A hierarchy of deterministic context-free ω-languages

✍ J. Duparc 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 386 KB

Ontology And The Hierarchy of Languages

✍ Robbins, Beverly 📂 Fiction 📅 0 🌐 English ⚖ 699 KB

Families of locally testable languages

✍ Pascal Caron 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 177 KB

## Kim, McNaughton and McCloskey have produced a polynomial time algorithm in order to test if a deterministic automaton recognizes a locally testable language. We provide a characterization in terms of automata for the strictly locally testable languages and for the strongly locally testable lang