Algebraically complete semirings and Greibach normal form (Q1772777): Difference between revisions

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.