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.
Complete list of metadatas

Cited literature [7 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-01866160
Contributor : Sylvain Lombardy <>
Submitted on : Friday, October 26, 2018 - 8:12:23 AM
Last modification on : Monday, September 16, 2019 - 11:02:07 AM
Long-term archiving on : Sunday, January 27, 2019 - 12:48:22 PM

File

470153_1_En_6_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Louis-Marie Dando, Sylvain Lombardy. Two-Way Automata over Locally Finite Semirings. 20th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2018, Hallifax, NS, Canada. pp.62-74, ⟨10.1007/978-3-319-94631-3_6⟩. ⟨hal-01866160⟩

Share

Metrics

Record views

476

Files downloads

91