A lower bound for the nondeterministic space complexity of context-free recognition

DOI10.1016/0020-0190(92)90127-HzbMath0780.68081OpenAlexW2044579324MaRDI QIDQ1198017

Viliam Geffert, Kurt Mehlhorn, Helmut Alt

Publication date: 16 January 1993

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(92)90127-h

zbMATH Keywords

computational complexitylower boundcontext-free languagenondeterministic space complexity

Mathematics Subject Classification ID

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

Related Items (5)

Limits of Baumslag-Solitar groups and dimension estimates in the space of marked groups. ⋮ Magic numbers in the state hierarchy of finite automata ⋮ Quantum computation with write-only memory ⋮ A combinatorial characterization of smooth LTCs and applications ⋮ Bridging across the \(\log(n)\) space frontier

Cites Work

• Unnamed Item
• Unnamed Item
• The method of forced enumeration for nondeterministic automata
• Lower bounds on space complexity for contextfree recognition
• Nondeterministic Space is Closed under Complementation
• A regularity test for pushdown machines

This page was built for publication: A lower bound for the nondeterministic space complexity of context-free recognition