Lower bounds on space complexity for contextfree recognition
From MaRDI portal
Publication:1251077
DOI10.1007/BF00264016zbMath0389.68043OpenAlexW1980884852MaRDI QIDQ1251077
Publication date: 1979
Published in: Acta Informatica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf00264016
Related Items
On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes, On eliminating nondeterminism from Turing machines which use less than logarithm worktape space, Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties, Magic numbers in the state hierarchy of finite automata, A lower bound for the nondeterministic space complexity of context-free recognition, A combinatorial characterization of smooth LTCs and applications, Some classes of languages in \(NC^ 1\), Bandwidth constraints on problems complete for polynomial time
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Bracket-languages are recognizable in logarithmic space
- Eine untere Schranke für den Platzbedarf bei der Analyse beschränkter kontextfreier Sprachen
- Log Space Recognition and Translation of Parenthesis Languages
- A regularity test for pushdown machines
- Language recognition by marking automata