Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata

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.
Type de document :
Communication dans un congrès
Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.589-600, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00360205
Contributeur : Publications Loria <>
Soumis le : mardi 10 février 2009 - 16:21:35
Dernière modification le : mercredi 11 avril 2018 - 12:12:03
Document(s) archivé(s) le : mardi 8 juin 2010 - 20:38:24

Fichier

49-kirsten.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00360205, version 1

Citation

Daniel Kirsten, Sylvain Lombardy. Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata. Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.589-600, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00360205〉

Partager

Métriques

Consultations de la notice

138

Téléchargements de fichiers

254