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

DOI10.1016/S0020-0190(00)00055-7zbMATH Open1137.68418MaRDI QIDQ930285FDOQ930285

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)

Recommendations

• scientific article; zbMATH DE number 1101595
• scientific article; zbMATH DE number 1257079
• A uniform framework for problems on context-free grammars
• The inclusion problem of context-free languages: some tractable cases
• scientific article; zbMATH DE number 1556865

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• On the computational power of pushdown automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• Recognition and parsing of context-free languages in time n3
• Reachability analysis of pushdown automata: Application to model-checking
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Title not available (Why is that?)
• Regular canonical systems
• On the regular structure of prefix rewriting

Cited In (5)

• Title not available (Why is that?)
• The complexity of bisimilarity-checking for one-counter processes.
• Deciding equivalence of top-down XML transformations in polynomial time
• Simulating finite automata with context-free grammars.
• A uniform framework for problems on context-free grammars

This page was built for publication: An efficient automata approach to some problems on context-free grammars.

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