Rational algebraic theories and fixed-point solutions
- 1 October 1976
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 147-158
- https://doi.org/10.1109/sfcs.1976.24
Abstract
In a wide variety of situations, computer science has found it convenient to define complex object as (fixed-point) solutions of certain equations. This has been done in both algebraic and order-theoretic settings, and has often been contrasted with other approaches. This paper shows how to formulate such solutions in a setting which encompasses both algebraic and order-theoretic aspects, so that the advantages of both worlds are available. Moreover, we try to show how this is consistent with other approaches to defining complex objects, through a number of applications, including: languages defined by context-free grammars; flow charts and their interpretations; and monadic recursive program schemes. The main mathematical results concern free rational theories and quotients of rational theories. However, the main goal has been to open up what we believe to be a beautiful and powerful new approach to the syntax and semantics of complex recursive specifications.Keywords
This publication has 10 references indexed in Scilit:
- Specification techniques for data abstractionsIEEE Transactions on Software Engineering, 1975
- The algebraic theory of recursive program schemesPublished by Springer Nature ,1975
- Automata on Infinite Objects and Church’s ProblemCBMS Regional Conference Series in Mathematics, 1972
- Languages for defining sets in arbitrary algebrasPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1971
- The common algebraic structure of exit-automata and machinesComputing, 1970
- On formalised computer programsJournal of Computer and System Sciences, 1970
- Automata in general algebrasInformation and Control, 1967
- Algebraic automata and context-free setsInformation and Control, 1967
- On Ianov's Program SchemataJournal of the ACM, 1964
- FUNCTORIAL SEMANTICS OF ALGEBRAIC THEORIESProceedings of the National Academy of Sciences, 1963