Expressive power of digraph solvability
Expressive power of digraph solvability
M. Bezem,C. Grabmayer,M. Walicki
2010 · DOI: 10.1016/j.apal.2011.08.004
Annals of Pure and Applied Logic · 28 Citations
TLDR
It is proved that solvability for recursive dags and digraphs is Σ11-complete, which implies that satisfiability for recursive theories of infinitary propositional logic is also Σ12 -complete, and a new equivalent of the axiom of choice is formulated.