کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4952133 1442010 2017 22 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Characterization and complexity results on jumping finite automata
ترجمه فارسی عنوان
خصوصیات و پیچیدگی در پرت کردن اتوماتای ​​نهایی نتیجه می شود
کلمات کلیدی
ترجمه چکیده
در یک ماشین اتوماتیک نزولی، پس از خواندن و مصرف یک نماد، سر ورودی می تواند به موقعیت دلخواه درون ورودی باقی مانده پرش کند. ما کلاس های متناظر زبان را از لحاظ عبارات مختلط خاص مشخص می کنیم و سایر معانی مشابه از ادبیات موجود را مورد بررسی قرار می دهیم. علاوه بر این، ما نتایج متعددی در رابطه با سختی محاسباتی و الگوریتم های تجزیه و سایر وظایف اساسی در مورد پرتاب اتوماتای ​​نهایی ارائه می کنیم.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
خصوصیات و پیچیدگی در پرت کردن اتوماتای ​​نهایی نتیجه می شود
چکیده انگلیسی
In a jumping finite automaton, the input head can jump to an arbitrary position within the remaining input after reading and consuming a symbol. We characterize the corresponding class of languages in terms of special shuffle expressions and survey other equivalent notions from the existing literature. Moreover, we present several results concerning computational hardness and algorithms for parsing and other basic tasks concerning jumping finite automata.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 679, 30 May 2017, Pages 31-52
نویسندگان
, , , ,