PSPACE-Completeness of the Equational Theory of Relational Kleene Algebra with Graph Loop
Yoshiki Nakamura · 2025
Read PSPACE-Completeness of the Equational Theory of Relational Kleene Algebra with Graph Loop by Yoshiki Nakamura (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-22930.txt.
Introduction
Yoshiki Nakamura settles the computational cost of deciding when two expressions mean the same thing in a relational algebra with a loop operator. Relational Kleene algebra models programs built from relations using composition, choice, and iteration. Its graph loop operator restricts a relation to pairs where input and output coincide, essentially testing for loops in a graph. Nakamura proves the equational theory for this system is PSPACE-complete.
The result survives adding top elements, tests, converse, and nominals to the language. It also resolves an open problem about Kleene algebra with tests: with domain, the relational equational theory is PSPACE-complete, in contrast to the ExpTime-completeness known for antidomain. The proof introduces loop-automata, finite automata on graphs that can test whether the current vertex carries a loop. Through them, the equational problem reduces in polynomial time to language inclusion for two-way alternating automata.
Catalog record
| CREATOR | Yoshiki Nakamura |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 166 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-22930
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
PSPACE-Completeness of the Equational Theory of Relational Kleene Algebra with Graph Loop Yoshiki Nakamura Abstract In this paper, we show that the equational theory of relational Kleene algebra with graph loop is PSpace -complete. Here, the graph loop is the unary operator that restricts a binary relation to the identity relation. We further show that this PSpace -completeness still holds by extending with top, tests, converse, and nominals. Notably, we also obtain that for Kleene algebra with tests (KAT), the equational theory of relational KAT with domain is PSpace -complete, whereas the equational theory of relational KAT with antidomain is ExpTime -complete. To this end, we introduce a novel automaton model on relational structures, named loop-automata . Loop-automata are obtained from non-deterministic finite string automata (NFA) by adding a transition type that tests whether the current vertex has a loop. Using this model, we give a polynomial-time reduction from the above equational theories to the language inclusion problem for 2-way alternating string automata. Institute of Science Tokyo, [email protected]://orcid.org/0000-0003-4106-0408 This work was supported by JSPS KAKENHI Grant Numbers JP21K13828 and JP25K14985. ccs Theory of computation Logic ccs Theory of computation Formal languages and automata theory keywords Kleene algebra, Graph loop, Domain † † runningtitle: PSPACE-Completeness of the Equational Theory of Loop-RKA † † runningauthor: Y. Nakamura † † copyright: Yoshiki Nakamura † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction We are interested in relational Kleene algebra (RKA), the relational model of Kleene algebra , which is an algebraic system on binary relations with the operators \{\mathsf{0},\mathsf{I},\mathbin{;},\mathbin{+},\_^{*}\} of empty relation ( \mathsf{0} ), identity relation ( \mathsf{I} ), union ( \mathbin{+} ), composition ( \mathbin{;} ), and reflexive transitive closure (Kleene star) ( \_^{*} ). RKA arises in various research areas, such as database theory [ calvaneseRewritingRegularExpressions1999 ] (e.g., regular path queries (RPQs)) and program verification [ kozenKleeneAlgebraTests1996 ] (e.g., relational Kleene algebra with tests (relational KAT, RKAT)). From the completeness theorem [ kozenCompletenessTheoremKleene1991 ] of Kleene algebra, the equational theory of RKA coincides the language equivalence problem of regular expressions, and hence it is PSpace -complete [ meyerEquivalenceProblemRegular1972 ] . The equational theory is still PSpace -complete even if we extend the system with several operators, such as tests [ kozenKleeneAlgebraTests1996 ] , converse ( \_^{\smile} ) [ brunetKleeneAlgebraConverse2014 ] , top ( \top ) [ nakamuraExistentialCalculiRelations2023 , pousCompletenessTheoremsKleene2024 ] , nominals [ nakamuraDerivativesGraphsPositive2025 ] , and all the combination of them [ nakamuraDerivativesGraphsPositive2025 ] . In contrast, for instance, the equational theory becomes ExpSpace -hard [ nakamuraPartialDerivativesGraphs2017 , brunetPetriAutomata2017 ] for RKA with intersection ( \cap ) (a.k.a. relational Kleene lattice [ andrekaEquationalTheoryKleene2011 ] ). Our natural question is which extensions of RKA keep the PSpace -completeness of the equational theory. Contribution In this paper, we study RKA with graph loop (loop-RKA). Here, we use \_^{\circlearrowleft} to denote graph loop (strong loop predicate) [ daneckiNondeterministicPropositionalDynamic1984 , nakamuraUndecidabilityPositiveCalculus2024 ] , which is the unary operator of restricting a given binary relation R on X to the identify relation: R^{\circlearrowleft}\coloneq R\cap\triangle_{X} . Our main contribution is to prove the following, which was left open by Nakamura [ nakamuraDerivativesGraphsPositive2025 , §8] : Theorem 1 . The equational theory is PSpace -complete for loop-RKA. To the best of our knowledge, it was previously only known that it is PSpace -hard (as RKA terms are a syntax fragment of loop-RKA terms) and in ExpTime [ daneckiNondeterministicPropositionalDynamic1984 , gollerPDLIntersectionConverse2009 ] (by a canonical embedding (see, e.g., [ fischerPropositionalDynamicLogic1979 ] ) to loop-PDL [ daneckiPropositionalDynamicLogic1984 ] ). Moreover, by adapting the operator encodings from [ nakamuraDerivativesGraphsPositive2025 , §6] , the PSpace upper bound still holds when we extend loop-RKA with several additional operators ( ), as follows: Theorem 2 . ] \theoremKLextrasPSPACEcomplete The equational theory is PSpace -complete for loop-RKA with top, tests, converse, and nominals. \theoremKLextrasPSPACEcomplete As an application, we can encode domain ( \_^{\mathsf{d}} ) and range ( \_^{\mathsf{r}} ), respectively, as follows: \displaystyle t^{\mathsf{d}}~ \displaystyle\coloneq~(t\mathbin{;}\top)^{\circlearrowleft}, \displaystyle t^{\mathsf{r}}~ \displaystyle\coloneq~(\top\mathbin{;}t)^{\circlearrowleft}~(\text{or,}~t^{\mathsf{r}}~\coloneq~(t^{\smile})^{\mathsf{d}}). (1) Thus, our result also implies the PSpace upper bounds for RKAT with domain [ desharnaisInternalAxiomsDomain2011 , mcleanFreeKleeneAlgebras2020 , sedlarKleeneAlgebraDynamic2023 ] and hence, for RKA with domain 1 1 1 RKA with domain is a strictly less expressive fragment of RKA with tests and antidomain. The latter system is often also called (relational) “Kleene algebra with domain” [ desharnaisKleeneAlgebraDomain2006 ] . , 2 2 2 [ reutterContainmentNestedRegular2013 , unpublised manuscript] claims that the containment problem of nested regular expressions [ perezNSPARQLNavigationalLanguage2008 ] (i.e., the inequational theory of RKA with domain and converse) is in PSpace , which also implies the PSpace upper bound of the equational theory of RKA with domain. , which were left open, e.g., by Mclean [ mcleanFreeKleeneAlgebras2020 , Problem 7.3] and Sedlár [ sedlarKleeneAlgebraDynamic2023 , p. 16] . Corollary 1 . The equational theory is PSpace -complete for RKAT with domain and range (resp. RKA with domain and range, RKAT with domain, and RKA with domain). Hence, while the equational theory is ExpTime -hard [ sedlarComplexityKleeneAlgebra2023 ] for RKA with antidomain ( \_^{\mathsf{a}} ) [ desharnaisKleeneAlgebraDomain2006 , desharnaisInternalAxiomsDomain2011 ] , extending domain keeps the PSpace upper bound. To prove Theorems 1 and 2 , we give a reduction from the equational theory into the language inclusion problem of 2-way alternating string automata (2AFAs) [ geffertTransformingTwoWayAlternating2014 , kapoutsisAlternationTwowayFinite2021 ] . We first observe that the equational theory has the linearly bounded pathwidth model property ( Proposition 3.5 ) [ nakamuraDerivativesGraphsPositive2025 , Prop. 2.10] : if there is some counter model for an equation (i.e., a structure refutating the equation), then there is also some counter model with pathwidth linear in the size of the equation. By viewing (width-bounded) path decompositions as strings, we can enumerate all possible structures of bounded pathwidth, using string automata. This baseline approach itself is the same approach as in [ nakamuraDerivativesGraphsPositive2025 ] for RKA with intersection. However, it is not clear how to obtain the PSpace upper bound when the intersection width ( 3 ) is not fixed [ nakamuraDerivativesGraphsPositive2025 , p. 46–47] . To obtain a PSpace -algorithm, we introduce a new automaton model, called loop-automata ( Section 4 ) as an alternative expression of the relational semantics of RKA with graph loop. Loop-automata are obtained from non-deterministic automata by extending a new transition for testing whether there exists a loop in the current vertex. From loop-automata, we build a 2-way alternating string automaton (2AFA) [ geffertTransformingTwoWayAlternating2014 , kapoutsisAlternationTwowayFinite2021 ] , where each string express a path decomposition. Using this construction, we give a reduction from the equational theory of RKA with graph loop into the language inclusion problem of 2AFAs. The main technical differences from [ nakamuraDerivativesGraphsPositive2025 ] are summarized as the following two: • Using loop-automata instead of derivatives on graphs, we consider only (nested) path graphs (they are sufficient for RKA with graph loop) instead of full series-parallel graphs . This significantly simplifies our algorithm compared to that of [ nakamuraDerivativesGraphsPositive2025 ] and eases us