کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
438835 690336 2006 21 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Sequential?
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Sequential?
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 356, Issues 1–2, 5 May 2006, Pages 224-244