کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
426757 | 686259 | 2014 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Removing nondeterminism in constant height pushdown automata
ترجمه فارسی عنوان
حذف غیرمتمرکز در اتوماتیک فشرده سازی ارتفاع ثابت
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
پیچیدگی توصیفی خودکار اتوماتیک دولتی، زبان های منظم، اتوماتای فشردگی قطعی و غیرمتمرکز
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We study the descriptional cost of removing nondeterminism in constant height pushdown automata—i.e., pushdown automata with a built-in constant limit on the height of the pushdown. We show a double-exponential size increase when converting a constant height nondeterministic pushdown automaton into an equivalent deterministic device. Moreover, we prove that such a double-exponential blow-up cannot be avoided by certifying its optimality.As a direct consequence, we get that eliminating nondeterminism in classical finite state automata is single-exponential even with the help of a constant height pushdown store.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 237, October 2014, Pages 257–267
Journal: Information and Computation - Volume 237, October 2014, Pages 257–267
نویسندگان
Zuzana Bednárová, Viliam Geffert, Carlo Mereghetti, Beatrice Palano,