کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950613 | 1364294 | 2017 | 28 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the state complexity of operations on two-way finite automata
ترجمه فارسی عنوان
در پیچیدگی دولت از عملیات در اتوماتیک دو طرفه محدود
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
پیچیدگی دولت، پیچیدگی توصیفی اتوماتای دو طرفه،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The paper investigates the effect of basic language-theoretic operations on the number of states in two-way deterministic finite automata (2DFAs). If m and n are the number of states in the 2DFAs recognizing the arguments of the following operations, then their result requires the following number of states: at least m+nâo(m+n) and at most 4m+n+const for union; at least m+nâo(m+n) and at most m+n+1 for intersection; at least Ω(mn)+2Ω(n)logâ¡m and at most 2mm+1â
2nn+1 for concatenation; at least 1n2n2â1 and at most 2O(nn+1) for Kleene star, square and projections; between n+1 and n+2 for reversal; exactly 2n for inverse homomorphisms. All results are obtained by first establishing high lower bounds on the number of states in any 1DFAs recognizing these languages, and then using these bounds to reason about the size of any equivalent 2DFAs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 253, Part 1, April 2017, Pages 36-63
Journal: Information and Computation - Volume 253, Part 1, April 2017, Pages 36-63
نویسندگان
Galina Jirásková, Alexander Okhotin,