Commutative action logic

DOI10.1093/LOGCOM/EXAC008MaRDI QIDQ6189212zbMATH OpenOpenAlexFDO

Authors Stepan Kuznetsov

Publication date 8 February 2024

Published in Journal Of Logic And Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2102.11639

Mathematics Subject Classification ID

Mathematical logic and foundations (03-XX) Computer science (68-XX)

Abstract: We prove undecidability and pinpoint the place in the arithmetical hierarchy for commutative action logic, that is, the equational theory of commutative residuated Kleene lattices (action lattices), and infinitary commutative action logic, the equational theory of *-continuous action lattices. Namely, we prove that the former is $Sigm{a}_1^0$-complete and the latter is $P{i}_1^0$-complete. Thus, the situation is the same as in the more well-studied non-commutative case. The methods used, however, are different: we encode infinite and circular computations of counter (Minsky) machines.

Cited in

(3)

• Algorithmic complexity for theories of commutative Kleene algebras
• Closure ordinal of immediate derivability operator of infinitary action logic
• Algorithmic complexity of theories with Kleene iteration

This page was built for publication: Commutative action logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6189212)