کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6873834 1440707 2018 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Accepting runs in a two-way finite automaton
ترجمه فارسی عنوان
پذیرش در ماشین اتوماتیک دو طرفه اجرا می شود
کلمات کلیدی
اتوماتای ​​دو طرفه، پذیرش اجرا، نمونه برداری،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
An accepting run in a two-way finite automaton M is a sequence of states that M enters during some accepting computation. The set of all such runs is denoted by Lrun,M. We study the complexity of Lrun,M when M is a 2NFA (2DFA). We also look at the complexity of “position sampling” (the sequence of states that M enters in specified positions of some accepted input) in a 2NFA. In particular, we give some language properties of sampled runs of 2NFAs augmented with restricted unbounded storage.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 260, June 2018, Pages 1-8
نویسندگان
, , ,