The Unsolvability of the Recognition of Linear Context-Free Languages
- 1 October 1966
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 13 (4) , 582-587
- https://doi.org/10.1145/321356.321365
Abstract
The problem of whether a given context-free language is linear is shown to be recursively undecidable.Keywords
This publication has 4 references indexed in Scilit:
- Operations Which Preserve Definability in LanguagesJournal of the ACM, 1963
- On ambiguity in phrase structure languagesCommunications of the ACM, 1962
- On certain formal properties of grammarsInformation and Control, 1959
- Finite Automata and Their Decision ProblemsIBM Journal of Research and Development, 1959