ออโตมาตาต้นไม้

Q: ข้อมูลสำคัญเกี่ยวกับ ออโตมาตาต้นไม้

ออ โตมาตาแบบต้นไม้ เป็นประเภทหนึ่งของ เครื่องจักรสถานะ ออโตมาตาแบบต้นไม้ทำงานกับ โครงสร้างแบบต้นไม้ แทนที่จะเป็น สตริง เหมือนเครื่องจักรสถานะทั่วไป

Q: ออโตมาตาแบบจากล่างขึ้นบนที่รับรายการบูลีน

โดยใช้การระบายสีเพื่อแยกแยะสมาชิกของ F และ Q และใช้ตัวอักษรเรียงลำดับ F = { false , true , nil , cons (.,.

ออโตมาตาแบบต้นไม้เป็นประเภทหนึ่งของเครื่องจักรสถานะออโตมาตาแบบต้นไม้ทำงานกับโครงสร้างแบบต้นไม้ แทนที่จะเป็น สตริงเหมือนเครื่องจักรสถานะทั่วไป

บทความต่อไปนี้กล่าวถึงออโตมาตาแบบแตกแขนงของต้นไม้ ซึ่งสอดคล้องกับภาษาปกติของต้นไม้

เช่นเดียวกับออโตมาตาแบบคลาสสิก ออโตมาตาต้นไม้จำกัด (FTA) สามารถเป็นออโตมาตาแบบกำหนดได้หรือไม่ก็ได้ ขึ้นอยู่กับวิธีที่ออโตมาตาประมวลผลต้นไม้ที่ป้อนเข้ามา ออโตมาตาต้นไม้จำกัดสามารถแบ่งออกได้เป็นสองประเภท: (ก) จากล่างขึ้นบน (ข) จากบนลงล่าง นี่เป็นประเด็นสำคัญ เพราะถึงแม้ว่าออโตมาตาต้นไม้แบบจากบนลงล่างและแบบจากล่างขึ้นบนที่ไม่กำหนด (ND) จะมีพลังในการแสดงออกที่เทียบเท่ากัน แต่ออโตมาตาแบบจากบนลงล่างที่กำหนดได้นั้นมีพลังน้อยกว่าออโตมาตาแบบจากล่างขึ้นบนที่กำหนดได้อย่างเคร่งครัด เนื่องจากคุณสมบัติของต้นไม้ที่ระบุโดยออโตมาตาต้นไม้แบบจากบนลงล่างที่กำหนดได้นั้นขึ้นอยู่กับคุณสมบัติของเส้นทางเท่านั้น (ออโตมาตาต้นไม้แบบจากล่างขึ้นบนที่กำหนดได้นั้นมีพลังเท่ากับออโตมาตาต้นไม้แบบไม่กำหนด)

คำจำกัดความ

ออโตมาตาต้นไม้จำกัดแบบล่างขึ้นบนบนFถูกกำหนดให้เป็นทูเปิล ( Q , F , Q , Δ) โดยที่Qคือเซตของสถานะ, Fคือตัวอักษรที่มีลำดับ (กล่าวคือ ตัวอักษรที่มีสัญลักษณ์ที่มีจำนวนสมาชิก ที่เกี่ยวข้อง ), $Q \subseteq Q$ คือเซตของสถานะสุดท้าย และ Δ คือเซตของกฎการเปลี่ยนสถานะในรูปแบบf ( q ( x ),..., q ( x )) → q ( f ( x ,..., x )) สำหรับ $f$ $\in$ $F$ ที่มีสมาชิก nตัว $,$ $q$ $,$ $q$ $\in$ $Q$ และx เป็นตัวแปรที่แสดงถึงต้นไม้ย่อย กล่าวคือ สมาชิกของ Δ คือกฎการเขียนใหม่จากโหนดที่มีรากของโหนดลูกเป็นสถานะ ไปยังโหนดที่มีรากเป็นสถานะ ดังนั้น สถานะของโหนดจึงถูกอนุมานจากสถานะของโหนดลูก

สำหรับn = 0 นั่นคือสำหรับสัญลักษณ์คงที่fคำจำกัดความของกฎการเปลี่ยนผ่านข้างต้นอ่านว่าf () → q ( f ()); บ่อยครั้งที่วงเล็บว่างจะถูกละเว้นเพื่อความสะดวก: f → q ( f ) เนื่องจากกฎการเปลี่ยนผ่านเหล่านี้สำหรับสัญลักษณ์คงที่ (ใบ) ไม่ต้องการสถานะ จึงไม่จำเป็นต้องมีสถานะเริ่มต้นที่กำหนดไว้อย่างชัดเจน ออโตมาตาต้นไม้แบบล่างขึ้นบนจะทำงานบนเทอมพื้นฐานเหนือFโดยเริ่มจากใบทั้งหมดพร้อมกันและเคลื่อนที่ขึ้นไป โดยเชื่อมโยงสถานะการทำงานจากQกับเทอมย่อยแต่ละเทอม เทอมจะได้รับการยอมรับหากรากของมันเชื่อมโยงกับสถานะที่ยอมรับจาก $Q$ ^{[ 1 ]}

ออ $โต$ มาตาต้นไม้จำกัดแบบบนลงล่างบนFถูกนิยามเป็นทูเปิล ( Q , F , Qi Δ) โดยมีความแตกต่างสองประการกับออโตมาตาต้นไม้แบบล่างขึ้นบน ประการแรก $Qi Q$ ซึ่งเป็นเซตของสถานะเริ่มต้น จะแทนที่ $ประการ$ การเปลี่ยนสถานะของมันมีทิศทางตรงกันข้าม: q ( f ( x1 ,..., xn → f ( q1 ( x1 ),..., qn ( xn สำหรับ $f$ $\in$ $F$ nตัวแปร $,$ $q$ $,$ $Qi$ $\in$ และXi ที่แสดงถึงต้นไม้ย่อย กล่าวคือ $ยัง$ โหนดที่มีรากของลูกเป็นสถานะ ออโตมาตาแบบบนลงล่างเริ่มต้นในสถานะเริ่มต้นบางส่วนที่รากและเคลื่อนที่ลงไปตามกิ่งก้านของต้นไม้ โดยเชื่อมโยงสถานะกับแต่ละเทอมย่อยแบบอุปนัยตลอดการเคลื่อนที่ ต้นไม้จะได้รับการยอมรับก็ต่อเมื่อทุกกิ่งก้านสามารถผ่านไปได้ด้วยวิธีนี้^[²^]

ออโตมาตาต้นไม้เรียกว่าแบบกำหนด (ย่อว่าDFTA ) หากไม่มีกฎสองข้อใดจาก Δ ที่มีด้านซ้ายเหมือนกัน มิฉะนั้นจะเรียกว่าแบบไม่กำหนด ( NFTA ) ^{[ 3 ]}ออโตมาตาต้นไม้แบบบนลงล่างที่ไม่กำหนดมีพลังการแสดงออกเช่นเดียวกับแบบล่างขึ้นบนที่ไม่กำหนด^{[ 4 ]}กฎการเปลี่ยนสถานะจะถูกกลับกัน และสถานะสุดท้ายจะกลายเป็นสถานะเริ่มต้น

ในทางตรงกันข้ามออโตมาตาต้นไม้แบบบนลงล่างเชิงกำหนด^{[ 5 ]}มีประสิทธิภาพน้อยกว่าออโตมาตาต้นไม้แบบล่างขึ้นบน เนื่องจากในออโตมาตาต้นไม้เชิงกำหนด กฎการเปลี่ยนสถานะสองข้อจะไม่เหมือนกันทางด้านซ้าย สำหรับออโตมาตาต้นไม้ กฎการเปลี่ยนสถานะคือกฎการเขียนใหม่ และสำหรับแบบบนลงล่าง ด้านซ้ายจะเป็นโหนดแม่ ดังนั้น ออโตมาตาต้นไม้แบบบนลงล่างเชิงกำหนดจะสามารถทดสอบคุณสมบัติของต้นไม้ที่เป็นจริงในทุกสาขาเท่านั้น เพราะการเลือกสถานะที่จะเขียนลงในแต่ละสาขาย่อยจะถูกกำหนดที่โหนดแม่ โดยไม่ทราบเนื้อหาของสาขาย่อย ตัวอย่างเช่น ถ้าFประกอบด้วยf , gและaซึ่งเป็น 2ary, 1ary และ 0ary ตามลำดับ เซตของเทอมทั้งหมดที่มีอินสแตนซ์พื้นฐานของf ( a , g ( x )) เป็นเทอมย่อย สามารถรับรู้ได้โดย DFTA แบบล่างขึ้นบน แต่ไม่ใช่โดย DFTA แบบบนลงล่าง^{[ a ]}^{[ 6 ]}

ออโตมาตาต้นไม้อนันต์ขยายออโตมาตาแบบบนลงล่างไปยังต้นไม้อนันต์ และสามารถใช้เพื่อพิสูจน์ความสามารถในการตัดสินใจของS2Sซึ่ง เป็นทฤษฎี ลำดับที่สองแบบเอกภาคที่มีผู้สืบทอดสองคน ออโตมาตาต้นไม้จำกัด (ไม่แน่นอนหากเป็นแบบบนลงล่าง) เพียงพอสำหรับ WS2S ^{[ 7 ]}

ตัวอย่าง

ออโตมาตาแบบจากล่างขึ้นบนที่รับรายการบูลีน

โดยใช้การระบายสีเพื่อแยกแยะสมาชิกของFและQและใช้ตัวอักษรเรียงลำดับF = { false , true , nil , cons (.,.) } โดยที่consมีจำนวนอาร์กิวเมนต์ 2 และสัญลักษณ์อื่นๆ ทั้งหมดมีจำนวนอาร์กิวเมนต์ 0 ออโตมาตาต้นไม้แบบล่างขึ้นบนที่ยอมรับเซตของรายการจำกัดทั้งหมดของค่าบูลีนสามารถกำหนดได้เป็น ( Q , F , Q , Δ) โดยที่ $Q$ $= {$ $Bool$ $,$ $BList$ $},$ $Q$ $= {$ $BList$ $}$ และ Δ ประกอบด้วยกฎต่างๆ

เท็จ	→	บูลีน (เท็จ )	(1)
จริง	→	บูลีน (จริง )	(2)
ไม่มี	→	บลิสต์ (ไม่มี )	(3) และ
cons ( Bool (x ), BList (x ))	→	BList ( cons (x ,x ))	(4).

ในตัวอย่างนี้ กฎสามารถเข้าใจได้โดยสัญชาตญาณว่าเป็นการกำหนดประเภทให้กับแต่ละเทอมในลักษณะจากล่างขึ้นบน เช่น กฎ (4) สามารถอ่านได้ว่า "เทอมcons ( x , x ) มีประเภทBListโดยมีเงื่อนไขว่าx และx มีประเภทBoolและBListตามลำดับ" ตัวอย่างการทำงานที่ยอมรับได้คือ

	ข้อเสีย (	เท็จ ,	ข้อเสีย (	จริง ,	ไม่มี	))
⇒	ข้อเสีย (	เท็จ ,	ข้อเสีย (	จริง ,	บลิสต์ (ไม่มี )	))	โดย (3)
⇒	ข้อเสีย (	เท็จ ,	ข้อเสีย (	บูลีน (จริง )	บลิสต์ (ไม่มี )	))	โดย (2)
⇒	ข้อเสีย (	เท็จ ,	รายชื่อ B (ข้อเสีย (	จริง ,	ไม่มี	)))	โดย (4)
⇒	ข้อเสีย (	บูล (เท็จ )	รายชื่อ B (ข้อเสีย (	จริง ,	ไม่มี	)))	โดย (1)
⇒	รายชื่อ B (ข้อเสีย (	เท็จ ,	ข้อเสีย (	จริง ,	ไม่มี	)))	โดย (4) ยอมรับ

เปรียบเทียบกับการอนุมานคำศัพท์เดียวกันจากไวยากรณ์ต้นไม้ปกติที่สอดคล้องกับออโตมาตอน ซึ่งแสดงไว้ในไวยากรณ์ต้นไม้ปกติ#ตัวอย่าง

ตัวอย่างการปฏิเสธการทำงานคือ

	ข้อเสีย (	เท็จ ,	จริง	)
⇒	ข้อเสีย (	เท็จ ,	บูลีน (จริง )	)	โดย (1)
⇒	ข้อเสีย (	บูล (เท็จ )	บูลีน (จริง )	)	โดย (2) ไม่มีกฎเพิ่มเติมที่ใช้ได้

โดยสัญชาตญาณแล้ว นี่สอดคล้องกับคำว่าcons ( false , true ) ที่ไม่ได้กำหนดประเภทไว้อย่างถูกต้อง

ออโตมาตาแบบบนลงล่างที่ยอมรับจำนวนทวีคูณของ 3 ในระบบเลขฐานสอง

(ก)

(ข)

(ค)

(ง)

กฎไวยากรณ์สตริง

การเปลี่ยนสถานะของออโตมาตาสตริง

การเปลี่ยนสถานะของออโตมาตาต้นไม้

กฎไวยากรณ์ต้นไม้

0
1
2
3
4
5
6

ส	→	ε
ส	→	0 S
ส	→	1 S
เอส	→	0 S
เอส	→	1 S
เอส	→	0 S
เอส	→	1 S


δ( S , 0 )	= S
δ( S , 1 )	= S
δ( S , 0 )	= S
δ( S , 1 )	= S
δ( S , 0 )	= S
δ( S , 1 )	= S

S (ศูนย์ )	→	ไม่มี
S ( 0 (x))	→	0 ( S (x))
S ( 1 (x))	→	1 ( S (x))
S ( 0 (x))	→	0 ( S (x))
S ( 1 (x))	→	1 ( S (x))
S ( 0 (x))	→	0 ( S (x))
S ( 1 (x))	→	1 ( S (x))

ส	→	ไม่มี
ส	→	0 ( S )
ส	→	1 ( S )
เอส	→	0 ( S )
เอส	→	1 ( S )
เอส	→	0 ( S )
เอส	→	1 ( S )

โดยใช้การระบายสีแบบเดียวกับข้างต้น ตัวอย่างนี้แสดงให้เห็นว่าออโตมาตาต้นไม้ขยายความของออโตมาตาสตริงธรรมดาอย่างไร ออโตมาตาสตริงเชิงกำหนดแบบจำกัดที่แสดงในภาพยอมรับสตริงทั้งหมดของตัวเลขไบนารีที่แสดงถึงพหุคูณของ 3 โดยใช้แนวคิดจากออโตมาตาเชิงกำหนดแบบจำกัด#คำจำกัดความอย่างเป็นทางการมันถูกกำหนดโดย:

เซตสถานะQ คือ { S , S , S }
โดยที่ตัวอักษรที่ป้อนเข้ามาคือ { 0 , 1 }
สถานะเริ่มต้นคือS
เซตของสถานะสุดท้ายคือ { S } และ
การเปลี่ยนสถานะเป็นไปตามที่แสดงในคอลัมน์ (B) ของตาราง

ในการตั้งค่าออโตมาตาต้นไม้ ตัวอักษรอินพุตจะถูกเปลี่ยนแปลง โดยที่สัญลักษณ์0และ1เป็นแบบเอกภาค และใช้สัญลักษณ์ศูนย์ เช่นnilสำหรับใบของต้นไม้ ตัวอย่างเช่น สตริงไบนารี " 110 " ในการตั้งค่าออโตมาตาสตริงจะสอดคล้องกับเทอม " 1 ( 1 ( 0 ( nil )))" ในการตั้งค่าออโตมาตาต้นไม้ ด้วยวิธีนี้ สตริงสามารถขยายไปเป็นต้นไม้หรือเทอมได้ ออโตมาตาต้นไม้จำกัดแบบบนลงล่างที่ยอมรับเซตของเทอมทั้งหมดที่สอดคล้องกับพหุคูณของ 3 ในสัญกรณ์สตริงไบนารีจะถูกกำหนดโดย:

โดยที่เซตสถานะQ ยังคงเป็น { S , S , S }
ตัวอักษรอินพุตที่จัดลำดับแล้วคือ { 0 , 1 , nil } โดยที่Arity ( 0 )= Arity ( 1 )=1 และArity ( nil )=0 ตามที่ได้อธิบายไว้
โดยเซตของสถานะเริ่มต้นคือ { S } และ
การเปลี่ยนสถานะเป็นไปตามที่แสดงในคอลัมน์ (C) ของตาราง

ตัวอย่างเช่น ต้นไม้ " 1 ( 1 ( 0 ( nil )))" ได้รับการยอมรับโดยการทำงานของออโตมาตาต้นไม้ดังต่อไปนี้:

	S (	1 (		1 (			ไม่มี	))))
⇒		1 (	S (	1 (			ไม่มี	))))	โดย 2
⇒		1 (		1 (	S (		ไม่มี	))))	โดย 4
⇒		1 (		1 (		S (	ไม่มี	))))	โดย 1
⇒		1 (		1 (			ไม่มี	)))	โดย 0

ในทางตรงกันข้าม เทอม " 1 ( 0 ( nil ))" นำไปสู่การทำงานของออโตมาตาที่ไม่ยอมรับดังต่อไปนี้:

⇒ S (	1 (			ไม่มี	)))
⇒	1 (	S (		ไม่มี	))))	โดย 2
⇒	1 (		S (	ไม่มี	))))	โดย 3 ไม่มีกฎเพิ่มเติมที่ใช้บังคับ

