UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Reversible Kleene Lattices

Brunet, P; (2017) Reversible Kleene Lattices. In: Larsen, KG and Bodlaender, HL and Raskin, J-F, (eds.) Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). (pp. 66:1-66:14). LIPICS: Dagstuhl, Germany. Green open access

[thumbnail of Brunet_Reversible kleene lattices_VoR.pdf]
Preview
Text
Brunet_Reversible kleene lattices_VoR.pdf - Published Version

Download (605kB) | Preview

Abstract

We investigate the equational theory of reversible Kleene lattices, that is algebras of languages with the regular operations (union, composition and Kleene star), together with intersection and mirror image. Building on results by Andréka, Mikulás and Németi from 2011, we construct the free representation of this algebra. We then provide an automaton model to compare representations. These automata are adapted from Petri automata, which we introduced with Pous in 2015 to tackle a similar problem for algebras of binary relations. This allows us to show that testing the validity of equations in this algebra is decidable, and in fact ExpSpace-complete.

Type: Proceedings paper
Title: Reversible Kleene Lattices
Event: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Location: Aalborg, Denmark
Dates: 21st-25th August 2017
ISBN-13: 978-3-95977-046-0
Open access status: An open access version is available from UCL Discovery
DOI: 10.4230/LIPIcs.MFCS.2017.66
Publisher version: http://dx.doi.org/10.4230/LIPIcs.MFCS.2017.66
Language: English
Additional information: © Paul Brunet. Licensed under Creative Commons License CC-BY (https://creativecommons.org/licenses/by/3.0/).
Keywords: Kleene algebra, Automata, Petri nets, Decidability, Complexity
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/10053897
Downloads since deposit
33Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item