An efficient automata approach to some problems on context-free grammars.

DOI10.1016/S0020-0190(00)00055-7zbMath1137.68418MaRDI QIDQ930285

Ahmed Bouajjani, Peter Rossmanith, Bernard Willems, Alain Finkel, Pierre Wolper, Javier Esparza, Oded Maler

Publication date: 27 June 2008

Published in: Information Processing Letters (Search for Journal in Brave)

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items

The complexity of bisimilarity-checking for one-counter processes., Deciding equivalence of top-down XML transformations in polynomial time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the regular structure of prefix rewriting
• On the computational power of pushdown automata
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Regular canonical systems
• Recognition and parsing of context-free languages in time n3
• Reachability analysis of pushdown automata: Application to model-checking