کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951185 | 1441197 | 2017 | 22 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
State complexity of operations on input-driven pushdown automata
ترجمه فارسی عنوان
پیچیدگی دولت در عملیات بر روی اتوماتیک رانده شده توسط ورودی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The family of languages recognized by deterministic input-driven pushdown automata (IDPDA; a.k.a. visibly pushdown automata, a.k.a. nested word automata) is known to be closed under concatenation, Kleene star and reversal (under natural assumptions on the partition of the alphabet). As shown by Alur and Madhusudan (2004) [2], the Kleene star and the reversal of an n-state IDPDA can be represented by an IDPDA with 2O(n2) states, while concatenation of an m-state and an n-state IDPDA is represented by an IDPDA with 2O((m+n)2) states. This paper presents more efficient constructions for the Kleene star and for the reversal, which yield 2Î(nlogâ¡n) states, as well as an m2Î(nlogâ¡n)-state construction for the concatenation. These constructions are optimal up to a factor in the exponent, due to the close lower bounds previously established by Piao and Salomaa (2009) [27].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 86, June 2017, Pages 207-228
Journal: Journal of Computer and System Sciences - Volume 86, June 2017, Pages 207-228
نویسندگان
Alexander Okhotin, Kai Salomaa,