Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
438835 | Theoretical Computer Science | 2006 | 21 Pages |
Abstract
This paper is a survey where we try to organise the known answers to the question whether a given finite automaton with multiplicity in a semiring K is equivalent to a sequential, or input deterministic, one. We shall see that depending on K, the question goes from obvious to open, that the answer goes from yes to undecidable. We review results on sequentiality in the cases of series of finite image, of series with multiplicity in fields, and of series with multiplicity in idempotent semirings.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics