The Equational Theory of Relational Kleene Algebra with Graph Loop is PSPACE-Complete
This paper establishes that the equational theory of relational Kleene algebra extended with the graph loop operator (and further with top, tests, converse, and nominals) is PSPACE-complete by introducing a novel loop-automaton model to reduce these theories to the language inclusion problem for 2-way alternating automata, thereby resolving an open problem regarding the complexity of relational KAT with domain.
Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer
Imagine you are trying to teach a robot how to navigate a maze, but instead of giving it a map, you are writing a set of rules using a special language of logic. This language, called "Relational Kleene Algebra," is like a toolkit for describing how things connect. It has tools for saying "do this, then that" (composition), "choose this or that" (union), and "keep doing this forever" (loops). For decades, computer scientists have known that if you just use these basic tools, figuring out whether two different rulebooks mean the exact same thing is a very hard puzzle, but one that a supercomputer can solve in a reasonable amount of time.
However, real-world problems often need more specific tools. What if you want to check if a robot is standing on a "loop" (a spot where it can move to itself)? Or what if you want to check if a robot is in a specific "test" zone? Adding these extra tools makes the puzzle much harder. In fact, for some versions of these rules, the puzzle becomes so difficult that it might take longer than the age of the universe for a computer to solve it. The big question in this field has been: if we add the "loop" tool, does the puzzle stay solvable in a reasonable time, or does it explode into an impossible mess?
This paper dives into that exact question. The author, Yoshiki Nakamura, investigates a specific version of this logic system that includes a "graph loop" operator—a tool that checks if a connection leads back to the same spot. The paper proves that even with this tricky loop tool added, the puzzle of checking if two rulebooks are equivalent remains solvable within a reasonable timeframe (specifically, it is "PSPACE-complete," which means it's as hard as the hardest problems a computer can solve with a standard amount of memory, but not harder).
To solve this, the author invents a new kind of "machine" called a loop-automaton. Think of a standard robot navigating a maze as a "nondeterministic finite automaton"—it can guess which path to take. The new loop-automaton is like a robot with a special superpower: at any moment, it can pause and ask, "Am I standing on a spot that has a loop?" If the answer is yes, it can take a special shortcut. The paper shows that by translating the complex logic rules into the behavior of these super-powered robots, we can check if two rulebooks are equivalent by seeing if one robot's path is always covered by the other's.
The author doesn't stop there. They show that this method works even if you add more fancy tools to the robot's toolkit, like "tests" (checking if a condition is true), "converse" (running the rules backward), and "nominals" (naming specific spots). Surprisingly, even with all these extra features, the difficulty of the puzzle doesn't jump to the "impossible" level; it stays in the "hard but solvable" zone.
This is a big deal because it settles a debate that had been open for a while. Previously, scientists knew that adding a different tool called "antidomain" made the puzzle much harder (taking exponential time), but they weren't sure about "domain" or "loop" tools. This paper proves that adding the loop tool (and even combining it with domain and range checks) keeps the problem manageable. The author achieves this by creating a clever reduction: they turn the abstract logic problem into a problem about whether one robot's set of possible paths is included in another's, a problem that computers are already known to handle efficiently.
In short, the paper confirms that while logic puzzles with loops are tricky, they aren't hopeless. By building a new type of "loop-checking" robot and translating the math into a language these robots understand, the author proves that we can still verify these complex systems without needing infinite computing power. This gives computer scientists and engineers confidence that they can build more sophisticated verification tools for software and databases without hitting a wall of complexity.
Drowning in papers in your field?
Get daily digests of the most novel papers matching your research keywords — with technical summaries, in your language.