کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4950589 1440713 2017 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Deletion operations on deterministic families of automata
ترجمه فارسی عنوان
عملیات حذف در خانواده های متشکل از اتوماتای
کلمات کلیدی
اتوماسیون و منطق، دستگاه های شمارنده، عملیات حذف، معکوس معکوس، تعیین کننده، اتوماتای ​​محدود
ترجمه چکیده
نشان داده شده است که زبانهای چند کانونی با محدودیت یکطرفه به طور مجردی به شکل یک طرفه با مقادیر مناسب با زبان های بسیاری از خانواده های زبان بسته می شوند؛ حتی آنهایی که توسط دستگاه های غیرتمرینتی مانند زبان های غیر متنی تعریف شده اند. همچنین نشان داده شده است که هنگامیکه با یک ماشین مجزا یک طرفه با یک شمارنده که تنها یک معکوس را ایجاد می کند، فاکتور چپ با زبان های مختلفی از خانواده های مختلف زبان مجددا به دست می آید، از جمله آنهایی که توسط ماشین های غیرتمرینتی تعریف شده مانند زبان های غیر متنی - تنها زبانهای متقابل چندگانه را به طور قطعی و یک طرفه به کار می برند. این نتایج شگفت انگیز است با توجه به ماهیت غیرمتمرکز تمایز. با این حال، اگر دو شمارنده معکوس بر روی شمارنده یا یک شمارنده ثانویه ثانویه 1 وجود داشته باشد، تقسیم سمت چپ (یا حتی عملیات پسوند)، زبان هایی را می دهد که نمی توانند توسط دستگاه های چند شمارنده مجزا ، و نه ماشین آلات قطعی 2 طرفه با یک ضد شمارنده معکوس.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
It is shown that one-way deterministic reversal-bounded multicounter languages are closed under right quotient with languages from many language families; even those defined by nondeterministic machines such as the context-free languages. Also, it is shown that when starting with one-way deterministic machines with one counter that makes only one reversal, taking the left quotient with languages from many different language families - again including those defined by nondeterministic machines such as the context-free languages - yields only one-way deterministic reversal-bounded multicounter languages. These results are surprising given the nondeterministic nature of the deletion. However, if there are two more reversals on the counter, or a second 1-reversal-bounded counter, taking the left quotient (or even just the suffix operation) yields languages that can neither be accepted by deterministic reversal-bounded multi-counter machines, nor by 2-way deterministic machines with one reversal-bounded counter.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 256, October 2017, Pages 237-252
نویسندگان
, , ,