The equational theory of relational Kleene algebra with graph loop is PSPACE-complete, and this PSPACE bound extends to top, tests, converse, and nominals, resolving the complexity of relational KAT with domain.
PDL with intersection and converse: satisfiability and infinite-state model checking
2 Pith papers cite this work, alongside 23 external citations. Polarity classification is still indexing.
2
Pith papers citing it
23
external citations · external index
fields
cs.LO 2years
2025 2representative citing papers
citing papers explorer
-
The Equational Theory of Relational Kleene Algebra with Graph Loop is PSPACE-Complete
The equational theory of relational Kleene algebra with graph loop is PSPACE-complete, and this PSPACE bound extends to top, tests, converse, and nominals, resolving the complexity of relational KAT with domain.
- Guarded Negation Transitive Closure Logic