On distributive fixed-point expressions

Authors
Seidl, H Niwinski, D
Citation
H. Seidl et D. Niwinski, On distributive fixed-point expressions, RAIRO-INF, 33(4-5), 1999, pp. 427-446
Citations number
20
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS
ISSN journal
09883754 → ACNP
Volume
33
Issue
4-5
Year of publication
1999
Pages
427 - 446
Database
ISI
SICI code
0988-3754(199907/10)33:4-5<427:ODFE>2.0.ZU;2-Y
Abstract
For every fixed-point expression e of alternation-depth r, we construct a n ew fixed-point expression e' of alternation-depth 2 and size O(r . \e\). Ex pression e' is equivalent to e whenever operators are distributive and the underlying complete lattice has a co-continuous least upper bound. We show that our transformation is optimal not only w.r.t. alternation-depth but al so w.r.t. the increase in size of the resulting expression. AMS Subject Cla ssification. 68Q60, 03D70, 06D99, 68Q25.