Sequential?

详细信息    查看全文

• 作者：Sylvain Lombardy and Jacques Sakarovitch
• 关键词：Finite automata ; Sequential machine ; Twinning property
• 刊名：Theoretical Computer Science
• 出版年：2006
• 出版时间：5 May 2006
• 年：2006
• 卷：356
• 期：1-2
• 页码：224-244
• 全文大小：387 K

文摘

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 is equivalent to a sequential, or input deterministic, one. We shall see that depending on , 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.