License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2017.66
URN: urn:nbn:de:0030-drops-81334
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8133/
Go to the corresponding LIPIcs Volume Portal

Brunet, Paul

Reversible Kleene lattices

pdf-format:
LIPIcs-MFCS-2017-66.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{brunet:LIPIcs:2017:8133,
  author =	{Paul Brunet},
  title =	{{Reversible Kleene lattices}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{66:1--66:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8133},
  URN =		{urn:nbn:de:0030-drops-81334},
  doi =		{10.4230/LIPIcs.MFCS.2017.66},
  annote =	{Keywords: Kleene algebra, Automata, Petri nets, Decidability, Complexity, Formal languages, Lattice}
}

Keywords: Kleene algebra, Automata, Petri nets, Decidability, Complexity, Formal languages, Lattice
Collection: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Issue Date: 2017
Date of publication: 01.12.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI