On the Complexity of Kleene Algebra with Domain

Autoři: Mgr. Igor Sedlár, Ph.D.
Rok vydání: 2023
Typ publikace: Konferenční příspěvek (mezinárodní konf.)
Periodikum: Relational and Algebraic Methods in Computer Science. 20th International Conference, RAMiCS 2023 Proceedings.
Projekty: GRADLACT: Stupňované logiky konání
Bibliografická citace: SEDLÁR, Igor. On the Complexity of Kleene Algebra with Domain. In: GLÜCK, R., SANTOCANALE, L., WINTER, M., eds. Relational and Algebraic Methods in Computer Science. 20th International Conference, RAMiCS 2023 Proceedings. Cham: Springer, 2023, S. 208-223. Lecture Notes in Computer Science, 13896. ISBN 978-3-031-28082-5
Dostupné z: doi:10.1007/978-3-031-28083-2_13.
DOI: 10.1007/978-3-031-28083-2_13
ID: 571145
Online záznam: Zobrazit online záznam

Abstrakt

We prove that the equational theory of Kleene algebra with domain is EXPTIME-complete. Our proof makes essential use of Hollenberg’s equational axiomatization of program equations valid in relational test algebra. We also show that the equational theory of Kleene algebra with domain coincides with the equational theory of *-continuous Kleene algebra with domain.