Fast recognition of pushdown automaton and context-free languages

DOI10.1016/S0019-9958(85)80024-3MaRDI QIDQ3751037zbMATH OpenFDO

Authors Wojciech Rytter

Publication date 1985

Published in Information and Control (Search for Journal in Brave)

zbMATH Keywords

context-free languagestwo-way nondeterministic pushdown automata

Mathematics Subject Classification ID

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

Cited in

(11)

• Fast multiplication of matrices over a finitely generated semiring
• Language recognition by two-way deterministic pushdown automata
• Efficient algorithms for clique problems
• Fast nondeterministic recognition of context-free languages using two queues
• If the current clique algorithms are optimal, so is Valiant's parser
• A practical simulation result for two-way pushdown automata
• The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
• A fast output-sensitive algorithm for Boolean matrix multiplication
• The Closest Pair Problem under the Hamming Metric
• A combinatorial algorithm for all-pairs shortest paths in directed vertex-weighted graphs with applications to disc graphs
• Improved output-sensitive quantum algorithms for Boolean matrix multiplication

This page was built for publication: Fast recognition of pushdown automaton and context-free languages

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