Capturing Bisimulation-Invariant Exponential-Time Complexity Classes

Florian Bruse, David Kronenberger, Martin Lange

Otto's Theorem characterises the bisimulation-invariant PTIME queries over graphs as exactly those that can be formulated in the polyadic mu-calculus, hinging on the Immerman-Vardi…