Oxford Journals
tools journals homepage advanced search contact help
Journal of Logic and Computation: Current Issue

OUP > Journals > Computing/Engineer. & Mathematics/Stats. > Journal of Logic and Computation

Journal of Logic and Computation

Volume 12, Issue 2, April 2002: pp. 271-300

Continuous Additive Algebras and Injective Simulations of Synchronization Trees

Zoltán Ésik1

1Dept. of Computer Science, University of Szeged, P.O.B. 652, 6701 Szeged, Hungary. esik@inf.u-szeged.hu

The (in)equational properties of the least fixed point operation on ([ohgr]-)continuous functions on ([ohgr]-)complete partially ordered sets are captured by the axioms of (ordered) iteration algebras, or iteration theories. We show that the inequational laws of the sum operation in conjunction with the least fixed point operation in continuous additive algebras have a finite axiomatization over the inequations of ordered iteration algebras. As a byproduct of this relative axiomatizability result, we obtain complete infinite inequational and finite implicational axiomatizations. Along the way of proving these results, we give a concrete description of the free algebras in the corresponding variety of ordered iteration algebras. This description uses injective simulations of regular synchronization trees. Thus, our axioms are also sound and complete for the injective simulation (resource bounded simulation) of (regular) processes.

Keywords: Equational logic; fixed points; synchronization trees; simulation

Table of Contents   Full-Text PDF (336 KB)

Oxford University Press
Published by Oxford University Press
Copyright ©Oxford University Press 2003
Print ISSN: 0955-792X  Online ISSN: 1465-363X.
Oxford University Press Privacy Policy and Legal Statement