On the Complexity of Kleene Algebra with Domain

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F23%3A00571145" target="_blank" >RIV/67985807:_____/23:00571145 - isvavai.cz</a>

Result on the web

<a href="https://dx.doi.org/10.1007/978-3-031-28083-2_13" target="_blank" >https://dx.doi.org/10.1007/978-3-031-28083-2_13</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-031-28083-2_13" target="_blank" >10.1007/978-3-031-28083-2_13</a>

Result language

angličtina

Original language name

On the Complexity of Kleene Algebra with Domain

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GA22-16111S" target="_blank" >GA22-16111S: GRADLACT: Graded Logics of Action</a><br>

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2023

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Relational and Algebraic Methods in Computer Science. 20th International Conference, RAMiCS 2023 Proceedings.

ISBN

978-3-031-28082-5

ISSN

—

e-ISSN

—

Number of pages

16

Pages from-to

208-223

Publisher name

Springer

Place of publication

Cham

Event location

Augsburg

Event date

Apr 3, 2023

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

000999078800013