کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875649 | 1441978 | 2018 | 23 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the gap between separating words and separating their reversals
ترجمه فارسی عنوان
در شکاف میان کلمات جداگانه و جدا شدن تغییرات آنها
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
جدایی کلمات، اتوماتای محدود
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A deterministic finite automaton (DFA) separates two strings w and x if it accepts w and rejects x. The minimum number of states required for a DFA to separate w and x is denoted by sep(w,x). The present paper shows that the difference |sep(w,x)âsep(wR,xR)| is unbounded for a binary alphabet; here wR stands for the mirror image of w. This solves an open problem stated in Demaine et al. (2011) [2].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 711, 8 February 2018, Pages 79-91
Journal: Theoretical Computer Science - Volume 711, 8 February 2018, Pages 79-91
نویسندگان
Farzam Ebrahimnejad,