کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952037 | 1442007 | 2017 | 21 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
State complexity of permutation on finite languages over a binary alphabet
ترجمه فارسی عنوان
پیچیدگی دولت از جایگزینی در زبان های محدود بر یک الفبای دودویی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
پیچیدگی دولت، اتوماتای محدود زبانهای محدود هماهنگی پارک،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The set of all strings Parikh equivalent to a string in a language L is called the permutation of L. The permutation of a finite n-state DFA (deterministic finite automaton) language over a binary alphabet can be recognized by a DFA with n2ân+22 states. We show that if the language consists of equal length binary strings the bound can be improved to f(n)=n2+n+13 and for every n congruent to 1 modulo 3 there exists an n-state DFA A recognizing a set of equal length strings such that the minimal DFA for the permutation of L(A) needs f(n) states.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 682, 19 June 2017, Pages 67-78
Journal: Theoretical Computer Science - Volume 682, 19 June 2017, Pages 67-78
نویسندگان
Da-Jung Cho, Daniel GoÄ, Yo-Sub Han, Sang-Ki Ko, Alexandros Palioudakis, Kai Salomaa,