کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6873834 | 1440707 | 2018 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Accepting runs in a two-way finite automaton
ترجمه فارسی عنوان
پذیرش در ماشین اتوماتیک دو طرفه اجرا می شود
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
اتوماتای دو طرفه، پذیرش اجرا، نمونه برداری،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
Journal: Information and Computation - Volume 260, June 2018, Pages 1-8
نویسندگان
Oscar H. Ibarra, Zhe Dang, Qin Li,