1 Search Results for "Kirsten, Daniel"

Document
DOI: 10.4230/LIPIcs.STACS.2009.1850
Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata

Authors: Daniel Kirsten and Sylvain Lombardy

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

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

Daniel Kirsten and Sylvain Lombardy. Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 589-600, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{kirsten_et_al:LIPIcs.STACS.2009.1850,
  author =	{Kirsten, Daniel and Lombardy, Sylvain},
  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 =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1850},
  URN =		{urn:nbn:de:0030-drops-18509},
  doi =		{10.4230/LIPIcs.STACS.2009.1850},
  annote =	{Keywords: Min-plus automata, Determinization, Finite semigroups}
}
  • Refine by Author
  • 1 Kirsten, Daniel
  • 1 Lombardy, Sylvain

  • Refine by Classification

  • Refine by Keyword
  • 1 Determinization
  • 1 Finite semigroups
  • 1 Min-plus automata

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2009

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact