کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436226 | 689977 | 2009 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Efficient computation of the iteration of functions
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Given a function f from {0,1,…,N−1} to {0,1,…,N−1}, we prove that fm(x), the mth iterate of f at x, can be computed in time O(logN) for each natural number m and each x by using O(N) information that is generated in a preprocessing procedure. Two types of optimal orbit decompositions of functional graphs are proposed for the preprocess. Both preprocesses require only linear time and linear space. Our decompositions minimize the number of recursions in the computation of fm(x) and solve some open problems in Tsaban (Discrete Applied Mathematics 155 (2007) 386–393).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 410, Issues 8–10, 1 March 2009, Pages 988-993
Journal: Theoretical Computer Science - Volume 410, Issues 8–10, 1 March 2009, Pages 988-993