کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
439109 690448 2009 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The “equal last letter” predicate for words on infinite alphabets and classes of multitape automata
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
The “equal last letter” predicate for words on infinite alphabets and classes of multitape automata
چکیده انگلیسی

We consider the first-order theory of the free infinitely generated monoid with the usual predicates “prefix” and “equal length” along with the predicate “equal last letter”. The associated definable relations are related to the algebras of relations recognized by different types of multitape automata which are natural extensions of the famous Rabin–Scott multitape automata and the synchronous automata. We investigate these classes of automata and solve decision issues concerning them.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 410, Issues 30–32, 20 August 2009, Pages 2870-2884