We study definability of languages

We study definability of languages in arithmetic and the free monoid by bounded versions of fixed-point and transitive-closure logic. In particular we give logical characterisations of complexity classes C by showing that a languages belongs to C if and only if it is definable in either arithmetic or the free monoid by a formulas of a certain logic. We investigate in which cases the bounds of fixed-point operators may be omitted. Finally, a general translation of results from descriptive complexity to the approach described in this paper is presented.

ผลลัพธ์ (ไทย) 1:

เราเรียน definability ภาษาเลขคณิตและ monoid ฟรีกี่รุ่นตรรกะเงินตรา และ ปิดสกรรมกริยา โดยเฉพาะอย่างยิ่ง เราให้ characterisations ตรรกะของ C ซับซ้อน โดยแสดงว่า ภาษาที่เป็นของ C ถ้าและเฉพาะถ้ากำหนดได้ในทางคณิตศาสตร์หรือ monoid ฟรี โดยสูตรของตรรกะที่แน่นอน เราตรวจสอบในกรณีที่อาจข้ามขอบเขตของตัวดำเนินเรื่อง ในที่สุด การแปลทั่วไปผลลัพธ์จากความซับซ้อนที่อธิบายวิธีที่อธิบายไว้ในเอกสารนี้จะแสดง

ผลลัพธ์ (ไทย) 2:

เราศึกษา definability ของภาษาในการคำนวณและหนังสือฟรีโดยรุ่นขอบเขตของจุดคงที่และตรรกะสกรรมกริยา-​​ปิด โดยเฉพาะอย่างยิ่งเราให้ characterisations ตรรกะของการเรียนความซับซ้อน C โดยแสดงให้เห็นว่าภาษาเป็นของ C และถ้าหากมันเป็นกำหนดทั้งในทางคณิตศาสตร์หรือหนังสือฟรีโดยสูตรของตรรกะบางอย่าง เราจะตรวจสอบในกรณีที่ขอบเขตของผู้ประกอบการจุดคงที่อาจถูกมองข้าม สุดท้ายแปลทั่วไปของผลที่ได้จากความซับซ้อนบรรยายวิธีการอธิบายไว้ในบทความนี้จะนำเสนอ

ผลลัพธ์ (ไทย) 3:

เราเรียนคณิตศาสตร์และภาษาใน definability ฟรีหนังสือโดยจำกัดรุ่น เรื่องการปิดและตรรกะ โดยเฉพาะเราให้เหตุผล characterisations ความซับซ้อนของคลาส C โดยแสดงให้เห็นว่าภาษาเป็นของ C ถ้าและเพียงถ้ามันคือการกำหนดในค่าหรือฟรีหนังสือโดยสูตรของตรรกะบางอย่างเราสืบคดีที่ขอบเขตของเรื่องที่ผู้ประกอบการอาจจะละเว้นได้ ในที่สุด , แปลเอกสารทั่วไปของผลลัพธ์จากความซับซ้อนอธิบายวิธีการที่อธิบายไว้ในบทความนี้จะนำเสนอ