|
 ABSTRACT
This is the introductory paper in a series devoted to a general algebraic theory of “recursive definitions” and “recursive languages”. In this paper we present the fundamental concepts and theorems concerning the basic structure (basic syntax), the semantics and the combination and manipulation of “recursive definitions” and the closure properties of “recursive languages”. The development is carried out within the framework of category theory and lattice theory. To illustrate the generality of the approach and our results we show how they apply directly to the specific examples of “recursive languages” of (generalized) context-free grammars, Turing machines, and flowcharts.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
Tarski, Alfred, "A Lattice-Theoretical Fixpoint Theorem and its Applications", Pacific J. Math. 5 (1955) 285-309.
|
| |
2
|
Scott, Dana, "The Lattice of Flow Diagrams", to appear in Semantics of Algorithmic Languages, Erwin Engeler (editor) Spring Lecture Notes Series, Springer-Verlag, Heidelberg.
|
| |
3
|
Park, David, "Fixpoint Induction and roofs of Program Properties", Machine Intelligence 5, American Elsevier Publ. Co., Inc., New York, (1970) 59-78.
|
| |
4
|
Eilenberg, Samuel and Wright, Jesse B., "Automata in General Algebras", Information and Control, 11, No. 4, (1967) 452-470.
|
| |
5
|
Elgot, Calvin, "Algebraic Theories and Program Schemes", to appear in Semantics of Algorithmic Languages, Erwin Engeler (editor) Spring Lecture Notes Series, Springer-Verlag, Heidelberg.
|
| |
6
|
Grothendieck, A., "Sur quelques points d'Algebre Homologique", Tohoku Math Journal, 9 (1957) 119-221.
|
| |
7
|
Chomsky, N., "On Certain Formal Properties of Grammars", Information and Control 2 (1959) 137-167
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
F.3