کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6873874 | 1440709 | 2018 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Automata for regular expressions with shuffle
ترجمه فارسی عنوان
خودکار برای عبارات منظم با زدن
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
عبارات منظم، عملیات مختلط، مشتقات جزئی، اتوماتای محدود اتوماتای موقعیت مورد متوسط، ترکیبیات تحلیلی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We generalize the partial derivative automaton and the position automaton to regular expressions with shuffle, and study their state complexity in the worst, as well as in the average case. The number of states of the partial derivative automaton (Apd) is, in the worst case, at most 2m, where m is the number of letters in the expression. The asymptotic average is bounded by (43)m. We define a position automaton (Apos) that is homogeneous, but in which several states can correspond to a same position, and we show that Apd is a quotient of Apos. The number of states of the position automaton is at most 1+m(2mâ1), while the asymptotic average is no more than m(43)m.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 259, Part 2, April 2018, Pages 162-173
Journal: Information and Computation - Volume 259, Part 2, April 2018, Pages 162-173
نویسندگان
Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis,