Greibach Normal Form in Algebraically Complete Semirings

Zoltán Ésik
Hans Leiß

December 2002


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

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.