TY - JOUR AU - Ésik, Zoltán AU - Leiß, Hans PY - 2002/12/05 Y2 - 2024/03/28 TI - Greibach Normal Form in Algebraically Complete Semirings JF - BRICS Report Series JA - BRICS VL - 9 IS - 46 SE - Articles DO - 10.7146/brics.v9i46.21761 UR - https://tidsskrift.dk/brics/article/view/21761 SP - AB - 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. ER -