The Equational Theory of Relational Kleene Algebra with Graph Loop is PSPACE-Complete
This resolves a long-standing open problem in algebraic logic and automata theory, providing tight complexity bounds for equational theories of Kleene algebras with domain and related operators.
The paper proves that the equational theory of relational Kleene algebra with the graph loop operator is PSPACE-complete, and resolves an open problem by showing that the equational theory of relational KAT with domain is PSPACE-complete, not ExpTime-complete as previously thought.
In this paper, we show that the equational theory of relational Kleene algebra with the \emph{graph loop} operator (a.k.a.~\emph{fixset}) is \textsc{PSpace}-complete. Here, the graph loop is the unary operator that restricts a binary relation to the identity relation. We further show that this \textsc{PSpace}-completeness still holds by extending the terms with top, tests, converse, and nominals, over relational models. Notably, for Kleene algebra with tests (KAT), while the equational theory of relational KAT with antidomain is \textsc{ExpTime}-complete, we show that the equational theory of relational KAT with domain is \textsc{PSpace}-complete, thereby resolving a problem left open in previous works. To this end, we introduce a novel automaton model on relational structures (graphs), called \emph{loop-automata}. Loop-automata extend nondeterministic finite automata with a transition type that tests whether the current vertex has a loop. Using this model, we can give a polynomial-time reduction from the equational theories above to the language inclusion problem for 2-way alternating automata.