Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata

Authors Daniel Kirsten, Sylvain Lombardy



PDF
Thumbnail PDF

File

LIPIcs.STACS.2009.1850.pdf
  • Filesize: 192 kB
  • 12 pages

Document Identifiers

Author Details

Daniel Kirsten
Sylvain Lombardy

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.STACS.2009.1850

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.
Keywords
  • Min-plus automata
  • Determinization
  • Finite semigroups

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
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