scientific article; zbMATH DE number 3958761

MaRDI QIDQ3727409zbMATH OpenFDO

Authors Wojciech Rytter

Publication date 1984

zbMATH Keywords

context-free languageloop-free pushdown automatontwo-way nondeterministic pushdown automaton

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3978426
• On efficient recognition of transductions and relations
• The recognition of deterministic CFLs in small time and space
• scientific article; zbMATH DE number 3917742
• Parallel time O(log n) recognition of unambiguous context-free languages

Cited in

(14)

• On efficient recognition of transductions and relations
• Upper bounds on recognition of a hierarchy of non-context-free languages
• A characterization of exponential-time languages by alternating context- free grammars
• Space-efficient recognition of sparse self-reducible languages
• Certifying DFA bounds for recognition and separation
• Language recognition by two-way deterministic pushdown automata
• Language Recognition Power and Succinctness of Affine Automata
• Fast nondeterministic recognition of context-free languages using two queues
• The recognition of deterministic CFLs in small time and space
• scientific article; zbMATH DE number 3874644 (Why is no real title available?)
• scientific article; zbMATH DE number 3978426 (Why is no real title available?)
• A simplified lower bound for context-free-language recognition
• Simulation of two-way pushdown automata revisited
• Bounded fixed-point definability and tabular recognition of languages

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3727409)