Paper Info
Title
Recursion Schemes and Generalized Interpretations (Extended Abstract)
Abstract
This paper investigates some of the underlying axioms allowing the fixpoint-semantics approach to hold for tree-like recursion schemes. The notions of scheme and interpretation are generalized. The axioms satisfied by "algebraic theories" are shown to be adequate for the definition of the notion of an interpretation. It is also shown that in order to provide the semantics of arbitrary finite recursion schemes, rational algebraic theories are insufficient and it is necessary to introduce a new class of "recursion-closed" algebraic theories. Finally, free recursion-closed algebraic theories are shown to exist.
Year
DOI
Venue
1979
10.1007/3-540-09510-1_20
ICALP
Keywords
Field
DocType
recursion schemes,extended abstract,generalized interpretations,satisfiability
Discrete mathematics,Combinatorics,Mutual recursion,Double recursion,Recursion,Mathematics
Conference
ISBN
Citations 
PageRank 
3-540-09510-1
0
0.34
References 
Authors
1
1
Name
Order
Citations
PageRank
Jean H. Gallier1749111.86