6533b7d0fe1ef96bd125ab80

RESEARCH PRODUCT

Two-way automata with multiplicity

Marcella AnselmoMarcella Anselmo

subject

Pure mathematicsFinite-state machineRegular languageLocal configurationCommutative semiringMultiplicity (mathematics)Computer Science::Formal Languages and Automata TheorySemiringAutomatonMathematics

description

We introduce the notion of two-way automata with multiplicity in a semiring. Our main result is the extension of Rabin, Scott and Shepherdson's Theorem to this more general case. We in fact show that it holds in the case of automata with multiplicity in a commutative semiring, provided that an additional condition is satisfied. We prove that this condition is also necessary in a particular case. An application is given to zig-zag codes using special two-way automata.

yearjournalcountryeditionlanguage
2005-12-11
https://doi.org/10.1007/bfb0032024