เนื่องจากไม่มีสถานะเริ่มต้นอื่นใดนอกจากS ที่จะใช้เริ่มต้นการทำงานของออโตมาตอน ดังนั้นเทอม " 1 ( 0 ( nil ))" จึงไม่ได้รับการยอมรับจากออโตมาตอนต้นไม้

เพื่อวัตถุประสงค์ในการเปรียบเทียบ ตารางในคอลัมน์ (A) และ (D) แสดงไวยากรณ์ปกติ (สตริง)และไวยากรณ์ต้นไม้ปกติตามลำดับ โดยแต่ละไวยากรณ์ยอมรับภาษาเดียวกันกับไวยากรณ์อัตโนมัติที่เทียบเท่ากัน

คุณสมบัติ

การจดจำ

สำหรับออโตมาตาแบบจากล่างขึ้นบน เทอมพื้นฐานt (นั่นคือ ต้นไม้) จะได้รับการยอมรับหากมีการลดรูปที่เริ่มต้นจากtและสิ้นสุดที่q ( t ) โดยที่qเป็นสถานะสุดท้าย สำหรับออโตมาตาแบบจากบนลงล่าง เทอมพื้นฐานtจะได้รับการยอมรับหากมีการลดรูปที่เริ่มต้นจากq ( t ) และสิ้นสุดที่tโดยที่qเป็นสถานะเริ่มต้น

