A new decidable problem, with applications
- 1 September 1977
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 62-73
- https://doi.org/10.1109/sfcs.1977.2
Abstract
A number of decision problems that are unsolvable in general are solvable when restricted to systems with sufficiently simple "loop structure". Examples of such problems are the equivalence problems for flowchart schemata with nonintersecting loops and for the LOOP(l) programs of Meyer and Ritchie. We here present a theorem that gives a unifying view of the solvability of both of these problems, and also of a variety of other old and new solvable decision problems in automata theory, schematology, and logic.Keywords
This publication has 13 references indexed in Scilit:
- The equivalence problem for program schemata with nonintersecting loopsPublished by Association for Computing Machinery (ACM) ,1977
- Simple Programs Realize Exactly Presburger FormulasSIAM Journal on Computing, 1976
- A Search Technique for Clause Interconnectivity GraphsIEEE Transactions on Computers, 1976
- Refutation graphsArtificial Intelligence, 1976
- Bounded-reversal multihead finite automata languagesInformation and Control, 1974
- A note on semilinear sets and bounded-reversal multihead pushdown automataInformation Processing Letters, 1974
- Representing program schemes in logicPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1972
- The Equivalence Problem of Simple ProgramsJournal of the ACM, 1970
- The complexity of loop programsPublished by Association for Computing Machinery (ACM) ,1967
- On Context-Free LanguagesJournal of the ACM, 1966