IDEALIZED ALGOL WITH GROUND RECURSION

ABSTRACT. WE PROVE THAT OBSERVATIONAL EQUIVALENCE OF IA3 + Y0 (3RD-ORDER IDEALIZED ALGOL WITH 0TH-ORDER RECURSION) IS EQUIVALENT TO THE DPDA EQUIVALENCE PROBLEM, AND HENCE DECIDABLE. THIS COMPLETES THE CLASSI-CATION OF DECIDABLE FRAGMENTS OF IDEALIZED ALGOL. WE ALSO PROVE THAT OB-SERVATIONAL APPROXIMATION OF IA1 + Y0 IS UNDECIDABLE BY REDUCING THE DPDA CONTAINMENT PROBLEM TO IT.