ภาษาต้นไม้L ( A ) ที่ยอมรับหรือรู้จักโดยออโตมาตาต้นไม้Aคือเซตของเงื่อนไขพื้นฐานทั้งหมดที่A ยอมรับ เซตของเงื่อนไขพื้นฐานจะรู้จักได้ก็ต่อเมื่อมีออโตมาตาต้นไม้ที่ยอมรับเซตนั้น

โฮโมมอร์ฟิซึมต้นไม้เชิงเส้น (นั่นคือ รักษาจำนวนอาร์กิวเมนต์) จะรักษาความสามารถในการจดจำ^{[ 8 ]}

ความสมบูรณ์และการลดลง

ออโตมาตาต้นไม้จำกัดแบบไม่กำหนดจะสมบูรณ์ก็ต่อเมื่อมีกฎการเปลี่ยนสถานะอย่างน้อยหนึ่งกฎที่ใช้ได้สำหรับทุกชุดสัญลักษณ์-สถานะที่เป็นไปได้ สถานะqสามารถเข้าถึงได้ก็ต่อเมื่อมีเทอมพื้นฐานt อยู่ เช่นนั้นจะมีการลดรูปจากtไปยังq ( t ) NFTA จะถูกลดรูปก็ต่อเมื่อสถานะทั้งหมดสามารถเข้าถึงได้^{[ 9 ]}

