Prime normal form and equivalence of simple grammars

DOI10.1016/j.tcs.2006.07.021zbMath1153.68024OpenAlexW2049140374MaRDI QIDQ860856

Wojciech Rytter, Wojciech Fraczak, Jurek Czyzowicz, Cédric Bastien

Publication date: 9 January 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.07.021

zbMATH Keywords

language equivalencedeterministic context-free languageprime normal formsimple grammar

Mathematics Subject Classification ID

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

Related Items (1)

Specific properties of canonical separated grammars

Cites Work

• A characterization of s-languages
• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• An axiomatic approach to the Korenjak-Hopcroft algorithms
• Implementation and Application of Automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Prime normal form and equivalence of simple grammars