کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9512467 | 1632466 | 2005 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Expressive power of existential first-order sentences of Büchi's sequential calculus
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The aim of this paper is to study the first-order theory of the successor, interpreted on finite words. More specifically, we are interested in the hierarchy based on quantifier alternations (or Σn-hierarchy). It was known (J. Comput. Syst. Sci. 25 (1982) 360-375) that this hierarchy collapses at level 2, but the expressive power of the lower levels was not characterized effectively. We give a semigroup theoretic description of the expressive power of BΣ1, the boolean combinations of existential formulas. We also give an O(n7)-time algorithm to decide whether the language accepted by a deterministic n-state automaton is expressible by a first-order sentence (respectively, a BΣ1-sentence).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 291, Issues 1â3, 6 March 2005, Pages 155-174
Journal: Discrete Mathematics - Volume 291, Issues 1â3, 6 March 2005, Pages 155-174
نویسندگان
Jean-Eric Pin,