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

DOI10.1016/S0020-0190(00)00055-7MaRDI QIDQ930285zbMATH OpenFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 1232241 (Why is no real title available?)
• scientific article; zbMATH DE number 1101595 (Why is no real title available?)
• scientific article; zbMATH DE number 789389 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• On the computational power of pushdown automata
• On the regular structure of prefix rewriting
• Reachability analysis of pushdown automata: Application to model-checking
• Recognition and parsing of context-free languages in time n3
• Regular canonical systems

Cited in

(5)

• scientific article; zbMATH DE number 1101595 (Why is no real title available?)
• 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)