نظریه مدل محدود و برخی کاربردهای آن در حساب محدود

سال انتشار: 1400
نوع سند: مقاله ژورنالی
زبان: فارسی
مشاهده: 54

فایل این مقاله در 19 صفحه با فرمت PDF قابل دریافت می باشد

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

JR_LOGIC-12-2_009

تاریخ نمایه سازی: 9 خرداد 1401

چکیده مقاله:

نظریه مدل محدود را می توان بخشی از نظریه مدل دانست که هدف آن بررسی مفاهیم و نتایج نظریه مدل در یک زبان شامل یک رابطه ترتیبی است در حالتی که سورهای مورد بحث همگی از نوع محدود هستند. از نظریه مدل محدود می توان برای مطالعه مسائل مربوط به نظریه حساب محدود استفاده کرد. حساب محدود را می توان زیرنظریه ای از حساب مرتبه اول پئانو در زبانی گسترش یافته دانست. خود حساب محدود، کاربردهای فراوانی در نظریه پیچیدگی محاسبات دارد. با تعریف و مطالعه مفاهیم پایه ای نظریه مدل در حالت محدود مانند حذف سور محدود و مدل کامل محدود، نتایج جالبی در نظریه مدل با کاربردهایی در نظریه پیچیدگی محاسبه و حساب محدود به دست آمده است. در این مقاله، ضمن مروری بر نتایج موجود در این زمینه، برخی مفاهیم و نتایج جدید را در این راستا ارائه می کنیم و ارتباط های آن ها را با برخی مسائل بنیادی در نظریه پیچیدگی محاسبه مطالعه می کنیم.

نویسندگان

ابوالفضل علم

گروه ریاضی، دانشگاه شهیدبهشتی ، تهران، ایران

مرتضی منیری

عضو هیئت علمی، گروه ریاضی، دانشگاه شهید بهشتی

مراجع و منابع این مقاله:

لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :
  • منیری، مرتضی (۱۳۸۴). «نظریه مرتبه اول پئانو و زیرنظریه های ...
  • Buss, S‎. ‎R‎. (۱۹۸۶).‎‎Bounded Arithmetic‎, Napoli: Bibliopolis ...
  • ‎Buss,‎S‎. ‎R‎. (۱۹۹۵). ‎Relating the Bounded Arithmetic and ‎‎Polynomial Time ...
  • ‎‎Buss,‎S‎. ‎R. (۱۹۹۸).‎ Handbook of Proof Theory‎.‎Amsterdam: ‎Elsevier ...
  • ‎Chang‎, C. C., ‎Keisler‎, J. (۱۹۹۰).‎Model theory‎, ‎‎Amsterdam: North-Holland‎ ...
  • ‎‎Cook‎, S. A. (۱۹۷۵). Feasibly Constructive Proofs and the Propositional ...
  • ‎Cook‎,‎S‎. ‎A. (۲۰۰۹). ‎Review of Three‎‎Papers Relating the Collapse of ...
  • ‎Cook‎,‎S‎. ‎A., ‎Urquhart‎,‎A. (۱۹۹۳). Functional Interpretations‎‎ of Feasibly Constructive Arithmetic‎. ...
  • ‎‎Hajek‎, ‎P.,‎Pudlak‎, P. (۱۹۹۳).‎Metamathematics of First-order Arithmetic‎. Berlin: ‎Springer-Verlag ...
  • Hodges‎, H. (۱۹۹۷). ‎A Shorter Model Theory‎. ‎Cambridge: ‎Cambridge University ...
  • Kaye‎, R. (۱۹۹۱).‎Models of Peano Arithmetic‎. ‎Oxford: Oxford University Press ...
  • ‎Krajicek‎, J. (۱۹۹۵). Bounded Arithmetic‎, ‎Propositional Logic‎,‎and Complexity Theory. ‎Cambridge‎: ...
  • ‎Krajicek‎, J. ,‎Pudlak‎, P., ‎‎Takeuti, G. (۱۹۹۱).‎Bounded Arithmetic and the ...
  • ‎Marker‎, D. (۲۰۰۲). Model Theory‎: ‎An Introduction‎. ‎New York: ‎Springer-Verlag ...
  • Moniri‎, M‎. (۲۰۰۶). An independence result for intuitionistic bounded arithmetic. ...
  • Moniri‎, M‎. (۲۰۰۷). ‎Preservation Theorems for Bounded Formulas. ‎Archive for ...
  • Parikh, R. J. (۱۹۷۱). Existence and feasibility in arithmetic, Journal ...
  • Parikh, R. J. (۱۹۷۳). Some results on the lengths of ...
  • ‎‎Zambella‎, D. (۱۹۹۶). Notes on Polynomially Bounded Arithmetic‎, ‎Journal of ...
  • نمایش کامل مراجع