Conference Paper/Proceeding/Abstract 910 views
Kleene Algebra with Hypotheses
Lecture Notes in Computer Science, Volume: 11425, Pages: 207 - 223
Swansea University Author:
Cécilia Pradic
Full text not available from this repository: check for access using links below.
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 |
| 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 |