Levels of Undecidability in Infinitary Rewriting: Normalization and Reachability
classification
💻 cs.LO
cs.CC
keywords
infinitarynormalizationanalyticalbeenegz09harderhierarchyhigher
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.