Fast recognition of pushdown automaton and context-free languages

DOI10.1016/S0019-9958(85)80024-3zbMath0611.68052MaRDI QIDQ3751037

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

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

Related Items (9)

A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs ⋮ Improving quantum query complexity of Boolean matrix multiplication using graph collision ⋮ If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser ⋮ The Closest Pair Problem under the Hamming Metric ⋮ A fast output-sensitive algorithm for Boolean matrix multiplication ⋮ Fast multiplication of matrices over a finitely generated semiring ⋮ Efficient algorithms for clique problems ⋮ A Practical Simulation Result for Two-Way Pushdown Automata ⋮ Unnamed Item

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