We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
TWO-WAY REPRESENTATIONS AND WEIGHTED AUTOMATA.
- Authors
LOMBARDY, SYLVAIN
- Abstract
We study the series realized by weighted two-way automata, that are strictly more powerful than weighted one-way automata. To this end, we consider the Hadamard product and the Hadamard iteration of formal power series. We introduce two-way representations and show that the series they realize are the solutions of fixed-point equations. In rationally additive semirings, we prove that two-way automata are equivalent to two-way representations, and, for some specific classes of two-way automata, rotating and sweeping automata, we give a characterization of the series that can be realized.
- Subjects
ROBOTS; MACHINE theory; FIXED point theory; HADAMARD matrices; MEMORYLESS systems
- Publication
RAIRO - Theoretical Informatics & Applications, 2016, Vol 50, Issue 4, p331
- ISSN
2804-7346
- Publication type
Article
- DOI
10.1051/ita/2016026