การสูบเลมมา

เทอมพื้นฐานt ที่ มีขนาดใหญ่พอสมควร^{[ 10 ]}ในภาษาต้นไม้ที่รู้จักLสามารถแบ่งออกเป็นสามส่วนในแนวตั้ง^[¹¹^]โดยที่การทำซ้ำโดยพลการ ("การสูบ") ของส่วนกลางจะทำให้เทอมที่ได้ยังคงอยู่ในL ^[¹²^]^[¹³^]

สำหรับภาษาของลิสต์จำกัดทั้งหมดของค่าบูลีนจากตัวอย่างข้างต้น เทอมทั้งหมดที่เกินขีดจำกัดความสูงk = 2 สามารถถูกเพิ่มเข้าไปได้ เนื่องจากเทอมเหล่านั้นจำเป็นต้องมีคำว่าcons ปรากฏอยู่ ตัวอย่างเช่น

ข้อเสีย (เท็จ ,	cons ( true , nil )	)	,
ข้อเสีย (เท็จ ,ข้อเสีย (เท็จ ,	cons ( true , nil )	))	,
ข้อเสีย (เท็จ ,ข้อเสีย (เท็จ ,ข้อเสีย (เท็จ ,	cons ( true , nil )	)))	...

ทั้งหมดล้วนอยู่ในภาษานั้น

