Greibach Normal Form in Algebraically Complete Semirings

  • Zoltán Ésik
  • Hans Leiß

Abstract

We 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.
Published
2002-12-05
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