Lower bounds on space complexity for contextfree recognition

DOI10.1007/BF00264016zbMath0389.68043OpenAlexW1980884852MaRDI QIDQ1251077

Helmut Alt

Publication date: 1979

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00264016

zbMATH Keywords

CONTEXT-FREE LANGUAGESPACE COMPLEXITY

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

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