การปิด

คลาสของภาษาต้นไม้ที่สามารถจดจำได้นั้นปิดภายใต้การรวม การเติมเต็ม และการตัดกัน^{[ 14 ]}

ทฤษฎีบทมายฮิลล์-เนโรด

ความสอดคล้องบนเซตของต้นไม้ทั้งหมดเหนือตัวอักษรลำดับFคือความสัมพันธ์สมมูลที่ $u \equiv v$ และ ... และ $u \equiv v$ หมายความว่า $f (u,..., u) \equiv f (v,..., v)$ สำหรับทุก $f \in F$ ความสัมพันธ์นี้จะมีดัชนีจำกัดหากจำนวนชั้นสมมูลของมันมีจำกัด

สำหรับภาษาต้นไม้Lที่ กำหนดให้ ความสอดคล้องสามารถนิยามได้โดย $u \equiv v$ ถ้า $C [u] \in L \Leftrightarrow C [v] \in L$ สำหรับแต่ละบริบทC

ทฤษฎีบทMyhill–Nerodeสำหรับออโตมาตาต้นไม้ระบุว่าข้อความสามข้อความต่อไปนี้เทียบเท่ากัน: ^{[ 15 ]}

Lเป็นภาษาต้นไม้ที่สามารถจดจำได้
Lคือการรวมกันของชั้นสมมูลบางชั้นของการสมภาคที่มีดัชนีจำกัด
ความสัมพันธ์ $\equiv$ เป็นความสอดคล้องที่มีดัชนีจำกัด

ประวัติศาสตร์

ตามที่ Engelfriet กล่าว^{[ 16 ]}ออโตมาตาต้นไม้จำกัดแบบล่างขึ้นบนถูกคิดค้นขึ้นประมาณปี 1965 โดยอิสระโดย( Doner 1965 ) ( Doner 1970 )และ( Thatcher & Wright 1968 )และในเวลาต่อมาโดย( Pair & Quere 1968 )ออโตมาตาต้นไม้จำกัดแบบบนลงล่างได้รับการแนะนำโดย( Rabin 1969 )และ( Magidor & Moran 1969 )และไวยากรณ์ต้นไม้ปกติโดย( Brainerd 1969 )

