Conference Paper/Proceeding/Abstract 379 views 85 downloads
Kleene Algebra with Hypotheses
Lecture Notes in Computer Science, Volume: 11425, Pages: 207 - 223
Swansea University Author:
Cécilia Pradic
-
PDF | Version of Record
© The Author(s) 2019. This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License
Download (384.4KB)
DOI (Published version): 10.1007/978-3-030-17127-8_12
Abstract
We study the Horn theories of Kleene algebras and star continuous Kleene algebras, from the complexity point of view. While their equational theories coincide and are PSpace-complete, their Horn theories differ and are undecidable. We characterise the Horn theory of star continuous Kleene algebras i...
| Published in: | Lecture Notes in Computer Science |
|---|---|
| ISSN: | 0302-9743 1611-3349 |
| Published: |
Cham
Springer International Publishing
2019
|
| Online Access: |
Check full text
|
| URI: | https://cronfa.swan.ac.uk/Record/cronfa58113 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Abstract: |
We study the Horn theories of Kleene algebras and star continuous Kleene algebras, from the complexity point of view. While their equational theories coincide and are PSpace-complete, their Horn theories differ and are undecidable. We characterise the Horn theory of star continuous Kleene algebras in terms of downward closed languages and we show that when restricting the shape of allowed hypotheses, the problems lie in various levels of the arithmetical or analytical hierarchy. We also answer a question posed by Cohen about hypotheses of the form 1=S where S is a sum of letters: we show that it is decidable. |
|---|---|
| Keywords: |
Kleene algebra; Hypotheses; Horn theory; Complexity |
| College: |
Faculty of Science and Engineering |
| Start Page: |
207 |
| End Page: |
223 |