On Determinism and Unambiguity of Weighted Two-way Automata

Vincent Carnino
(LIGM, Université Paris-Est)
Sylvain Lombardy
(LaBRI, Insitut Polytechnique de Bordeaux)

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.

In Zoltán Ésik and Zoltán Fülöp: Proceedings 14th International Conference on Automata and Formal Languages (AFL 2014), Szeged, Hungary, May 27-29, 2014, Electronic Proceedings in Theoretical Computer Science 151, pp. 188–200.
Published: 21st May 2014.

ArXived at: http://dx.doi.org/10.4204/EPTCS.151.13 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org