Levels of Undecidability in Infinitary Rewriting: Normalization and Reachability
Endrullis, Joerg · arXiv (Cornell University) · 2010
In [EGZ09] it has been shown that infinitary strong normalization (SNi) is Pi-1-1-complete. Suprisingly, it turns out that infinitary weak normalization (WNi) is a harder problem, being Pi-1-2-complete, and thereby strictly higher in the analytical hierarchy.