PRODUCTS OF TREE LANGUAGESAbstractS

PRODUCTS OF TREE LANGUAGES
Abstract
Sets of terms of type τ are called tree languages. The tree language product is an
important operation defined on sets of tree languages which maps recognizable
tree languages to recognizable tree languages. This tree language product can
be described by the superposition of sets of terms. Based on the superposition
operation we define a binary associative operation. In the theory of tree languages
the product of languages is called the z-product. The aim of this paper is to study
properties of the arising semigroups and its subsemigroups. We are especially
interested in idempotent and regular elements, Green’s relations L and R, in
constant, left-zero and right-zero subsemigroups and in rectangular bands. Since
the set of all recognizable tree languages of a given type is closed under the
language product, the set of all recognizable tree languages forms a subsemigroup
of the semigroup of all tree languages which contains the semigroup of all finite
tree languages of the given type. Recognizable tree languages can be generated by
regular tree grammars. We characterize all idempotent elements in the semigroup
of all recognizable tree languages of type τ by properties of regular grammars.
The iteration of the language product plays the role of the Kleene-∗-operation in
the theory of formal languages and is one of the regular operations.
Keywords: Tree languages; product of tree languages; regular elements;
recognizable tree languages; Green’s relations; right-zero semigroups; leftzero
semigroups; rectangular bands.
AMS Subject Classification: 08C99, 20M17

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

ผลิตภัณฑ์ของต้นไม้ภาษาบทคัดย่อชุดของเงื่อนไขการτชนิดเรียกว่าภาษาต้น ต้นไม้ภาษาเป็นการการดำเนินงานที่สำคัญที่กำหนดไว้ในชุดภาษาต้นไม้ซึ่งแผนที่รู้จักภาษาต้นไม้ต้นไม้รู้จักภาษา ต้นไม้ภาษาได้ที่นี่สามารถอธิบาย โดย superposition ของชุดของเงื่อนไข คะแนนเฉลียจากการ superpositionการดำเนินการที่เรากำหนดดำเนินการเชื่อมโยงแบบไบนารี ในทฤษฎีของต้นไม้ภาษาผลิตภัณฑ์ของภาษาเรียกว่า z-ผลิตภัณฑ์ จุดประสงค์ของเอกสารนี้คือการ ศึกษาคุณสมบัติของ semigroups เกิดและ subsemigroups ของ เราเป็นอย่างยิ่งสนใจ idempotent และองค์ประกอบปกติ ความสัมพันธ์ของสีเขียว L และ Rsubsemigroups คง ศูนย์ซ้าย และขวาเป็นศูนย์และ ในวงสี่เหลี่ยม ตั้งแต่ปิดการตั้งค่าของภาษารู้จักต้นไม้ทั้งหมดของชนิดที่กำหนดภายใต้การผลิตภัณฑ์ภาษา ชุดภาษารู้จักต้นไม้ทั้งหมดรูปแบบ subsemigroupของ semigroup ภาษาต้นไม้ทั้งหมดที่ประกอบด้วย semigroup ของมีจำกัดทั้งหมดภาษาต้นไม้ชนิดที่ได้รับ ภาษารู้จักต้นไม้สามารถสร้างได้โดยgrammars ต้นไม้ปกติ เราลักษณะ idempotent องค์ประกอบทั้งหมดในการ semigroupภาษารู้จักต้นไม้ทั้งหมดของชนิดτโดยคุณสมบัติของ grammars ปกติการเกิดซ้ำของผลิตภัณฑ์ภาษาบทบาทของ Kleene-∗-การดำเนินการในทฤษฎีทางภาษา และเป็นหนึ่งในการดำเนินงานปกติคำสำคัญ: ต้นไม้ภาษา ผลิตภัณฑ์ของต้นไม้ภาษา องค์ประกอบปกติต้นไม้รู้จักภาษา ความสัมพันธ์ของสีเขียว ขวาศูนย์ semigroups leftzerosemigroups สี่เหลี่ยมกับวงดนตรีจำแนกเรื่อง AMS: 08C 99, 20 ม. 17

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

ผลิตภัณฑ์ของต้นไม้ภาษา
บทคัดย่อ
ชุดแง่ของประเภทτจะเรียกว่าภาษาต้นไม้ ผลิตภัณฑ์ภาษาต้นไม้เป็น
การดำเนินงานที่สำคัญกำหนดไว้ในชุดภาษาต้นไม้ซึ่งแผนที่ที่รู้จัก
ภาษาต้นไม้ภาษาต้นไม้ที่รู้จัก สินค้าภาษาต้นไม้ต้นนี้สามารถ
อธิบายได้ด้วยการทับซ้อนของชุดของคำ ขึ้นอยู่กับการซ้อน
การดำเนินงานที่เรากำหนดดำเนินการเชื่อมโยงไบนารี ในทฤษฎีของภาษาต้นไม้
สินค้าของภาษาที่เรียกว่า Z-สินค้า จุดมุ่งหมายของการวิจัยนี้มีวัตถุประสงค์เพื่อศึกษา
คุณสมบัติของ semigroups ที่เกิดขึ้นและ subsemigroups ของมัน โดยเฉพาะอย่างยิ่งเรามีความ
สนใจในการ idempotent และปกติองค์ประกอบความสัมพันธ์ L สีเขียวและ R ใน
คงซ้ายและขวาศูนย์ศูนย์ subsemigroups และวงดนตรีที่เป็นรูปสี่เหลี่ยมผืนผ้า ตั้งแต่
ชุดของทุกภาษาที่รู้จักต้นไม้ชนิดที่กำหนดปิดให้บริการภายใต้
ผลิตภัณฑ์ภาษาชุดของทุกภาษาต้นไม้ที่รู้จักในรูปแบบ subsemigroup
ของ semigroup ภาษาต้นไม้ทั้งหมดที่มี semigroup ทุก จำกัด
ภาษาต้นไม้ชนิดที่กำหนด ภาษาที่รู้จักต้นไม้สามารถสร้างขึ้นโดย
ไวยากรณ์ต้นไม้ปกติ เราให้ลักษณะองค์ประกอบ idempotent ทั้งหมดใน semigroup
. ของทุกภาษาต้นไม้ที่รู้จักประเภทτโดยคุณสมบัติของไวยากรณ์ปกติ
ย้ำของผลิตภัณฑ์ภาษาบทบาทของ Kleene - การ * - การดำเนินงานใน
ทฤษฎีของภาษาอย่างเป็นทางการและเป็นหนึ่งในปกติ การดำเนินงาน.
คำสำคัญ: ภาษาต้นไม้; สินค้าภาษาต้นไม้; องค์ประกอบปกติ
ภาษาต้นไม้ที่รู้จัก; ความสัมพันธ์ของกรีน; semigroups ขวาศูนย์; leftzero
semigroups; วงดนตรีที่เป็นรูปสี่เหลี่ยมผืนผ้า.
AMS เรื่องการจัดประเภท: 08C99, 20M17