A lower bound for the nondeterministic space complexity of context-free recognition
From MaRDI portal
Recommendations
- A simplified lower bound for context-free-language recognition
- TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES
- Upper bounds on recognition of a hierarchy of non-context-free languages
- Fast nondeterministic recognition of context-free languages using two queues
- Almost optimal sublinear time parallel recognition algorithms for three subclasses of context free languages
- scientific article; zbMATH DE number 3978426
- Parallel time O(log n) recognition of unambiguous context-free languages
- Space-efficient recognition of sparse self-reducible languages
- Lower bounds for context-free grammars
Cites work
- A regularity test for pushdown machines
- scientific article; zbMATH DE number 3575000 (Why is no real title available?)
- scientific article; zbMATH DE number 3311755 (Why is no real title available?)
- Lower bounds on space complexity for contextfree recognition
- Nondeterministic Space is Closed under Complementation
- The method of forced enumeration for nondeterministic automata
Cited in
(7)- Bridging across the (n) space frontier
- Space-efficient recognition of sparse self-reducible languages
- Certifying DFA bounds for recognition and separation
- Magic numbers in the state hierarchy of finite automata
- A combinatorial characterization of smooth LTCs and applications
- Limits of Baumslag-Solitar groups and dimension estimates in the space of marked groups.
- TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES
This page was built for publication: A lower bound for the nondeterministic space complexity of context-free recognition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1198017)
