On the Complexity of Kleene Algebra with Domain

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

On the Complexity of Kleene Algebra with Domain

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

On the Complexity of Kleene Algebra with Domain

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

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

Projekt

<a href="/cs/project/GA22-16111S" target="_blank" >GA22-16111S: GRADLACT: Stupňované logiky konání</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2023

Kód důvěrnosti údajů

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

Název statě ve sborníku

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

ISBN

978-3-031-28082-5

ISSN

—

e-ISSN

—

Počet stran výsledku

16

Strana od-do

208-223

Název nakladatele

Springer

Místo vydání

Cham

Místo konání akce

Augsburg

Datum konání akce

3. 4. 2023

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000999078800013