History


Please fill in your query. A complete syntax description you will find on the General Help page.
Two-way automata with multiplicty. (English)
Automata, languages and programming, Proc. 17th Int. Colloq., Warwick/GB 1990, Lect. Notes Comput. Sci. 443, 88-102 (1990).
Summary: [For the entire collection see Zbl 0758.00017.] We introduce the notion of two-way automata with multiplicity in a semiring. Our main result is the extension of {\it M. O. Rabin} and {\it D. Scott} [Finite automata and their decision problems, IBM J. Res. Dev. 3, No. 2, 114-125 (1959); and in {\it E. F. Moore} (editor), “Sequential machines: selected papers”, Addison-Wesley (1964)] and {\it J. C. Shepherdson} [The reduction of two-way automata in one-way automata, IBM J. Res. 3, No. 2, 198-200 (1959); and in {\it E. F. Moore} (editor), “Sequential machines: selected papers”, Addison-Wesley (1964)] 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 with 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.
WorldCat.org
Valid XHTML 1.0 Transitional Valid CSS!