Fast recognition of pushdown automaton and context-free languages

DOI10.1016/S0019-9958(85)80024-3zbMATH Open0611.68052MaRDI QIDQ3751037FDOQ3751037

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 (12)

• Fast multiplication of matrices over a finitely generated semiring
• Language recognition by two-way deterministic pushdown automata
• Efficient algorithms for clique problems
• A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs
• Fast nondeterministic recognition of context-free languages using two queues
• Title not available (Why is that?)
• Improving quantum query complexity of Boolean matrix multiplication using graph collision
• The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
• A fast output-sensitive algorithm for Boolean matrix multiplication
• A Practical Simulation Result for Two-Way Pushdown Automata
• The Closest Pair Problem under the Hamming Metric
• If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser

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)