×

Equational type logic. (English) Zbl 0716.03022

Summary: Equational type logic is an extension of (conditional) equational logic that enables one to deal in a single, unified framework with diverse phenomena such as partiality, type polymorphism and dependent types. In this logic, terms may denote types as well as elements, and atomic formulae are either equations or type assignments. Models of this logic are type algebras, viz. universal algebras equipped with a binary relation - to support type assignment. Equational type logic has a sound and complete calculus, and initial models exist. The use of equational type logic is illustrated by means of simple examples, where all of the aforementioned phenomena occur. Formal notions of reduction and extension are introduced, and their relationship to free constructions is investigated. Computational aspects of equational type logic are investigated in the framework of conditional term rewriting systems, generalizing known results on confluence of these systems. Finally, some closely related work is reviewed and future research directions are outlined in the conclusions.

MSC:

03C05 Equational classes, universal algebra in model theory
68Q65 Abstract data types; algebraic specification
08B05 Equational logic, Mal’tsev conditions
68Q42 Grammars and rewriting systems

References:

[1] Andreka, H.; Burmeister, P.; Nemeti, I., Quasivarieties of partial algebras—a unifying approach towards a two-valued model theory for partial algebras (1980), FB Mathematik und Informatik: FB Mathematik und Informatik TH Darmstadt, Preprint Nr. 557 · Zbl 0537.08004
[2] Bergstra, J. A.; Klop, J. W., Conditional rewrite rules: confluence and termination, J. Comput. Systems Sci., 32, 3, 323-362 (1986) · Zbl 0658.68031
[3] Bernot, G.; Bidoit, M.; Choppy, C., Abstract data types with exception handling: an initial approach based on a distinction between exceptions and errors, Theoret. Comput. Sci., 46, 1, 13-45 (1986) · Zbl 0603.68015
[4] Birkhoff, G.; Lipson, J. D., Heterogeneous algebras, J. Combin. Theory, 8, 115-133 (1970) · Zbl 0211.02003
[5] Breazu-Tannen, V.; Gallier, J., Polymorphic rewriting conserves algebraic strong normalization and confluence, (Ausiello, G.; Dezani-Ciancaglini, M.; Ronchi Della Rocca, S., Automata, Languages and Programming, Proc. 16th ICALP. Automata, Languages and Programming, Proc. 16th ICALP, Lecture Notes in Computer Science, 372 (1989), Springer: Springer Berlin), 137-150 · Zbl 0686.68022
[6] Broy, M.; Wirsing, M., Partial abstract types, Acta Inform., 18, 47-64 (1982) · Zbl 0494.68020
[7] Burmeister, P., A Model Theoretic Oriented Approach to Partial Algebras (1986), Akademie-Verlag: Akademie-Verlag Berlin · Zbl 0598.08004
[8] Burstall, R. M.; Goguen, J. A., Putting theories together to make specifications, (Proc. 5th Internat. Joint Conf. on Artificial Intelligence (1977), Kaufman: Kaufman Cambridge, MA), 1045-1058
[9] Ehrig, H.; Mahr, B., Fundamentals of Algebraic Specification, 1 (1985), Springer: Springer Berlin · Zbl 0557.68013
[10] Futatsugi, K.; Goguen, J. A.; Jouannaud, J.-P.; Meseguer, J., Principles of OBJ2, (Proc. Symp. Principles of Programming Languages (1985), ACM), 52-66
[11] Goguen, J. A., Abstract errors for abstract data types, (Proc. IFIP Working Conf. on Formal Description of Programming Concepts (1977), MIT: MIT Cambridge, MA) · Zbl 0373.68024
[12] Goguen, J. A., Order sorted algebras, semantics and theory of computation, (Report 14 (1978), University of California at Los Angeles) · Zbl 0306.68028
[13] Goguen, J.; Burstall, R., Introducing institutions, (Clarke, E.; Kozen, D., Proc. Logics of Programming Workshop. Proc. Logics of Programming Workshop, Lecture Notes in Computer Science, 164 (1984), Springer: Springer Berlin), 221-256 · Zbl 1288.03001
[14] Goguen, J. A.; Meseguer, J., Models and equality for logical programming, (Ehrig, H.; Kowalski, R.; Levi, G.; Montanari, U., TAPSOFT ’87, Volume 2. TAPSOFT ’87, Volume 2, Lecture Notes in Computer Science, 250 (1987), Springer: Springer Berlin), 1-22 · Zbl 0626.68032
[15] Goguen, J. A.; Thatcher, J. W.; Wagner, E. G., An initial algebra approach to the specification, correctness, and implementation of abstract data types, (Yeh, R., Current Trends in Programming Methodology IV (1978), Prentice Hall: Prentice Hall Englewood Cliffs, NJ), 80-149
[16] Hatcher, W. S., The Logical Foundations of Mathematics (1982), Pergamon Press: Pergamon Press Oxford · Zbl 0191.28205
[17] Higgins, P. J., Algebras with a scheme of operators, Math. Nachr., 27, 115-132 (1963) · Zbl 0117.25903
[18] Manca, V.; Salibra, A., Budapest. Budapest, Proc. Internat. Conf. on Algebraic Logic (August 8-14, 1988), to appear in:
[19] Manca, V.; Salibra, A.; Scollo, G., On the nature of TELLUS, a typed equational logic look over uniform specification, (Kreczmar, A.; Mirkowska, G., Mathematical Foundations of Computer Science 1989. Mathematical Foundations of Computer Science 1989, Lecture Notes in Computer Science, 379 (1989), Springer: Springer Berlin), 338-349 · Zbl 0755.68105
[20] V. Manca, A. Salibra and G. Scollo, On the expressiveness of equational type logic, forthcoming.; V. Manca, A. Salibra and G. Scollo, On the expressiveness of equational type logic, forthcoming. · Zbl 0768.08003
[21] Martin-Löf, P., An intuitionistic theory of types: predicative part, (Rose, H. E.; Shepherdson, J. C., Logic Colloquium 1973 (1975), North-Holland: North-Holland Amsterdam), 73-118 · Zbl 0334.02016
[22] Mosses, P. D., Unified Algebras and Institutions, (Proc. 4th IEEE Symp. on Logic In Computer Science. Proc. 4th IEEE Symp. on Logic In Computer Science, Pacific Grove, CA (1989), IEEE) · Zbl 0716.68066
[23] Poigné, A., Partial algebras, subsorting and dependent types: prerequisites of error handling in algebraic specification, (Sannella, D.; Tarlecki, A., Recent Trends in Data Type Specification. Recent Trends in Data Type Specification, Lecture Notes in Computer Science, 332 (1988), Springer: Springer Berlin), 208-234 · Zbl 0659.68028
[24] Reichel, H., Initial Computability, Algebraic Specifications, and Partial Algebras (1987), Clarendon Press: Clarendon Press Oxford · Zbl 0634.68001
[25] Rus, T., HAS-hierarchy: a natural tool for language specification, Fund. Inform., 3, 3, 269-294 (1979) · Zbl 0452.68087
[26] Scollo, G., On the use of equational type logic for software engineering and protocol design, Constantine, Algeria. Constantine, Algeria, 1st Maghrebin Conf. on Artificial Intelligence and Software Engineering (1989)
[27] Smolka, G., Type logic, Berlin. Berlin, Proc. 6th ADT Workshop (1988), Abstract.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.