Abstract
Birkhoff's HSP theorem is that the models of a set of algebraic equations form a variety, i.e. a category of algebras which admits homomorphic images, subalgebras and products. We show here first, that every equational set of retract structures in combinatory logic is a variety, and second, that every set of combinators, closed under certain operations, is equational. It follows that the models of cumulative logic programs form an equational variety.
Chapter PDF
Similar content being viewed by others
References
K. Aberer, Combinatory differential fields and constructive analysis. PhD thesis ETH No. 9357, ETH Zürich, (1991).
B. Amrhein, Universal Algebra in Combinatory Logic. PhD thesis ETH No. 10 005, ETH Zürich, (1992).
H.P. Barendregt. The Lambda Calculus. North Holland, Amsterdam, (1984).
M. J. Beeson. Foundations of Constructive Mathematics. Springer, (1984).
G. Birkhoff. On the Structure of Abstract Algebras. Proc. Cambridge Phil. Soc. 31, (1935).
E. Engeler. Cumulative Logic Programs and Modelling. Logic Colloquium '86, North Holland, pp. 83–93, (1988).
E. Engeler. Sketch of a New Discipline of Modelling. Report Math. Dept. ETH Zürich, (1988).
J. W. Lloyd. Foundations of Logic Programming. Springer (1987).
J. Hodas, D. Miller, Logic Programming in a Fragment of Intuitionistic Linear Logic, Logics in Computer Science, Amsterdam, (1991).
G. Schwärzler Knowledge-Based Modelling of Cooperative Processes. PhD thesis ETH No. 9926, ETH Zürich (1992).
T. Weibel, Extension of Combinatory Logic to a Theory of Combinatory Representation, TCS, 97: 157–173, (1992).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Amrhein, B. (1994). Birkhoff's HSP-theorem for cumulative logic programs. In: Dyckhoff, R. (eds) Extensions of Logic Programming. ELP 1993. Lecture Notes in Computer Science, vol 798. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-58025-5_48
Download citation
DOI: https://doi.org/10.1007/3-540-58025-5_48
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58025-6
Online ISBN: 978-3-540-48417-2
eBook Packages: Springer Book Archive