کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
426798 | 686285 | 2012 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The Church problem for expansions of (N,<)(N,<) by unary predicates
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
For a two-variable formula B(X,Y)B(X,Y) of Monadic Logic of Order (MLO) the Church synthesis problem concerns the existence and construction of a finite-state operator Y=F(X)Y=F(X) such that B(X,F(X))B(X,F(X)) is universally valid over Nat.Büchi and Landweber (1969) proved that the Church synthesis problem is decidable.We investigate a parameterized version of the Church synthesis problem. In this extended version a formula B and a finite-state operator F might contain as a parameter a unary predicate P.A large class of predicates P is exhibited such that the Church problem with the parameter P is decidable.Our proofs use composition method and game theoretical techniques.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 218, September 2012, Pages 1–16
Journal: Information and Computation - Volume 218, September 2012, Pages 1–16
نویسندگان
Alexander Rabinovich,