On Determinism and Unambiguity of Weighted Two-way Automata

Abstract

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.

arXiv commentIn Proceedings AFL 2014, arXiv:1405.5272

References in corpus (2)

• Deciding Unambiguity and Sequentiality starting from a Finitely Ambiguous Max-Plus Automaton
• Series which are both max-plus and min-plus rational are unambiguous