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

algebraically complete semiringcontext-free languagesConway semiringequational theoryGreibach normal formKleene algebrapre-fixed-point induction

Mathematics Subject Classification ID

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

Review text

The authors define Park \({\mu}\)-semirings, which are ordered semirings with enough least pre-fixed points to interpret all \(\mu\)-terms. After that they add two more natural conditions, both inequations, to the axioms of Park \({\mu}\)-semirings in order to obtain algebraically complete semirings. An iteration {*} is defined which makes any algebraically complete semiring a symmetric inductive {*}-semiring and, if + is idempotent, a Kleene algebra. The main example is the semiring of a context-free language. The authors identify context-free grammars with simultaneous least-fixed-point terms \(\mu\overrightarrow{x}.\overrightarrow{t}\), where\(\overrightarrow{t}\) are polynomials. They show that the main normal forms for context-free grammars are equations between \(\mu\)-terms that hold in all algebraically complete semirings. Equational properties of fixed-point are sufficient for the core of the Greibach normal form and inequational properties (and idempotence of the semirings) are necessary for elimination of chain rules and \(\epsilon\)-rules. The paper ends with some open problems and concluding remarks.

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

• 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
• 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?)
• Inductive \(^{*}\)-semirings
• Matrix and matricial iteration theories. I
• Matrix Equations and Normal Forms for Context-Free Grammars
• 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

(7)

• On \(*\)-\(\lambda\)-semirings.
• scientific article; zbMATH DE number 4135415 (Why is no real title available?)
• scientific article; zbMATH DE number 1948159 (Why is no real title available?)
• The matrix ring of a -continuous Chomsky algebra is -continuous
• A proof theory of right-linear ( -)grammars via cyclic proofs
• A proof theory of ( -)context-free languages, via non-wellfounded proofs
• Normal design algebra

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)