ในวารสารNotices of the AMS ฉบับเดือนพฤศจิกายน พ.ศ. 2508 มี บทคัดย่อสองเรื่อง( Doner 1965 )และ( Thatcher & Wright 1965 )ซึ่งทั้งสองเรื่องได้รับการส่งมาเมื่อวันที่ 17 กันยายน บทคัดย่อทั้งสองเรื่องอ้างอิงถึงกันและกัน โดยกล่าวว่าออโตมาตาต้นไม้จำกัดได้รับการค้นพบโดยอิสระ ในขณะที่ Thatcher & Wright ยอมรับว่าการประยุกต์ใช้เพื่อพิสูจน์ความสามารถในการตัดสินใจของ "ทฤษฎีลำดับที่สองแบบอ่อนของ ฟังก์ชันผู้สืบทอด kตัว" นั้น Doner เป็นผู้ค้นพบก่อน

ดูเพิ่มเติม

ทฤษฎีบทของคูร์เซลล์ - การประยุกต์ใช้เครื่องจักรสถานะต้นไม้เพื่อพิสูจน์ทฤษฎีบทเชิงอัลกอริทึมเกี่ยวกับกราฟ
ทรานสดิวเซอร์แบบต้นไม้ - ขยายออโตมาตาแบบต้นไม้ในลักษณะเดียวกับที่ทรานสดิวเซอร์แบบคำขยายออโตมาตาแบบคำ
ออโตมาตาต้นไม้สลับ
ออโตมาตาต้นไม้อนันต์

หมายเหตุ

