Survey on classes of interpretations and some of their applications
Abstract
We introduce classes of interpretations. We characterize the free and Herbrand interpretations for a class. We define the algebraic, equational, relational and first-order classes of interpretations, study their properties and relate them to the literature. We apply this study to derive complete proof systems for deducing (in some (in) equational logic) all (in) equalitions valid in a class.
References
[1]
/ADJ/ ADJ, Algebraic theories, I-adic theories and program semantics, Proc. 3rd Workshop on Categorical and Algebraic methods in Computer Science, Dortmund University - Report no 114 (1980), 109--114.
[2]
/AN/ H. Andreka, I. Nemeti, Generalization of variety and quasi-variety concepts to partial algebras through category theory, Dissertations Mathematicae (Rozprawy Math.) 204 (1982).
[3]
/AN1/ H. Andreka, I. Nemeti, Applications of Universal Algebra, Model theory and categories in Computer Science, FCT 81, LNCS 117, Berlin (1981), 16--23.
[4]
/ARN/ A. Arnold, M. Nivat, Non-deterministic recursive program schemes, FCT 77, LNCS 56, Berlin (1977), 12--21.
[5]
/BG1/ D. Benson, I. Guessarian, Algebraic solutions to recursion schemes, LITP-Report no 81-66, Paris (1981), submitted for publication.
[6]
/BG2/ D. Benson, I. Guessarian, Iterative and recursive matrix theories, WSU Report CS-81-XXX (1981), submitted for publication.
[7]
/BS/ J. Bell, A. Slomson, Models and Ultraproducts, North-Holland, London (1971).
[8]
/B/ G. Birkhoff, Lattice theory, AMS coll., 3rd edition, New-York (1979)
[9]
/BL/ S. Bloom, R. Tindell, Varieties of "IF-THEN-ELSE", IBM Report, Yorktown Heights (1982).
[10]
/BD/ G. Boudol, Sémantique opérationnelle et algébrique des programmes récursifs non-déterministes, Thesis, LITP-Report no 80-28 (1980).
[11]
/BK/ G. Boudol, L. Kott, Recursion induction principle revisited, to appear in TCS.
[12]
/C/ P. M. Cohn, Universal Algebra, Harper-Row, New York (1965).
[13]
/CO/ B. Courcelle, Infinite trees in normal form and recursive equations having a unique solution, MST 13 (1979), 131--180.
[14]
/CG/ B. Courcelle, I. Guessarian, On some classes of interpretations, JCSS 17 (1978), 388--413.
[15]
/CR/ B. Courcelle, J.-C. Raoult, Completions of ordered magmas, Fundamentae Informaticae 3 (1980), 105--116.
[16]
/COU/ G. Cousineau, Les arbres à feuilles indicées: un cadre algébrique des structures de controle, thesis, Paris (1977).
[17]
/E/ C. C. Elgot, Monadic computation and iterative algebraic theories, Logic colloquium 73, North-Holland, Amsterdam (1975).
[18]
/EG/ F. Ermine, I. Guessarian, Terminaison et simplification de programmes, Revue Tech. Thomson-CSF, 12 (1980), 71--90.
[19]
/EN/ J. Engelfriet, Some open questions and recent results on tree transducers and tree languages, in Formal languages: perspectives and open problems, Academic Press, London (1980), 241--286.
[20]
/G/ J. H. Gallier, n-rational algebras, Univ. of Pennsylvania report (1981),
[21]
/GB/ R. M. Burstall, J. A. Goguen, Institutions: Logic and specification, this conference.
[22]
/GI/ S. Ginali, Regular trees and the free iterative theory, JCSS 18 (1979), 228--242.
[23]
/GR/ G. Grätzer, Universal Algebra, 2nd edition, Springer-Verlag, Berlin (1979).
[24]
/GU/ I. Guessarian, Algebraic Semantics, LNCS 99, Springer-Verlag, Berlin (1981)
[25]
/GU1/ I. Guessarian, Schémas récursifs polyadiques: équivalences et classes d'interprétation, Thesis, Paris (1975).
[26]
/GU2/ I. Guessarian, Survey on classes of interpretations and some of their applications, Proc. US-French conference on applications of Algebraic methods in Language definition and compiling, Fontainebleau (1982), to appear.
[27]
/GM/ I. Guessarian, J. Meseguer, Remarks on the axiomatisation of "if-then-else", in preparation.
[28]
/GPP/ I. Guessarian, F. Parisi-Presicce, A remark on iterative and regular factor algebras, submitted for publication.
[29]
/K/ L. Kott, Des substitutions dans les systemes d'équations algébriques sur le magma; application aux transformations de programme et à leur correction, Thesis, Paris (1979).
[30]
/LP/ D. Lehmann, A. Pasztor, Epis need not be dense, TCS 17 (1982), 151--162.
[31]
/MAC/ J. McCarthy, A basis for a mathematical theory of computation, in Computer Programming and formal systems, North-Holland, Amsterdam (1963), 33--70.
[32]
/MA/ A. I. Mal'cev, Algebraic systems, North-Holland, Amsterdam (1973)
[33]
/MI/ J. Meseguer, Varieties of chain complete algebras, J. Pure and Applied Algebra 19 (1980), 347--383.
[34]
/M2/ J. Meseguer, A. Birkhoff-like theorem for algebraic classes of interpretations of program schemes, LNCS 107, Springer-Verlag, Berlin (1981), 152--168.
[35]
/MI/ R. Milner, A calculus of communication systems, LNCS 92, Springer Verlag Berlin (1980).
[36]
/NE/ E. Nelson, Iterative algebras, McMaster University Comp. Sci. Tec. Rep no 81 - CS - 12.
[37]
/NI/ M. Nivat, Langages algébriques sur le magma libre et sémantique des shcémas de programmes, Proc. 1st ICALP, North Holland, Amsterdam (1972).
[38]
/N/ M. Nivat, On the interpretation of recursive polyadic program schemes, Symp. Mathematica 15, Rome (1975), 255--281.
[39]
/O/ F. J. Oles, A category theoretic approach to the semantics of programming languages, Ph. D. thesis, Syracuse University (1982).
[40]
/P/ A. Pasztor, Chain-continuous algebras - a variety of partial algebras, Stuttgart Univ. Report no 7-82.
[41]
/PP/ F. Parisi-Presicce, Uniqueness of solutions of fixedpoint equations in regular extensions of iterative algebras, Ph. D, Univ. of Connecticut (1981).
[42]
/R/ W. C. Rounds, Mappings and grammars on trees, MST 4 (1970), 257--287.
[43]
/S/ D. Scott, Date types as lattices, SIAM Jour. Comp. 5 (1976), 522--587.
[44]
/SE/ R. Sethi, Conditional expressions with equality tests, J. ACM 25 (1978), 667--674.
[45]
/T/ J. Tiuryn, Unique fixed points vs. least fixed points, TCS 12 (1980), 229--254.
[46]
/W/ W. Wechler, R-fuzzy computation, to appear in Fuzzy Inf. and decision processes.
- Survey on classes of interpretations and some of their applications
Recommendations
First-Order Interpretations of Bounded Expansion Classes
The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter tractable over ...
Disunification for ultimately periodic interpretations
LPAR'10: Proceedings of the 16th international conference on Logic for programming, artificial intelligence, and reasoningDisunification is an extension of unification to first-order formulae over syntactic equality atoms. Instead of considering only syntactic equality, I extend a disunification algorithm by Comon and Delor to ultimately periodic interpretations, i.e. ...
Mitotic classes
COLT'07: Proceedings of the 20th annual conference on Learning theoryFor the natural notion of splitting classes into two disjoint subclasses via a recursive classifier working on texts, the question is addressed how these splittings can look in the case of learnable classes. Here the strength of the classes is compared ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 1983 Author.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 July 1983
Published in SIGACT Volume 15, Issue 3
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 154Total Downloads
- Downloads (Last 12 months)38
- Downloads (Last 6 weeks)4
Reflects downloads up to 09 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in