Simple Programs on Strings and Their Decision Problems
Giorgio Ausiello · eCommons (Cornell University) · 1975
Classes of simple programs operating on srings are considered. Their power as acceptors and their power as generation devices are compared and consequences on upper bounds and lower bounds for several decision problems are derived. It is shown that even for such a small class of programs some problems are undecidable.