On the Complexity of Kleene Algebra with Domain

Authors: Igor Sedlár
Publication year: 2023
Publication type: Konferenční příspěvek (mezinárodní konf.)
Periodical: Relational and Algebraic Methods in Computer Science. 20th International Conference, RAMiCS 2023 Proceedings.
Projects: GRADLACT: Graded Logics of Action
Bibliographic citation: 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 record: View online record

Abstract

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.