Tropical Two-Way Automata
Abstract
In this paper we study two-way min-plus automata. We prove that two-way distance automata are equivalent to one-way distance automata. In the second part of the paper we show that, with general min-plus semirings, it is decidable whether every accepted word has a finite weight and that, in contrast, it is undecidable whether there exists a word accepted with a finite weight.
Domains
Discrete Mathematics [cs.DM]| Origin | Files produced by the author(s) |
|---|
Loading...
