Two-Way Automata over Locally Finite Semirings
Abstract
Two-way transducers or weighted automata are in general more powerful than one-way ones. We show that two-way automata over locally finite semirings may have undefined behaviour. We prove that it is decidable whether this behaviour is defined, and, if it is, we show that two-way automata over locally finite semirings are equivalent to one-way automata.
| Origin | Files produced by the author(s) |
|---|
Loading...
