License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2009.1850
URN: urn:nbn:de:0030-drops-18509
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/1850/
Go to the corresponding LIPIcs Volume Portal

Kirsten, Daniel ; Lombardy, Sylvain

Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata

pdf-format:
09001.KirstenDaniel.1850.pdf (0.2 MB)

Abstract

This paper solves the unambiguity and the sequentiality problem for polynomially ambiguous min-plus automata. This result is proved through a decidable algebraic characterization involving so-called metatransitions and an application of results from the structure theory of finite semigroups. It is noteworthy that the equivalence problem is known to be undecidable for polynomially ambiguous automata.

BibTeX - Entry

@InProceedings{kirsten_et_al:LIPIcs:2009:1850,
  author =	{Daniel Kirsten and Sylvain Lombardy},
  title =	{{Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{589--600},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Susanne Albers and Jean-Yves Marion},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/1850},
  URN =		{urn:nbn:de:0030-drops-18509},
  doi =		{10.4230/LIPIcs.STACS.2009.1850},
  annote =	{Keywords: Min-plus automata, Determinization, Finite semigroups}
}

Keywords: Min-plus automata, Determinization, Finite semigroups
Collection: 26th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2009
Date of publication: 19.02.2009

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