DISI Dipartimento di Informatica e Scienze dell'Informazione

From total equational to partial first order

M. Cerioli , Till Mossakowski and Horst Reichel.

In E. Astesiano, H.-J. Kreowski and B. Krieg-Bruckner, editors, Algebraic Foundation of Information Systems Specification, chapter 3, pages 31--104, Berlin, 1999. Springer Verlag.

A preliminary version is in DISI-TR-96, 1996.

The focus of this Chapter is the incremental presentation of partial first-order logic, seen as a powerfull framework where the specification of most data types can be directly represented in the most natural way. Both model theory and logical deduction are described in full detail.
Alternatives to partiality, like (variants of) error algebras and order-sortedness are also discussed, showing their uses and limitations.
Moreover, both the total and the partial (positive) conditional fragment is investigated in detail, and in particular the existence of initial (free) objects for such restricted logical paradigms is proved.
Some more powerful algebraic frameworks are sketched at the end.
The compressed postscript version of the report version is available through anonymous ftp at ftp.disi.unige.it, in /person/CerioliM/IFIP96.ps.gz (202082 Kb)