Computing Reviews

Data types over multiple-valued logics
Pigozzi D. Theoretical Computer Science77(1-2):161-194,1990.Type:Article
Date Reviewed: 08/01/92

Pigozzi proposes to transform predicates in a relational structure into equations in an algebraic structure because of the many advantages of equational specifications over other specification methods. The process, known as algebraization, is applicable not only to Boolean logic but to nonclassical multivalued logics, such as the logics of Belnap, Kleene, Lukasiewics, and McCarthy, which are gaining importance in computer science. The main part of this paper investigates whether the properties of algebraization over Boolean logic apply to the nonclassical logics.

In nonclassical situations, a standard logic is said to be autoalgebraizable if an operator eq exists such that eq A is -admissible for every algebra A. The deduction theorem is said to hold for the logic if an operator de exists such that t 0 ,..., t n - 1 , r ⊨ s iff t 0 ,..., t n - 1 de ( r , s ) for all terms t 0 ,..., t n - 1 , r , s. The author shows that these two conditions are sufficient to guarantee that the main properties of Boolean algebraization will be retained in a similar form in nonclassical situations. For example, every generalized equality-test algebra is isomorphic to a direct limit of subdirect products of special equality-test algebras; a set of conditional equations is a complete specification if it is both initial and final; and every special equality-test data type with a finite initial specification is computable.

The paper is fairly long, and the formal definitions of various logics and algebras differ only slightly from one another. It would be useful to casual readers if informal comparisons were given, highlighting the main differences. Another small problem is that readers are referred no fewer than eight times to a more fundamental paper by the same author, which has not yet been published.

Reviewer:  T.H. Tse Review #: CR115135

Reproduction in whole or in part without permission is prohibited.   Copyright 2024 ComputingReviews.com™
Terms of Use
| Privacy Policy