Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-25T09:01:36.820Z Has data issue: false hasContentIssue false
  • English
  • Français

Primitive recursive algebraic theories and program schemes

Published online by Cambridge University Press:  17 April 2009

W. Kühnel ,
J. Meseguer ,
M. Pfender  and
I. Sols
W. Kühnel
Affiliation:
Fachbereich Mathematik, Technische Universität Berlin, Berlin, Germany;
J. Meseguer
Affiliation:
Departamento de Algebra y Fundamentos, Facultad de Ciencias, Universidad, Santiago de Compostela, Spain;
M. Pfender
Affiliation:
Fachbereich Mathematik, Technische Universität Berlin, Berlin, Germany;
I. Sols
Affiliation:
Departamento de Matematica, Universidad de Zaragoza, Zaragoza, Spain.
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We introduce primitive recursion as a generation process for arrows of algebraic theories in the sense of Lawvere and carry over important results on algebraic theories and functorial semantics to the enriched setting of “primitive recursive algebra”: existence of free primitive recursive theories and of theories presented by operations and equations on primitive recursive functions; existence of free models presented by generators and equations. Finally semantical correctness of translations is reduced to correctness for the basic operations. There is a connection to the theory of program schemes: program schemes involving primitive recursion correspond to arrows of a primitive recursive theory freely generated over a graph of basic operations. This theory T can be viewed as a programming language with “arithmetics” given by the basic operations and with DO-loops. A machine loaded with a compiler for T can be interpreted as a T-model in Lawvere's sense, preserving primitive recursion.

Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 17 , Issue 2 , October 1977 , pp. 207 - 233
Copyright
Copyright © Australian Mathematical Society 1977

References

[1]Alagić, Suad, Arbib, Michael A., Taylor, Robert W., “Algebraic models of syntax, semantics and data structures” (Computer and Information Science Technical Report 74B−1. University of Massachusetts at Amherst, Amherst, 1974).Google Scholar
[2]Arbib, M.A. and Give'on, Y., “Algebra automata I: Parallel programming as a prolegomena to the categorical approach”, Information and Control 12 (1968), 331–345.CrossRefGoogle Scholar
[3]Bénabou, Jean, “Structures algébriques dans les catégories”, Cahiers Topologie Géom. Différentielle 10 (1968), 1–126.Google Scholar
[4]Dubuc, Eduardo, “Adjoint triangles”, Reports on the Midwest Category Seminar II, 69–91 (Lecture Notes in Mathematics, 61. Springer-Verlag, Berlin, Heidelberg, New York, 1968).CrossRefGoogle Scholar
[5]Ehrig, Hartmut, Kühnel, Wolfgang, Pfender, Michael, “Characterization of recursion”, Category theory applied to computation and control, 137–143 (Proc. First Internat. Sympos.,San Francisco,1974. Lecture Notes in Computer Science, 25. Springer-Verlag, Berlin, Heidelberg, New York, 1975).CrossRefGoogle Scholar
[6]Eilenberg, Samuel, Wright, Jesse B., “Automata in general algebras”, Information and Control 11 (1967), 452–470.CrossRefGoogle Scholar
[7]Eilenberg, Samuel, Elgot, Calvin C., Recursiveness (Academic Press, New York and London, 1970).Google Scholar
[8]Elgot, C.C., “Monadic computation and iterative algebraic theories” (Report RC4564. IBM Research, Yorktown Heights, New York; San Jose, California; Zurich, Switzerland; 1973).Google Scholar
[9]Freyd, Peter, “Aspects of topoi”, Bull. Austral. Math. Soc. 7 (1972), 1–76.CrossRefGoogle Scholar
[10]Goguen, J.A. and Thatcher, J.W., “Initial algebra semantics” (Report RC4865. IBM Research, Yorktown Heights, New York; San Jose, California; Zurich, Switzerland; 1974).CrossRefGoogle Scholar
[11]*Joyal, M. André, “Arithmetic universes”,unpublished talk at Conference on Category Theory,Oberwolfach,July 1973.Google Scholar
[12]Kühnel, W., Meseguer, J., Pfender, M., Sols, I., “Algebras with actions and automata” (Preprint Reihe Mathematik, 9. Technische Universität, Berlin, 1975).Google Scholar
[13]Kühnel, W., Meseguer, J., Pfender, M., Sols, I., “Primitive recursive algebraic theories with applications to program schemes”, Cahiers Topologie Géom. Différentielle 16 (1975), 271–273.Google Scholar
[14]Lawvere, Francis William Jr., “Functorial semantics of algebraic theories” (PhD thesis, Columbia University, New York, 1963); see also: F. William Lawvere, “Functorial semantics of algebraic theories”, Proc. Nat. Acad. Sci. USA 50 (1963), 869–873.CrossRefGoogle Scholar
[15]Lawvere, F. William, “An elementary theory of the category of sets”, Proc. Nat. Acad. Sci. USA 52 (1964), 1506–1511.CrossRefGoogle ScholarPubMed
[16]Linton, F.E.J., “Some aspects of equational categories”,Proc. Conf. Categorical Algebra,La Jolla, California,1965, 84–95 (Springer-Verlag, Berlin, Heidelberg, New York, 1966).CrossRefGoogle Scholar
[17]Linton, F.E.J., “Coequalizers in categories of algebras”, Seminar on triples and categorical homology theory, 75–90 (Lecture Notes in Mathematics, 80. Springer-Verlag, Berlin, Heidelberg, New York, 1969).CrossRefGoogle Scholar
[18]Lane, Saunders Mac, Birkhoff, Garrett, Algebra (Macmillan, New York; Collier-Macmillan, London; 1967).Google Scholar
[19]Guaita, José Meseguer, “Algebra universal y recursion primitiva en categorias monoidales” (Departamento de Electricidad y Electronica, Universidad de Zaragoza, Spain, 1975).Google Scholar
[20]Meyer, A.R., Ritchie, D.M., “Computational complexity and program structure” (Report RC1817. IBM Research, Yorktown Heights, New York; San Jose, California; Zurich, Switzerland; 1967).Google Scholar
[21]Pfender, Michael, Universal algebra in S-monoidal categories (Algebra-Berichte, 20. Mathematisches Institut der Universität München, Verlag Uni-Druck, München, 1974).Google Scholar
[22]Lucia, Ignacio Sols, “Aportaciones a la teoria de topos, al algebra universal y a las matematicas fuzzy” (Departamento de Geometria y Topologia, Universidad de Zaragoza, Spain, 1975).Google Scholar