کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428814 | 686938 | 2016 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A note on the size of prenex normal forms
ترجمه فارسی عنوان
یادداشتی در مورد اندازه اشکال طبیعی prenex
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم ها؛ روش های رسمی؛ منطق در علوم کامپیوتر؛ اندازه فرمول و مختصر
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
• Prenex normal forms (PNF) of logical sentences are often used computational logic.
• Converting to PNF with the standard method can lead to exponentially larger formulas.
• We show that the conversion is possible with polynomial growth.
The textbook method for converting a first-order logic formula to prenex normal form potentially leads to an exponential growth of the formula size, if the formula is allowed to use all of the classical logical connectives ∧, ∨, →, ↔, ¬. This note presents a short proof which shows that the conversion is possible with polynomial growth of the formula size.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 116, Issue 7, July 2016, Pages 443–446
Journal: Information Processing Letters - Volume 116, Issue 7, July 2016, Pages 443–446
نویسندگان
Frederik Harwath,