Lower bounds on space complexity for contextfree recognition
- 1 June 1979
- journal article
- Published by Springer Nature in Acta Informatica
- Vol. 12 (1), 33-61
- https://doi.org/10.1007/bf00264016
Abstract
No abstract availableKeywords
This publication has 11 references indexed in Scilit:
- Log Space Recognition and Translation of Parenthesis LanguagesJournal of the ACM, 1977
- Eine untere Schranke für den Platzbedarf bei der Analyse beschränkter kontextfreier SprachenPublished by Springer Nature ,1977
- Bracket-languages are recognizable in logarithmic spaceInformation Processing Letters, 1976
- A language over a one symbol alphabet requiring only O (log log n) spaceACM SIGACT News, 1975
- A note on tape bounds for sla language processingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1975
- About the deterministic simulation of nondeterministic (log n)-tape bounded turing machinesPublished by Springer Nature ,1975
- Language recognition by marking automataInformation and Control, 1972
- A regularity test for pushdown machinesInformation and Control, 1967
- Linear AlgebraPublished by Springer Nature ,1967
- Memory bounds for recognition of context-free and context-sensitive languagesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1965