On the complexity of reasoning in Kleene algebra

DOI10.1006/inco.2001.2960zbMath1096.03077OpenAlexW2142072439MaRDI QIDQ2506487

Dexter Kozen

Publication date: 10 October 2006

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1813/7279

Mathematics Subject Classification ID

Logic in computer science (03B70) Complexity of computation (including implicit computational complexity) (03D15) Other algebras related to logic (03G25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Adaptive logics using the minimal abnormality strategy are \(\Pi^1_1\)-complex, Complexity of a fragment of infinitary action logic with exponential via non-well-founded proofs, Override and update, On tools for completeness of Kleene algebra with hypotheses, A restricted fragment of the Lambek calculus with iteration and intersection operations, Infinitary action logic: complexity, models and grammars, Kleene star, subexponentials without contraction, and infinite computations, The multiplicative-additive Lambek calculus with subexponential and bracket modalities, Infinitary action logic with exponentiation, KAT-ML: an interactive theorem prover for Kleene algebra with tests, Equational theories for automata

Cites Work

• On the decidability of some problems about rational subsets of free partially commutative monoids
• Complete systems of \(\mathcal B\)-rational identities
• A completeness theorem for Kleene algebras and the algebra of regular events
• The complexity of the word problems for commutative semigroups and polynomial ideals
• Une remarque sur les systèmes complets d'identités rationnelles
• A Semiring on Convex Polygons and Zero-Sum Cycle Problems
• Equational axioms for regular sets
• Two Complete Axiom Systems for the Algebra of Regular Events
• On the Forms of the Predicates in the Theory of Constructive Ordinals
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item