Open AccessGreibach Normal Form in Algebraically Complete Semirings
Author(s) -
Zoltán Ésik,
Hans Leiß
Publication year - 2002
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v9i46.21761
Subject(s) - idempotence , axiom , mathematics , context (archaeology) , fixed point , operator (biology) , point (geometry) , discrete mathematics , pure mathematics , algebra over a field , mathematical analysis , paleontology , biochemistry , chemistry , geometry , repressor , gene , transcription factor , biology
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.