کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10334319 | 690377 | 2005 | 19 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the descriptional complexity of finite automata with modified acceptance conditions
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We consider deterministic and nondeterministic finite automata with acceptance conditions that rely on the whole history of a computation on a given word and not only on the last state of the computation under consideration. Formally, these conditions can be seen as the natural analogies of the Büchi and Muller acceptance for finite automata on infinite words. We study the computational power of these new acceptance mechanisms and prove some results on the descriptional complexity of conversions between automata with these new acceptance criteria and finite automata with ordinary acceptance.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 330, Issue 2, 2 February 2005, Pages 267-285
Journal: Theoretical Computer Science - Volume 330, Issue 2, 2 February 2005, Pages 267-285
نویسندگان
Markus Holzer, Martin Kutrib,