Algebraic families of interpretations
Authors:
- Bruno CourcelleBCBruno Courcelle
- Maurice NivatMNMaurice Nivat
- 1 October 1976
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 137-146
Abstract
To each family C of interpretations corresponds an equivalence relation among program schemes, namely the equivalence of the program schemes for all interpretation of C. A family C is algebraic if any two programs are C-equivalent iff every partial finite computation of one of them is C-equivalent to some partial finite computation of the other. Our main theorem states that a family C is algebraic iff it is represented with respect to the equivalence of programs by a single interpretation (a C-Herbrand interpretation) which is algebraic (in Scott's sense, roughly speaking). We give examples of algebraic and non algebraic families.Keywords
This publication has 4 references indexed in Scilit: