کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
438492 | 690281 | 2007 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Complementation of rational sets on scattered linear orderings of finite rank
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In a preceding paper [V. Bruyère, O. Carton, Automata on linear orderings, in: J. Sgall, A. Pultr, P. Kolman (Eds.), MFCS’2001, in: Lect. Notes in Comput. Sci., vol. 2136, 2001, pp. 236–247. iGM report 2001-12], automata have been introduced for words indexed by linear orderings. These automata are a generalization of automata for finite, infinite, bi-infinite, and even transfinite words studied by Büchi. Kleene’s theorem has been generalized to these words. We show that deterministic automata do not have the same expressive power. Despite this negative result, we prove that rational sets of words of finite ranks are closed under complementation.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 382, Issue 2, 31 August 2007, Pages 109-119
Journal: Theoretical Computer Science - Volume 382, Issue 2, 31 August 2007, Pages 109-119