Kleene Algebra with Hypotheses

Doumane, Amina; Kuperberg, Denis; Pous, Damien; Pradic, Cécilia

doi:10.1007/978-3-030-17127-8_12

Conference Paper/Proceeding/Abstract 379 views 85 downloads

Kleene Algebra with Hypotheses

Amina Doumane, Denis Kuperberg, Damien Pous, Cécilia Pradic

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)

Check full text

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

Full description

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!

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>SCS</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>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</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 SCS 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 Computer Science COLLEGE CODE SCS 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-05T04:14:22Z
_version_	1763753971412893696
score	10.997933

Kleene Algebra with Hypotheses

Similar Items