@article { author = {Alam, Abolfazl and Moniri, Morteza}, title = {Bounded Model Theory and its Applications to Bounded Arithmetic}, journal = {Logical Studies}, volume = {12}, number = {2}, pages = {193-211}, year = {2022}, publisher = {Institute for Humanities and Cultural Studies}, issn = {2383-0662}, eissn = {2383-0670}, doi = {10.30465/lsj.2021.36251.1358}, abstract = {Bounded model theory can be considered as part of first-order model theory, which its aim is to study model-theoretic notions in a language consisting of an order relation where all quantifiers are restricted to the bounded ones. One can apply bounded model theory to study some problems in bounded arithmetic. Bounded arithmetic can be considered as a sub-theory of first-order Peano arithmetic in an extended language. Bounded arithmetic has some applications in computational complexity theory. There are already some related bounded model-theoretic concepts like bounded quantifier elimination and bounded model completeness which has been applied to bounded arithmetic and complexity theory. In this article, we review some known results and prove some new ones in bounded model theory and use them to obtain certain results in bounded arithmetic and complexity theory. In particular, we define the notion of bounded model companion and study its relations to some fundamental problems in complexity theory.}, keywords = {Bounded Arithmetic,Bounded formula,Bounded model complete,Bounded model companion,Bounded quantifier elimination}, title_fa = {نظریهٔ مدل محدود و برخی کاربردهای آن در حساب محدود}, abstract_fa = {نظریة مدل محدود را می‌توان بخشی از نظریة مدل دانست که هدف آن بررسی مفاهیم و نتایج نظریة مدل در یک زبان شامل یک رابطة ترتیبی است در حالتی که سورهای مورد بحث همگی از نوع محدود هستند. از نظریة مدل محدود می‌توان برای مطالعة مسائل مربوط به نظریة حساب محدود استفاده کرد. حساب محدود را می‌توان زیرنظریه‌ای از حساب مرتبة اول پئانو در زبانی گسترش‌یافته دانست. خود حساب محدود، کاربردهای فراوانی در نظریة پیچیدگی محاسبات دارد. با تعریف و مطالعة مفاهیم پایه‌ای نظریة مدل در حالت محدود مانند حذف سور محدود و مدل‌ کامل محدود، نتایج جالبی در نظریة مدل با کاربردهایی در نظریۀ پیچیدگی محاسبه و حساب محدود به دست آمده است. در این مقاله، ضمن مروری بر نتایج موجود در این زمینه، برخی مفاهیم و نتایج جدید را در این راستا ارائه می‌کنیم و ارتباط‌های آن‌ها را با برخی مسائل بنیادی در نظریة پیچیدگی محاسبه مطالعه می‌کنیم.}, keywords_fa = {حساب محدود,فرمول محدود,مدل کامل محدود,مدل همراه محدود,حذف سور محدود}, url = {https://logicalstudy.ihcs.ac.ir/article_7003.html}, eprint = {https://logicalstudy.ihcs.ac.ir/article_7003_e304194b8cfa8620fb9a200ac762e9c2.pdf} }