Concerning two-adjacent context-free languages

DOI10.1016/0304-3975(85)90069-6MaRDI QIDQ1085985zbMATH OpenOpenAlexFDO

Authors Elias Dahlhaus, Haim Gaifman

Publication date 1985

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(85)90069-6

zbMATH Keywords

context-free languageE0L-languagesk-adjacent languagesk-languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Review text

The k-adjacent languages appeared first in a paper of \textit{J. Gonczarowski} and \textit{E. Shamir} [J. Comput. Syst. Sci. 30, 249-273 (1985; Zbl 0601.68057)] as a special case of k-languages. Every context- free language is a k-language as well as a k-adjacent language. For each \(k>1\), there are k-languages which are not context-free. By contrast, very little has been known about the adjacent case. This paper contains the following result: There are 2-adjacent languages which are not context-free and not even E0L-languages. A variant of 2- adjacent languages which contains all E0L-languages is also presented.

Recommendations

• A note on context-free languages
• Two complexity measures for context-free languages
• On an extension of the class of context-free languages
• On context-free and Szilard languages
• scientific article; zbMATH DE number 4035186
• On commutative context-free languages
• scientific article; zbMATH DE number 59504
• scientific article; zbMATH DE number 3254902
• On regularity of context-free languages
• Expressiveness and complexity of regular pure two-dimensional context-free languages

Cites work

• Applications of scheduling theory to formal language theory
• Closure properties of some families of languages associated with biological systems
• Complexity of some problems concerningL systems
• Description of developmental languages using recurrence systems
• scientific article; zbMATH DE number 3569855 (Why is no real title available?)
• scientific article; zbMATH DE number 3802813 (Why is no real title available?)
• Pattern selector grammars and several parsing algorithms in the context- free style

Cited in

(7)

• Applications of scheduling theory to formal language theory
• A pumping result for 2-context-free languages
• On the Kleijn-Rozenberg k-adjacent languages
• Manipulating derivation forests by scheduling techniques
• scientific article; zbMATH DE number 3861188 (Why is no real title available?)
• Hierarchy of k-context-free languages part 1
• Hierarchy ofk-context-free languages

This page was built for publication: Concerning two-adjacent context-free languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1085985)