کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4952298 1364438 2017 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Local testability from words to traces, a suitable definition
ترجمه فارسی عنوان
تردید محلی از کلمات به آثار، تعریف مناسب
کلمات کلیدی
ردیابی زبان، آزمودنی محلی، شناسایی، ستاره فریزر، انطباق، ایده آل،
ترجمه چکیده
خانواده زبان های آزمایشی محلی به طور گسترده مورد مطالعه قرار گرفته است. ما پیشنهادی از مفهوم تستپذیری محلی را از مونوئید آزاد به مونوئید نیمه ممتد آزاد (به اصطلاح ردیابی مونوئید) پیشنهاد می کنیم. ما نشان می دهیم که برای رسمیت دادن مفهوم مکان در آثار مفهومی دشوار است و ما نوع جدیدی از عامل را معرفی میکنیم که این مشکلات را در نظر میگیرد. بنابراین، یک زبان ردیابی محلی قابل تست را به عنوان یک اتحاد از طبقات یک رابطه هم ارز جدید یک شاخص محدود تعریف می کنیم که ثابت شده است که سازگاری با استفاده از ترکیبیات روی اثرات است. سپس ما ویژگی های نظری مجموعه ای از خانواده از زبان های ردیابی محلی قابل تست را از نظر برخی از مجموعه های به نام این شبه ایده آل ها به عنوان تعمیم ایده آل ها در کلمات می دهیم. در نهایت، با تجزیه و تحلیل موارد شدید مونوئید آزاد و مونوئید تعویض رایگان، ما ثابت می کنیم که این خانواده جدید دقیقا همان زبان محلی تسلط در مورد کلمات است.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The family of locally testable languages has been extensively studied. We propose an extension of the notion of local testability from the free monoid to the free partially commutative monoid (the so called trace monoid). We show that to formalize the notion of locality in traces is conceptually difficult, and we introduce a new kind of factor which takes into account these difficulties. Thus we define a locally testable trace language as a union of classes of a new equivalence relation of a finite index, which is proved to be a congruence using some combinatorics on traces. Then we give a set-theoretic characterization of the family of locally testable trace languages, in terms of some sets called here quasi-ideals, as a generalization of ideals in words. Finally, analyzing the extreme cases of the free monoid and the free commutative monoid, we prove that this new family becomes exactly that of locally testables languages in the case of words.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 658, Part A, 7 January 2017, Pages 175-189
نویسندگان
,