AbstractEvery graph property expres

Abstract
Every graph property expressible in monadic second-order (MSO) logic, can be
checked in linear time on graphs of bounded tree-width by means of finite automata
running on terms denoting tree-decompositions. Implementing these automata is
difficult because of their huge sizes. Fly-automata (FA) are deterministic automata
that compute the necessary states and transitions when running (instead of looking
into tables); they overcome this difficulty. Previously, we constructed FA to check
MSO properties of graphs of bounded clique-width. An MSO property with edge
quantifications (called an MSO2 property) is an MSO property of the incidence
graph and, graphs of tree-width k have incidence graphs of clique-width O(k). Our
existing constructions can be used for MSO2 properties of graphs of bounded treewidth.
We examine concrete aspects of this adaptation.

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

บทคัดย่อคุณสมบัติกราฟทุก expressible ใน monadic ลำดับสอง (MSO) ตรรกะ สามารถการตรวจสอบในเวลาเชิงเส้นกราฟของความกว้างของต้นไม้ยาม โดยยูโรโกะจำกัดทำงานบนเงื่อนไขแสดงต้นไม้ decompositions ใช้ยูโรโกะเหล่านี้คือยากเนื่องจากขนาดใหญ่ บินยูโรโกะ (FA) เป็น deterministic ยูโรโกะที่คำนวณอเมริกาจำเป็นและการเปลี่ยนเมื่อใช้งาน (แทนที่จะมองตาราง); พวกเขาเอาชนะอุปสรรค ก่อนหน้านี้ เราสร้าง FA เพื่อตรวจสอบMSO คุณสมบัติของกราฟของความกว้างของกลุ่มยาม คุณสมบัติการ MSO ขอบquantifications (เรียกว่าเป็น MSO2 แห่ง) เป็นทรัพย์สิน MSO ของอุบัติการณ์กราฟและ กราฟของความกว้างของต้นไม้ k มีกราฟแสดงอุบัติการณ์ของความกว้างของกลุ่ม O(k) ของเราก่อสร้างที่มีอยู่สามารถใช้สำหรับการ MSO2 คุณสมบัติของกราฟของยาม treewidthเราตรวจสอบคอนกรีตด้านการปรับตัวนี้

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

บทคัดย่อทรัพย์สินกราฟแสดงได้ในทุกเอกที่สองสั่งซื้อ (MSO) ตรรกะสามารถตรวจสอบในเวลาเชิงเส้นกราฟของต้นไม้ล้อมรอบกว้างโดยวิธีการของออโตจำกัดการทำงานในแง่ที่แสดงถึงต้นไม้สลายตัว การใช้ออโตเหล่านี้เป็นเรื่องยากเพราะขนาดใหญ่ของพวกเขา บินออโต (เอฟเอ) มีกำหนดออโตที่คำนวณรัฐที่จำเป็นและการเปลี่ยนเมื่อใช้(แทนที่จะมองลงในตาราง); พวกเขาเอาชนะความยากลำบากนี้ ก่อนหน้านี้เราสร้างเอฟเอในการตรวจสอบคุณสมบัติของกราฟ MSO ของก๊กที่มีความกว้างล้อมรอบ สถานที่ให้บริการ MSO กับขอบquantifications (เรียกว่าทรัพย์สิน MSO2) เป็นสถานที่ให้บริการ MSO ของอุบัติการณ์กราฟและกราฟของk ต้นไม้มีความกว้างกราฟอุบัติการณ์ของก๊กที่มีความกว้าง O (k) เราปลูกสร้างที่มีอยู่สามารถนำมาใช้สำหรับ MSO2 คุณสมบัติของกราฟของ treewidth จำกัด . เราตรวจสอบทุกแง่มุมที่เป็นรูปธรรมของการปรับตัวนี้