نظریه مدل محدود و برخی کاربردهای آن در حساب محدود (مقاله علمی وزارت علوم)

چکیده

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