Cover Image

The Equational Theory of Relational Kleene Algebra with Graph Loop is PSPACE-Complete

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Nakamura, Yoshiki
Format:	Preprint
Published:	2025
Subjects:	Logic in Computer Science
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Words-to-Letters Valuations for Language Kleene Algebras with Variable and Constant Complements
by: Nakamura, Yoshiki, et al.
Published: (2024)

On Tools for Completeness of Kleene Algebra with Hypotheses
by: Pous, Damien, et al.
Published: (2022)

Completeness of Finitely Weighted Kleene Algebra With Tests
by: Sedlár, Igor
Published: (2024)

Undecidability of the Emptiness Problem of Deterministic Propositional While Programs with Graph Loop: Hypothesis Elimination Using Loops
by: Nakamura, Yoshiki
Published: (2025)

Paraconsistent Relations as a Variant of Kleene Algebras
by: Cunha, Juliana, et al.
Published: (2025)

Completions of Kleene's second model
by: Terwijn, Sebastiaan A.
Published: (2023)

Derivatives on Graphs for the Positive Calculus of Relations with Transitive Closure
by: Nakamura, Yoshiki
Published: (2024)

Morita Rigidity for Kleene Algebras
by: Serafin, Luke
Published: (2025)

A Complete Inference System for Skip-free Guarded Kleene Algebra with Tests
by: Kappé, Tobias, et al.
Published: (2023)

Existential Calculi of Relations with Transitive Closure: Complexity and Edge Saturations
by: Nakamura, Yoshiki
Published: (2023)

On the Finite Variable-Occurrence Fragment of the Calculus of Relations with Bounded Dot-Dagger Alternation
by: Nakamura, Yoshiki
Published: (2023)

Completeness of Relational Algebra via Cylindric Algebra
by: Laštovička, Jan
Published: (2026)

Note on a Translation from First-Order Logic into the Calculus of Relations Preserving Validity and Finite Validity
by: Nakamura, Yoshiki
Published: (2023)

An Elementary Proof of the FMP for Kleene Algebra
by: Kappé, Tobias
Published: (2022)

A Complete Propositional Dynamic Logic for Regular Expressions with Lookahead
by: Nakamura, Yoshiki
Published: (2026)

A cyclic proof system for Guarded Kleene Algebra with Tests (full version)
by: Rooduijn, Jan, et al.
Published: (2024)

Kleene algebra with commutativity conditions is undecidable
by: de Amorim, Arthur Azevedo, et al.
Published: (2024)

Deciding Equations in the Time Warp Algebra
by: van Gool, Sam, et al.
Published: (2023)

Rings and Boolean Algebras as Algebraic Theories
by: De Faveri, Arturo
Published: (2025)

Verifying Quantized Graph Neural Networks is PSPACE-complete
by: Sälzer, Marco, et al.
Published: (2025)

The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete)
by: Daviaud, Laure, et al.
Published: (2023)

A Complete Finite Axiomatisation of the Equational Theory of Common Meadows
by: Bergstra, Jan A, et al.
Published: (2023)

Finite Hilbert systems for Weak Kleene logics
by: Greati, Vitor, et al.
Published: (2024)

A Taxonomy of Hoare-Like Logics: Towards a Holistic View using Predicate Transformers and Kleene Algebras with Top and Tests
by: Verscht, Lena, et al.
Published: (2024)

A PSPACE Algorithm for Almost-Sure Rabin Objectives in Multi-Environment MDPs
by: Suilen, Marnix, et al.
Published: (2024)

Towards Practical Zero-Knowledge Proof for PSPACE
by: Karthikeyan, Ashwin, et al.
Published: (2025)

The Relational Quotient Completion
by: Dagnino, Francesco, et al.
Published: (2024)

Complete and Terminating Tableau Calculus for Undirected Graph
by: Nishimura, Yuki, et al.
Published: (2024)

THEIA: Learning Complete Kleene Three-Valued Logic in a Pure-Neural Modular Architecture
by: Li, Augustus Haoyang
Published: (2026)

Guarded Negation Transitive Closure Logic
by: Figueira, Diego, et al.
Published: (2025)

Cardinality and Representation of Stone Relation Algebras
by: Furusawa, Hitoshi, et al.
Published: (2023)

A General Completeness Theorem for Skip-free Star Algebras
by: Kappé, Tobias, et al.
Published: (2025)

A Cut-free, Sound and Complete Russellian Theory of Definite Descriptions
by: Indrzejczak, Andrzej, et al.
Published: (2024)

Compact Quantitative Theories of Convex Algebras
by: Mio, Matteo
Published: (2025)

On the Relative Completeness of Satisfaction-based Probabilistic Hoare Logic With While Loop
by: Sun, Xin, et al.
Published: (2024)

TREBL -- A Relative Complete Temporal Event-B Logic. Part I: Theory
by: Schewe, Klaus-Dieter, et al.
Published: (2025)

A Decision Procedure for Probabilistic Kleene Algebra with Angelic Nondeterminism
by: Ong, Shawn, et al.
Published: (2025)

The Pebble-Relation Comonad in Finite Model Theory
by: Montacute, Yoàv, et al.
Published: (2021)

A Complete Equational Theory for Real-Clifford+CH Quantum Circuits
by: Clément, Alexandre
Published: (2026)

Relative Completeness of Incorrectness Separation Logic
by: Lee, Yeonseok, et al.
Published: (2025)