Cover Image

Kleene algebra with commutativity conditions is undecidable

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	de Amorim, Arthur Azevedo, Zhang, Cheng, Gaboardi, Marco
Format:	Preprint
Published:	2024
Subjects:	Logic Computational Complexity Computation and Language Logic in Computer Science Programming Languages
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Domain Reasoning in TopKAT
by: Zhang, Cheng, et al.
Published: (2024)

Non-commutative linear logic fragments with sub-context-free complexity
by: Nishimiya, Yusaku, et al.
Published: (2025)

Program Synthesis is $Σ_3^0$-Complete
by: Kim, Jinwoo
Published: (2024)

Reasonable Space for the $λ$-Calculus, Logarithmically
by: Accattoli, Beniamino, et al.
Published: (2022)

LFPL: Revisited and Mechanized
by: Glover, Nathaniel, et al.
Published: (2026)

Complete and tractable machine-independent characterizations of second-order polytime
by: Hainry, Emmanuel, et al.
Published: (2022)

Reversible Computation with Stacks and "Reversible Management of Failures"
by: Palazzo, Matteo, et al.
Published: (2025)

Outrunning Big KATs: Efficient Decision Procedures for Variants of GKAT
by: Zhang, Cheng, et al.
Published: (2026)

Denotational Foundations for Expected Cost Analysis
by: de Amorim, Pedro H. Azevedo
Published: (2024)

From Time to Space: The Impact of Linearity in Higher-Order Datalog
by: Charalambidis, Angelos, et al.
Published: (2026)

The Power of Negation in Higher-Order Datalog
by: Charalambidis, Angelos, et al.
Published: (2025)

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

Counting and Sampling Traces in Regular Languages
by: de Colnet, Alexis, et al.
Published: (2025)

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)

Flexible Type-Based Resource Estimation in Quantum Circuit Description Languages
by: Colledan, Andrea, et al.
Published: (2024)

Cypher is Turing-Complete: A Formal Proof via 2-Counter Machine Simulation
by: Halftermeyer, Pierre
Published: (2026)

Towards a Characterization of Two-way Bijections in a Reversible Computational Model
by: Palazzo, Matteo, et al.
Published: (2025)

A faster FPRAS for #NFA
by: Meel, Kuldeep S., et al.
Published: (2023)

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

Coinductive Proofs for Temporal Hyperliveness
by: Correnson, Arthur, et al.
Published: (2025)

Token-Sensitive Enclosure Semantics for Measurement-Bearing Expressions
by: Hulak, David B., et al.
Published: (2026)

An Intermediate Program Representation for Optimizing Stream-Based Languages
by: Baumeister, Jan, et al.
Published: (2025)

The Expressive Power of Transformers with Chain of Thought
by: Merrill, William, et al.
Published: (2023)

2-ASP(Q) programs with weak constraints: Complexity and efficient implementation
by: Cuteri, Andrea, et al.
Published: (2026)

Cryptis: Cryptographic Reasoning in Separation Logic
by: de Amorim, Arthur Azevedo, et al.
Published: (2025)

The Proof Analysis Problem
by: Arteche, Noel, et al.
Published: (2025)

A Probabilistic Choreography Language for PRISM
by: Carbone, Marco, et al.
Published: (2025)

Verifying Functional Correctness Properties At the Level of Java Bytecode
by: Paganoni, Marco, et al.
Published: (2024)

Reasoning About Exceptional Behavior At the Level of Java Bytecode
by: Paganoni, Marco, et al.
Published: (2024)

Hennessy-Milner Logic in CSLib, the Lean Computer Science Library
by: Montesi, Fabrizio, et al.
Published: (2026)

Symmetric Proofs of Parameterized Programs
by: Cheng, Ruotong, et al.
Published: (2026)

Complete Local Reasoning About Parameterized Programs Over Topologies
by: Cheng, Ruotong, et al.
Published: (2026)

Products of Recursive Programs for Hypersafety Verification (Extended Version)
by: Cheng, Ruotong, et al.
Published: (2025)

Frex: dependently-typed algebraic simplification
by: Allais, Guillaume, et al.
Published: (2023)

Functional variant of Polynomial Analogue of Gandy's Fixed Point Theorem
by: Nechesov, Andrey
Published: (2024)

Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets
by: Atserias, Albert, et al.
Published: (2024)

$Π_{2}^{P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem
by: Zhuk, Dmitriy
Published: (2024)

Proof Complexity of Linear Logics
by: Tabatabai, Amirhossein Akbar, et al.
Published: (2026)

An order out of nowhere: a new algorithm for infinite-domain CSPs
by: Mottet, Antoine, et al.
Published: (2023)

Proof complexity of positive branching programs
by: Das, Anupam, et al.
Published: (2021)