Kleene algebra with commutativity conditions is undecidable

• URL: http://arxiv.org/abs/2411.15979v1
• Date: Sun, 24 Nov 2024 20:44:27 GMT
• Title: Kleene algebra with commutativity conditions is undecidable
• Abstract summary: We prove that the equational theory of Kleene algebra with commutativity conditions on primitives is undecidable. Our results hold even for weaker theories that do not support the induction axioms of Kleene algebra.
• Score: 12.189056858192778
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We prove that the equational theory of Kleene algebra with commutativity conditions on primitives (or atomic terms) is undecidable, thereby settling a longstanding open question in the theory of Kleene algebra. While this question has also been recently solved independently by Kuznetsov, our results hold even for weaker theories that do not support the induction axioms of Kleene algebra.

Related papers

• Revisiting the operator extension of strong subadditivity [44.99833362998488]
  We give a new proof of the operator extension of the strong subadditivity of von Neumann entropy $rho_AB otimes sigma_C-1 leq rho_A otimes sigma_BC-1$ by identifying the mathematical structure behind it as Connes' theory of spatial derivatives.
  arXiv  Detail & Related papers  (2025-07-30T14:18:43Z)
• Self-distributive structures, braces & the Yang-Baxter equation [0.0]
  We recall certain structures called shelves, racks and quandles.<n>These objects satisfy a self-distributivity condition and lead to solutions of the Yang-Baxter equation.<n>We show that these are quasi-triangular Hopf algebras and we derive the universal set-theoretic Drinfel'd twist.
  arXiv  Detail & Related papers  (2024-09-30T16:40:41Z)
• Machine Learning of the Prime Distribution [49.84018914962972]
  We provide a theoretical argument explaining the experimental observations of Yang-Hui He about the learnability of primes. We also posit that the ErdHos-Kac law would very unlikely be discovered by current machine learning techniques.
  arXiv  Detail & Related papers  (2024-03-19T09:47:54Z)
• Logical Characterization of Contextual Hidden-Variable Theories based on Quantum Set Theory [0.0]
  We show that a set theoretical universe is associated with a beable subalgebra if and only if it is ZFC-satisfiable. We show that there is a unique maximal ZFC-satisfiable subuniverse "implicitly definable"
  arXiv  Detail & Related papers  (2023-11-15T11:39:43Z)
• An algebraic formulation of nonassociative quantum mechanics [0.0]
  We develop a version of quantum mechanics that can handle nonassociative algebras of observables. Our approach is naturally probabilistic and is based on using the universal enveloping algebra of a general nonassociative algebra.
  arXiv  Detail & Related papers  (2023-11-07T01:36:23Z)
• Connecting classical finite exchangeability to quantum theory [69.62715388742298]
  Exchangeability is a fundamental concept in probability theory and statistics. We show how a de Finetti-like representation theorem for finitely exchangeable sequences requires a mathematical representation which is formally equivalent to quantum theory.
  arXiv  Detail & Related papers  (2023-06-06T17:15:19Z)
• Supersymmetric Quantum Mechanics, multiphoton algebras and coherent states [0.0]
  The algebras are generated by the multiphoton and creation operators, as well as by Hamiltonians which are functions of an appropriate number operator. The Barut-Girardello coherent states, which are annihilations of the operator, are obtained and their uncertainty relations are explored.
  arXiv  Detail & Related papers  (2023-04-11T19:18:43Z)
• Negations and Meets in Topos Quantum Theory [0.0]
  The daseinisation is a mapping from an orthomodular lattice in ordinary quantum theory into a Heyting algebra in topos quantum theory. We investigate the conditions under which negations and meets are preserved by daseinisation.
  arXiv  Detail & Related papers  (2021-11-30T09:16:54Z)
• Annihilating Entanglement Between Cones [77.34726150561087]
  We show that Lorentz cones are the only cones with a symmetric base for which a certain stronger version of the resilience property is satisfied. Our proof exploits the symmetries of the Lorentz cones and applies two constructions resembling protocols for entanglement distillation.
  arXiv  Detail & Related papers  (2021-10-22T15:02:39Z)
• Some Hoeffding- and Bernstein-type Concentration Inequalities [47.24550702683417]
  We prove concentration inequalities for functions of independent random variables under sub-gaussian and sub-exponential conditions. The utility of the inequalities is demonstrated by an extension of the now classical method of Rademacher complexities to Lipschitz function classes and unbounded sub-exponential distribution.
  arXiv  Detail & Related papers  (2021-02-11T23:09:13Z)
• Topological Quantum Gravity of the Ricci Flow [62.997667081978825]
  We present a family of topological quantum gravity theories associated with the geometric theory of the Ricci flow. First, we use BRST quantization to construct a "primitive" topological Lifshitz-type theory for only the spatial metric. We extend the primitive theory by gauging foliation-preserving spacetime symmetries.
  arXiv  Detail & Related papers  (2020-10-29T06:15:30Z)
• A criterion to characterize interacting theories in the Wightman framework [0.0]
  We propose a criterion to characterize interacting theories in a suitable Wightman framework of quantum field theories. We conjecture that it characterizes either unstable (composite) particles or the charge-carrying particles, which become infraparticles in the presence of massless particles.
  arXiv  Detail & Related papers  (2020-02-20T09:52:49Z)
• A refinement of Reznick's Positivstellensatz with applications to quantum information theory [72.8349503901712]
  In Hilbert's 17th problem Artin showed that any positive definite in several variables can be written as the quotient of two sums of squares. Reznick showed that the denominator in Artin's result can always be chosen as an $N$-th power of the squared norm of the variables.
  arXiv  Detail & Related papers  (2019-09-04T11:46:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.