No Cover Image

Conference Paper/Proceeding/Abstract 19 views 7 downloads

Kleene Algebra with Hypotheses / Amina Doumane, Denis Kuperberg, Damien Pous, Pierre Pradic

Lecture Notes in Computer Science, Volume: 11425, Pages: 207 - 223

Swansea University Author: Pierre Pradic

  • 58113.pdf

    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)

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!
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: College of Science
Start Page: 207
End Page: 223