Greibach Normal Form in Algebraically Complete Semirings
AbstractWe give inequational and equational axioms for semirings with a fixed-point operator and formally develop a fragment of the theory of context-free languages. In particular, we show that Greibach's normal form theorem depends only on a few equational properties of least pre-fixed-points in semirings, and elimination of chain- and deletion rules depend on their inequational properties (and the idempotency of addition). It follows that these normal form theorems also hold in non-continuous semirings having enough fixed-points.
How to Cite
Ésik, Z., & Leiß, H. (2002). Greibach Normal Form in Algebraically Complete Semirings. BRICS Report Series, 9(46). https://doi.org/10.7146/brics.v9i46.21761
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.