อัลกอริทึมการระบุการผันกลับของเซลลูลาร์ออโตมาตาหนึ่งมิติด้วยกราฟสับเซตย่อยภายใต้เงื่อนไขการกำหนดขอบเขตแบบไม่มีค่า

Abstract

เซลลูลาร์ออโตมาตาถือเป็นโมเดลทางคณิตศาสตร์ที่สามารถทำงานแบบระบบพลวัต ซึ่งประกอบไปด้วยสถานะจำกัดที่เรียงตัวกันอย่างเป็นระบบเรียกเซลล์ แต่ละเซลล์จะเปลี่ยนสถานะไปยังสถานะใหม่พร้อมกันด้วยการอาศัยกฎการส่งผ่านที่ขึ้นอยู่กับเซลล์รอบ ๆ ด้วยเวลาแบบเต็มหน่วย แม้ว่าเซลลูลาร์ออโตมาตามีโครงสร้างและนิยามในแบบพื้นฐาน แต่สามารถสร้างระบบที่พฤติกรรมมีความซับซ้อนได้ สมบัติในการผันกลับได้ของเซลลูลาร์ออโตมาตาถือเป็นสมบัติสำคัญที่ได้รับความสนใจในหลายงานวิจัยและสามารถนำไปประยุกต์ใช้ได้ในงานหลาย ๆ ด้านในทางวิทยาศาสตร์ แต่สำหรับเซลลูลาร์ออโตมาตาหนึ่งมิติภายใต้เงื่อนไขการกำหนดขอบเขตแบบไม่มีค่ายังถือมีข้อจำกัดของจำนวนกฎที่มีไม่มากที่มีสมบัติดังกล่าว

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