On Model-Checking Higher-Order Effectful Programs
summary
Paper shows higher-order effectful programs map to ordinary higher-order recursion schemes via a CPS transformation and recovers classic model-checking decidability (K‑EXPTIME-complete by order) for EPCF when observations reduce to MSO. It proves MSO-parametric on O decidable for effects like global store, exceptions, nondeterminism and IO, but shows probabilistic choice and general effect handlers make even reachability undecidable by simulating natural numbers and equality. Decidability returns under the restricted generic effect handlers discipline (continuation passed linearly).
AI-written summary · about