We show that the termination of Mohri's algorithm is decidable for polynomially ambiguous weighted finite automata over the tropical semiring which gives a partial answer to a question by Mohri [29]. The proof relies on an improvement of the notion of the twins property and a Burnside type characterization for the finiteness of the set of states produced by Mohri's algorithm.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:33091 |
| Date | 06 February 2019 |
| Creators | Kirsten, Daniel |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, doc-type:article, info:eu-repo/semantics/article, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | 0988-3754, 1290-385X |
Page generated in 0.0018 seconds