On Distributive Fixed-Point Expressions
FB IV – Informatik,
54286 Trier, Germany
2 Institute of Informatics, University of Warsaw, Ul. Banacha 2, 02-097 Warsaw, Poland
Revised: 22 April 1999
For every fixed-point expression e of alternation-depth r, we construct a new fixed-point expression e' of alternation-depth 2 and size . Expression e' is equivalent to e whenever operators are distributive and the underlying complete lattice has a co-continuous least upper bound. We alternation-depth but also w.r.t. the increase in size of the resulting expression.
Mathematics Subject Classification: 68Q60 / 03D70 / 06D99 / 68Q25
Key words: Fixed-point expressions / distributivity / alternation-depth / lower bounds.
© EDP Sciences, 1999