کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
426410 686052 2015 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Existence of constants in regular splicing languages
ترجمه فارسی عنوان
وجود ثابت در زبان های اسپلایزی معمولی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

In spite of wide investigations of finite splicing systems in formal language theory, basic questions, such as their characterization, remain unsolved. It has been conjectured that a necessary condition for a regular language L to be a splicing language is that L must have a constant in the Schützenberger sense. We prove this longstanding conjecture to be true. The result is based on properties of strongly connected components of the minimal deterministic finite state automaton for a regular splicing language. Using constants of the corresponding languages, we also provide properties of transitive automata and path-automata.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 242, June 2015, Pages 340–353
نویسندگان
, ,