↑ Comon et al. 2008 , ส่วนที่ 1.1, หน้า 20.
↑ Comon et al. 2008 , ส่วนที่ 1.6, หน้า 38.
↑ Comon et al. 2008 , ส่วนที่ 1.1, หน้า 23.
↑คอมมอน และคณะ 2551 , ส่วน. 1.6 ทฤษฎีบท 1.6.1 หน้า 38.
↑ในความหมายที่เคร่งครัดแล้ว ออโตมาตาแบบท็อปดาวน์เชิงกำหนดไม่ได้ถูกนิยามโดย Comon et al. (2008)แต่มีการนำไปใช้ในนั้น (ส่วนที่ 1.6 ข้อเสนอ 1.6.2 หน้า 38) โดยยอมรับคลาสของภาษาต้นไม้แบบปิดเส้นทาง (ส่วนที่ 1.8 แบบฝึกหัด 1.6 หน้า 43-44)
↑ Comon et al. 2008 , ส่วนที่ 1.8, แบบฝึกหัด 1.2 และ 1.6.3, หน้า 43-44.
↑ Morawietz, Frank; Cornell, Tom (1997-07-07). "การแสดงข้อจำกัดด้วยออโตมาตา" . รายงานการประชุมประจำปีครั้งที่ 35 ของสมาคมภาษาศาสตร์เชิงคำนวณ - . ACL '98/EACL '98. สหรัฐอเมริกา: สมาคมภาษาศาสตร์เชิงคำนวณ. หน้า468– 475. doi : 10.3115/976909.979677 .
↑แนวคิดเรื่องโฮโมมอร์ฟิซึมของต้นไม้ใน งานของ Comon et al. (2008 , ส่วนที่ 1.4, ทฤษฎีบท 1.4.3, หน้า 31-32)นั้นมีขอบเขตทั่วไปมากกว่าบทความเรื่อง "โฮโมมอร์ฟิซึมของต้นไม้"
↑ Comon et al. 2008 , ส่วนที่ 1.1, หน้า 23-24.
↑ในทางทฤษฎี:ความสูง ( t ) > kโดยที่ k > 0 ขึ้นอยู่กับ L เท่านั้น ไม่ขึ้นอยู่กับ t
↑ในทางทฤษฎี: มีบริบท C [.], บริบทที่ไม่ธรรมดา $C' [.]$ และเทอมพื้นฐาน uที่ $t = C [C' [u]]$ "บริบท" C [.] คือต้นไม้ที่มีรูหนึ่งรู (หรือในทำนองเดียวกัน เทอมที่มีการปรากฏของตัวแปรหนึ่งตัวเพียงครั้งเดียว) บริบทเรียกว่า "ธรรมดา" ถ้าต้นไม้ประกอบด้วยโหนดรูเพียงอย่างเดียว (หรือในทำนองเดียวกัน ถ้าเทอมเป็นเพียงตัวแปร) สัญลักษณ์ C [ t ] หมายถึงผลลัพธ์ของการแทรกต้นไม้ tลงในรูของ C [.] (หรือในทำนองเดียวกัน การ กำหนดค่าตัวแปรให้กับ t ) Comon et al. 2008 , หน้า17ให้คำจำกัดความอย่างเป็นทางการ
↑ในทางรูปแบบ: $C [C' n [u]] \in L$ สำหรับทุก n ≥ 0 สัญลักษณ์ C ⁿ [.] หมายถึงผลลัพธ์ของการซ้อนสำเนา C [.] จำนวน nชุดเข้าด้วยกัน ดู Comon et al. 2008 ,หน้า17
↑ Comon et al. 2008 , ส่วนที่ 1.2, หน้า 29.
↑คอมมอน และคณะ 2551 , ส่วน. 1.3 ทฤษฎีบท 1.3.1 หน้า 30.
↑ Comon et al. 2008 , ส่วนที่ 1.5, หน้า 36.
↑ Engelfriet 1975 .

↑ให้ Q = { q , q , q , q } โดยมีความหมายอย่างไม่เป็นทางการ ว่า q : "เห็น a " , q : "เห็น g บางตัว (...)", q : "เห็น fบางตัว( a , g (...))", q : "ไม่เห็นสิ่งเหล่านั้นเลย" ให้ Q = { q } เป็นเซตของสถานะสุดท้าย กฎการเปลี่ยนสถานะ Δ = { a → q ( a ), f ( q ( x ), q ( y )) → q ( f ( x , y )) }∪ { g ( q ( x )) → q ( g ( x )) }∪ { f ( q ( x ), q ( y )) → q ( f ( x , y )), f ( q ( x ), q ( y )) → q ( f ( x , y )), : q ∈ Q }∪ { g ( q ( x )) → q ( g ( x )), : q ∈ Q \ { q } }∪ { f ( q ( x ), q ( y )) → q ( f ( x , y )), f ( q ( x ), q ( y )) → q ( f (x , y )) : q ∈ Q } รักษาความหมายที่ไม่เป็นทางการของสถานะต่างๆ ในระหว่างการเคลื่อนที่จากล่างขึ้นบนผ่านต้นไม้tและยอมรับtก็ต่อเมื่อtมีต้นไม้ย่อยf ( a , g (...)) อยู่ที่ใดที่หนึ่ง

ลิงก์ภายนอก

การนำไปใช้

Grappa ( เก็บถาวรเมื่อวันที่ 1 กุมภาพันธ์ 2019 ที่Wayback Machine ) - ไลบรารีออโตมาตาต้นไม้แบบจัดอันดับและไม่จัดอันดับ (OCaml)
Timbuk - เครื่องมือสำหรับการวิเคราะห์การเข้าถึงและการคำนวณออโตมาตาต้นไม้ (OCaml)
LETHAL - ไลบรารีสำหรับทำงานกับต้นไม้จำกัดและออโตมาตาแบบเฮดจ์ (Java)
ไลบรารีออโตมาตาต้นไม้ที่ตรวจสอบด้วยเครื่อง (Isabelle [OCaml, SML, Haskell])
VATA - ไลบรารีสำหรับการจัดการออโตมาตาต้นไม้แบบไม่กำหนดผลลัพธ์อย่างมีประสิทธิภาพ (C++)

[FOOTNOTEComon_et_al.2008sect._1.1,_p._20-1] Comon et al. 2008 , ส่วนที่ 1.1, หน้า 20.

[FOOTNOTEComon_et_al.2008sect._1.6,_p._38-2] Comon et al. 2008 , ส่วนที่ 1.6, หน้า 38.

[FOOTNOTEComon_et_al.2008sect._1.1,_p._23-3] Comon et al. 2008 , ส่วนที่ 1.1, หน้า 23.

[FOOTNOTEComon_et_al.2008sect._1.6,_theorem_1.6.1,_p._38-4] คอมมอน และคณะ 2551 , ส่วน. 1.6 ทฤษฎีบท 1.6.1 หน้า 38.

[5] ในความหมายที่เคร่งครัดแล้ว ออโตมาตาแบบท็อปดาวน์เชิงกำหนดไม่ได้ถูกนิยามโดย Comon et al. (2008)แต่มีการนำไปใช้ในนั้น (ส่วนที่ 1.6 ข้อเสนอ 1.6.2 หน้า 38) โดยยอมรับคลาสของภาษาต้นไม้แบบปิดเส้นทาง (ส่วนที่ 1.8 แบบฝึกหัด 1.6 หน้า 43-44)

[FOOTNOTEComon_et_al.2008sect._1.8,_exercise_1.2_and_1.6.3,_p.43-44-7] Comon et al. 2008 , ส่วนที่ 1.8, แบบฝึกหัด 1.2 และ 1.6.3, หน้า 43-44.

[8] Morawietz, Frank; Cornell, Tom (1997-07-07). "การแสดงข้อจำกัดด้วยออโตมาตา" . รายงานการประชุมประจำปีครั้งที่ 35 ของสมาคมภาษาศาสตร์เชิงคำนวณ - . ACL '98/EACL '98. สหรัฐอเมริกา: สมาคมภาษาศาสตร์เชิงคำนวณ. หน้า468– 475. doi : 10.3115/976909.979677 .

[9] แนวคิดเรื่องโฮโมมอร์ฟิซึมของต้นไม้ใน งานของ Comon et al. (2008 , ส่วนที่ 1.4, ทฤษฎีบท 1.4.3, หน้า 31-32)นั้นมีขอบเขตทั่วไปมากกว่าบทความเรื่อง "โฮโมมอร์ฟิซึมของต้นไม้"

[FOOTNOTEComon_et_al.2008sect._1.1,_p._23-24-10] Comon et al. 2008 , ส่วนที่ 1.1, หน้า 23-24.

[11] ในทางทฤษฎี:ความสูง ( t ) > kโดยที่ k > 0 ขึ้นอยู่กับ L เท่านั้น ไม่ขึ้นอยู่กับ t

[12] ในทางทฤษฎี: มีบริบท C [.], บริบทที่ไม่ธรรมดา $C' [.]$ และเทอมพื้นฐาน uที่ $t = C [C' [u]]$ "บริบท" C [.] คือต้นไม้ที่มีรูหนึ่งรู (หรือในทำนองเดียวกัน เทอมที่มีการปรากฏของตัวแปรหนึ่งตัวเพียงครั้งเดียว) บริบทเรียกว่า "ธรรมดา" ถ้าต้นไม้ประกอบด้วยโหนดรูเพียงอย่างเดียว (หรือในทำนองเดียวกัน ถ้าเทอมเป็นเพียงตัวแปร) สัญลักษณ์ C [ t ] หมายถึงผลลัพธ์ของการแทรกต้นไม้ tลงในรูของ C [.] (หรือในทำนองเดียวกัน การ กำหนดค่าตัวแปรให้กับ t ) Comon et al. 2008 , หน้า17ให้คำจำกัดความอย่างเป็นทางการ

