Program equivalence and context-free grammars
- 1 October 1972
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
This note defines a new equivalence relation among systems of recursion equations and a method for assigning context-free grammars to these systems, such that (1) The new equivalence implies strong equivalence; (2) Systems are equivalent in the new sense iff their grammars generate the same language; (3) There is a nontrivial decidable class of systems whose grammars have the decidability properties of LL(k) grammars. Thus, the decidability of generative equivalence for LL(k) grammars mitigates the general undecidability of strong equivalence between arbitrary systems of recursion equations.Keywords
This publication has 9 references indexed in Scilit:
- Tree-Manipulating Systems and Church-Rosser TheoremsJournal of the ACM, 1973
- Recursive definitions of partial functions and their computationsPublished by Association for Computing Machinery (ACM) ,1972
- Translating recursion equations into flow chartsJournal of Computer and System Sciences, 1971
- DECIDABLE PROPERTIES OF MONADIC FUNCTIONAL SCHEMASPublished by Elsevier ,1971
- Properties of deterministic top-down grammarsInformation and Control, 1970
- On formalised computer programsJournal of Computer and System Sciences, 1970
- Tree-oriented proofs of some theorems on context-free and indexed languagesPublished by Association for Computing Machinery (ACM) ,1970
- Formal models for some features of programming languagesPublished by Association for Computing Machinery (ACM) ,1969
- A Basis for a Mathematical Theory of Computation)Published by Elsevier ,1963