Conference Paper/Proceeding/Abstract 583 views 128 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 |
first_indexed |
2021-10-15T15:33:23Z |
---|---|
last_indexed |
2021-10-19T03:23:09Z |
id |
cronfa58113 |
recordtype |
SURis |
fullrecord |
<?xml version="1.0"?><rfc1807><datestamp>2021-10-18T13:22:19.4650668</datestamp><bib-version>v2</bib-version><id>58113</id><entry>2021-09-27</entry><title>Kleene Algebra with Hypotheses</title><swanseaauthors><author><sid>3b6e9ebd791c875dac266b3b0b358a58</sid><ORCID>0000-0002-1600-8846</ORCID><firstname>Cécilia</firstname><surname>Pradic</surname><name>Cécilia Pradic</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2021-09-27</date><deptcode>MACS</deptcode><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.</abstract><type>Conference Paper/Proceeding/Abstract</type><journal>Lecture Notes in Computer Science</journal><volume>11425</volume><journalNumber/><paginationStart>207</paginationStart><paginationEnd>223</paginationEnd><publisher>Springer International Publishing</publisher><placeOfPublication>Cham</placeOfPublication><isbnPrint/><isbnElectronic/><issnPrint>0302-9743</issnPrint><issnElectronic>1611-3349</issnElectronic><keywords>Kleene algebra; Hypotheses; Horn theory; Complexity</keywords><publishedDay>5</publishedDay><publishedMonth>4</publishedMonth><publishedYear>2019</publishedYear><publishedDate>2019-04-05</publishedDate><doi>10.1007/978-3-030-17127-8_12</doi><url/><notes/><college>COLLEGE NANME</college><department>Mathematics and Computer Science School</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>MACS</DepartmentCode><institution>Swansea University</institution><apcterm/><lastEdited>2021-10-18T13:22:19.4650668</lastEdited><Created>2021-09-27T22:55:54.1690232</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>Amina</firstname><surname>Doumane</surname><order>1</order></author><author><firstname>Denis</firstname><surname>Kuperberg</surname><order>2</order></author><author><firstname>Damien</firstname><surname>Pous</surname><order>3</order></author><author><firstname>Cécilia</firstname><surname>Pradic</surname><orcid>0000-0002-1600-8846</orcid><order>4</order></author></authors><documents><document><filename>58113__21179__bb38b417353e4353bde053fc7ed16d0f.pdf</filename><originalFilename>58113.pdf</originalFilename><uploaded>2021-10-15T16:56:18.2230678</uploaded><type>Output</type><contentLength>393622</contentLength><contentType>application/pdf</contentType><version>Version of Record</version><cronfaStatus>true</cronfaStatus><documentNotes>© The Author(s) 2019. This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License</documentNotes><copyrightCorrect>true</copyrightCorrect><language>eng</language><licence>http://creativecommons.org/licenses/by/4.0/</licence></document></documents><OutputDurs/></rfc1807> |
spelling |
2021-10-18T13:22:19.4650668 v2 58113 2021-09-27 Kleene Algebra with Hypotheses 3b6e9ebd791c875dac266b3b0b358a58 0000-0002-1600-8846 Cécilia Pradic Cécilia Pradic true false 2021-09-27 MACS 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. Conference Paper/Proceeding/Abstract Lecture Notes in Computer Science 11425 207 223 Springer International Publishing Cham 0302-9743 1611-3349 Kleene algebra; Hypotheses; Horn theory; Complexity 5 4 2019 2019-04-05 10.1007/978-3-030-17127-8_12 COLLEGE NANME Mathematics and Computer Science School COLLEGE CODE MACS Swansea University 2021-10-18T13:22:19.4650668 2021-09-27T22:55:54.1690232 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Amina Doumane 1 Denis Kuperberg 2 Damien Pous 3 Cécilia Pradic 0000-0002-1600-8846 4 58113__21179__bb38b417353e4353bde053fc7ed16d0f.pdf 58113.pdf 2021-10-15T16:56:18.2230678 Output 393622 application/pdf Version of Record true © The Author(s) 2019. This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License true eng http://creativecommons.org/licenses/by/4.0/ |
title |
Kleene Algebra with Hypotheses |
spellingShingle |
Kleene Algebra with Hypotheses Cécilia Pradic |
title_short |
Kleene Algebra with Hypotheses |
title_full |
Kleene Algebra with Hypotheses |
title_fullStr |
Kleene Algebra with Hypotheses |
title_full_unstemmed |
Kleene Algebra with Hypotheses |
title_sort |
Kleene Algebra with Hypotheses |
author_id_str_mv |
3b6e9ebd791c875dac266b3b0b358a58 |
author_id_fullname_str_mv |
3b6e9ebd791c875dac266b3b0b358a58_***_Cécilia Pradic |
author |
Cécilia Pradic |
author2 |
Amina Doumane Denis Kuperberg Damien Pous Cécilia Pradic |
format |
Conference Paper/Proceeding/Abstract |
container_title |
Lecture Notes in Computer Science |
container_volume |
11425 |
container_start_page |
207 |
publishDate |
2019 |
institution |
Swansea University |
issn |
0302-9743 1611-3349 |
doi_str_mv |
10.1007/978-3-030-17127-8_12 |
publisher |
Springer International Publishing |
college_str |
Faculty of Science and Engineering |
hierarchytype |
|
hierarchy_top_id |
facultyofscienceandengineering |
hierarchy_top_title |
Faculty of Science and Engineering |
hierarchy_parent_id |
facultyofscienceandengineering |
hierarchy_parent_title |
Faculty of Science and Engineering |
department_str |
School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science |
document_store_str |
1 |
active_str |
0 |
description |
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. |
published_date |
2019-04-05T11:32:41Z |
_version_ |
1824666483279527936 |
score |
11.052662 |