Algebraically complete semirings and Greibach normal form

DOI10.1016/J.APAL.2004.10.008MaRDI QIDQ1772777zbMATH OpenOpenAlexFDO

Authors Zoltán Ésik, Hans Leiß

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 languagesKleene algebraequational theoryGreibach normal formalgebraically complete semiringConway semiringpre-fixed-point induction

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1948159
• Publication:3468619
• scientific article; zbMATH DE number 177807
• On Greibach normal form construction
• Analytic approach to context-free languages in the Greibach normal form

Cites work

• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 408802 (Why is no real title available?)
• scientific article; zbMATH DE number 549971 (Why is no real title available?)
• scientific article; zbMATH DE number 1047921 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3995637 (Why is no real title available?)
• scientific article; zbMATH DE number 1834683 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3316966 (Why is no real title available?)
• scientific article; zbMATH DE number 3366846 (Why is no real title available?)
• A Fully Equational Proof of Parikh's Theorem
• A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
• Complete systems of \(\mathcal B\)-rational identities
• Completeness of Park induction
• Decidability of bisimulation equivalence for process generating context-free languages
• Inductive \(^{*}\)-semirings
• Matrix Equations and Normal Forms for Context-Free Grammars
• Matrix and matricial iteration theories. I
• Two Complete Axiom Systems for the Algebra of Regular Events
• Une condition impliquant toutes les identités rationnelles
• Une remarque sur les systèmes complets d'identités rationnelles

Cited in

(5)

• scientific article; zbMATH DE number 4135415 (Why is no real title available?)
• Normal design algebra
• scientific article; zbMATH DE number 1948159 (Why is no real title available?)
• The matrix ring of a \(\mu\)-continuous Chomsky algebra is \(\mu\)-continuous
• On \(*\)-\(\lambda\)-semirings.

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

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