Algebraically complete semirings and Greibach normal form

DOI10.1016/j.apal.2004.10.008zbMath1066.68084OpenAlexW1968315635MaRDI QIDQ1772777

Hans Leiß, Zoltán Ésik

Publication date: 21 April 2005

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2004.10.008

zbMATH Keywords

context-free languagesequational theoryKleene algebraGreibach normal formalgebraically complete semiringConway semiringpre-fixed-point induction

Mathematics Subject Classification ID

Algebraic theory of languages and automata (68Q70) Grammars and rewriting systems (68Q42) Semirings (16Y60) Equational classes, universal algebra in model theory (03C05)

Related Items (2)

Normal design algebra ⋮ On \(*\)-\(\lambda\)-semirings.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complete systems of \(\mathcal B\)-rational identities
• Completeness of Park induction
• Inductive \(^{*}\)-semirings
• Matrix and matricial iteration theories. I
• Decidability of bisimulation equivalence for process generating context-free languages
• Une remarque sur les systèmes complets d'identités rationnelles
• Une condition impliquant toutes les identités rationnelles
• A Fully Equational Proof of Parikh's Theorem
• A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
• Matrix Equations and Normal Forms for Context-Free Grammars
• Two Complete Axiom Systems for the Algebra of Regular Events

This page was built for publication: Algebraically complete semirings and Greibach normal form