[13] ในทางรูปแบบ: $C [C' n [u]] \in L$ สำหรับทุก n ≥ 0 สัญลักษณ์ C ⁿ [.] หมายถึงผลลัพธ์ของการซ้อนสำเนา C [.] จำนวน nชุดเข้าด้วยกัน ดู Comon et al. 2008 ,หน้า17

[FOOTNOTEComon_et_al.2008sect._1.2,_p._29-14] Comon et al. 2008 , ส่วนที่ 1.2, หน้า 29.

[FOOTNOTEComon_et_al.2008sect._1.3,_theorem_1.3.1,_p._30-15] คอมมอน และคณะ 2551 , ส่วน. 1.3 ทฤษฎีบท 1.3.1 หน้า 30.

[FOOTNOTEComon_et_al.2008sect._1.5,_p_.36-16] Comon et al. 2008 , ส่วนที่ 1.5, หน้า 36.

[FOOTNOTEEngelfriet1975-17] Engelfriet 1975 .

[6] ให้ Q = { q , q , q , q } โดยมีความหมายอย่างไม่เป็นทางการ ว่า q : "เห็น a " , q : "เห็น g บางตัว (...)", q : "เห็น fบางตัว( a , g (...))", q : "ไม่เห็นสิ่งเหล่านั้นเลย" ให้ Q = { q } เป็นเซตของสถานะสุดท้าย กฎการเปลี่ยนสถานะ Δ = { a → q ( a ), f ( q ( x ), q ( y )) → q ( f ( x , y )) }∪ { g ( q ( x )) → q ( g ( x )) }∪ { f ( q ( x ), q ( y )) → q ( f ( x , y )), f ( q ( x ), q ( y )) → q ( f ( x , y )), : q ∈ Q }∪ { g ( q ( x )) → q ( g ( x )), : q ∈ Q \ { q } }∪ { f ( q ( x ), q ( y )) → q ( f ( x , y )), f ( q ( x ), q ( y )) → q ( f (x , y )) : q ∈ Q } รักษาความหมายที่ไม่เป็นทางการของสถานะต่างๆ ในระหว่างการเคลื่อนที่จากล่างขึ้นบนผ่านต้นไม้tและยอมรับtก็ต่อเมื่อtมีต้นไม้ย่อยf ( a , g (...)) อยู่ที่ใดที่หนึ่ง

[ 1 ]

[

[ 3 ]

[ 4 ]

[ 5 ]

[ a ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[

[

[

[ 14 ]

[ 15 ]

[ 16 ]