Concerning two-adjacent context-free languages (Q1085985): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/0304-3975(85)90069-6 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W1988767282 / rank | |||
Normal rank | |||
Revision as of 21:01, 19 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Concerning two-adjacent context-free languages |
scientific article |
Statements
Concerning two-adjacent context-free languages (English)
0 references
1985
0 references
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.
0 references
k-adjacent languages
0 references
k-languages
0 references
context-free language
0 references
E0L-languages
0 references
