2014/05/22 by Vincent Carnino, Sylvain Lombardy
Computer Science · #cs.FL
paper · pdf · doi:10.4204/eptcs.151.13
published as EPTCS 151, 2014, pp. 188-200 · In Proceedings AFL 2014, arXiv:1405.5272
arxiv created 2014/05/22 · arxiv updated 2014/05/23
In this paper, we first study the conversion of weighted two-way automata to one-way automata. We show that this conversion preserves the unambiguity but does not preserve the determinism. Yet, we prove that the conversion of an unambiguous weighted one-way automaton into a two-way automaton leads to a deterministic two-way automaton. As a consequence, we prove that unambiguous weighted two-way automata are equivalent to deterministic weighted two-way automata in commutative semirings.