Geodesic
Algorithmic complexity for theories of commutative Kleene algebras
Izvestiya. Mathematics , Tome 88 (2024) no. 2, pp. 236-269

Voir la notice de l'article provenant de la source Math-Net.Ru

Kleene algebras are structures with addition, multiplication and constants $0$ and $1$, which form an idempotent semiring, and the Kleene iteration operation. In the particular case of $*$-continuous Kleene algebras, Kleene iteration is defined, in an infinitary way, as the supremum of powers of an element. We obtain results on algorithmic complexity for Horn theories (semantic entailment from finite sets of hypotheses) of commutative $*$-continuous Kleene algebras. Namely, $\Pi_1^1$-completeness for the Horn theory and $\Pi^0_2$-completeness for its fragment, where iteration cannot be used in hypotheses, is proved. These results are commutative counterparts of the corresponding theorems of D. Kozen (2002) for the general (non-commutative) case. Several accompanying results are also obtained.
Keywords: Kleene algebras, algorithmic complexity, infinitary logic. 
@article{IM2_2024_88_2_a3,
     author = {S. L. Kuznetsov},
     title = {Algorithmic complexity for theories of commutative {Kleene} algebras},
     journal = {Izvestiya. Mathematics },
     pages = {236--269},
     publisher = {mathdoc},
     volume = {88},
     number = {2},
     year = {2024},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IM2_2024_88_2_a3/}
}
TY  - JOUR
AU  - S. L. Kuznetsov
TI  - Algorithmic complexity for theories of commutative Kleene algebras
JO  - Izvestiya. Mathematics 
PY  - 2024
SP  - 236
EP  - 269
VL  - 88
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IM2_2024_88_2_a3/
LA  - en
ID  - IM2_2024_88_2_a3
ER  - 
%0 Journal Article
%A S. L. Kuznetsov
%T Algorithmic complexity for theories of commutative Kleene algebras
%J Izvestiya. Mathematics 
%D 2024
%P 236-269
%V 88
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IM2_2024_88_2_a3/
%G en
%F IM2_2024_88_2_a3
S. L. Kuznetsov. Algorithmic complexity for theories of commutative Kleene algebras. Izvestiya. Mathematics , Tome 88 (2024) no. 2, pp. 236-269. http://geodesic.mathdoc.fr/item/IM2_2024_88_2_a3/