The Equational Specification of Finite Minimal Unoids Using only Unary Hidden Functions

Article type: Research Article

Authors: Bergstra, Jan A.^a | Meyer, John-Jules Ch.^b

Affiliations: [a] Institute of Applied Mathematics and Computer Science, University of Leiden | [b] Wiskundig Seminarium, Free University Amsterdam

Abstract: In [5] it has been proved that by using hidden functions the number of equations needed to specify a finite data type is bounded by numbers depending only on the signature of that data type. In the special case of a finite minimal unoid, however, it seems to be relevant to ask whether or not a specification can also be made by a bounded number of equations using only unary hidden functions. In this paper we prove that this can be done.

Keywords: algebraic data types, finite data types, unoids, equational specifications with hidden functions, boundedness properties

DOI: 10.3233/FI-1982-5203

Journal: Fundamenta Informaticae, vol. 5, no. 2, pp. 143-170, 1982