Back to Search
Start Over
Deciding Unambiguity and Sequentiality starting from a Finitely Ambiguous Max-Plus Automaton
- Source :
- Theoretical Computer Science 327, 3 (2004) 349-373
- Publication Year :
- 2007
-
Abstract
- Finite automata with weights in the max-plus semiring are considered. The main result is: it is decidable in an effective way whether a series that is recognized by a finitely ambiguous max-plus automaton is unambiguous, or is sequential. A collection of examples is given to illustrate the hierarchy of max-plus series with respect to ambiguity.
- Subjects :
- Computer Science - Computational Complexity
Subjects
Details
- Database :
- arXiv
- Journal :
- Theoretical Computer Science 327, 3 (2004) 349-373
- Publication Type :
- Report
- Accession number :
- edsarx.0709.4117
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1016/j.tcs.2004.02.049