کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
438080 690225 2008 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A finite set of functions with an EXPTIME-complete composition problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A finite set of functions with an EXPTIME-complete composition problem
چکیده انگلیسی

We exhibit a finite family of functions over a finite set (i.e. a finite algebra), such that the problem whether a given function can be obtained as a composition of the members of this family (i.e. is a member of the clone generated by the algebra) is EXPTIME-complete.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 407, Issues 1–3, 6 November 2008, Pages 330-341