کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
426830 686305 2011 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Curves that must be retraced
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Curves that must be retraced
چکیده انگلیسی

We exhibit a polynomial time computable plane curve Γ that has finite length, does not intersect itself, and is smooth except at one endpoint, but has the following property. For every computable parametrization f of Γ and every positive integer m, there is some positive-length subcurve of Γ that f retraces at least m times. In contrast, every computable curve of finite length that does not intersect itself has a constant-speed (hence non-retracing) parametrization that is computable relative to the halting problem.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 209, Issue 6, June 2011, Pages 992-1006