Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
One-dimensional reversible cellular automata determination algorithm based on subset graph under null boundary condition
Year (A.D.)
2020
Document Type
Thesis
First Advisor
อรรถสิทธิ์ สุรฤกษ์
Faculty/College
Faculty of Engineering (คณะวิศวกรรมศาสตร์)
Department (if any)
Department of Computer Engineering (ภาควิชาวิศวกรรมคอมพิวเตอร์)
Degree Name
วิศวกรรมศาสตรดุษฎีบัณฑิต
Degree Level
ปริญญาเอก
Degree Discipline
วิศวกรรมคอมพิวเตอร์
DOI
10.58837/CHULA.THE.2020.1133
Abstract
เซลลูลาร์ออโตมาตาถือเป็นโมเดลทางคณิตศาสตร์ที่สามารถทำงานแบบระบบพลวัต ซึ่งประกอบไปด้วยสถานะจำกัดที่เรียงตัวกันอย่างเป็นระบบเรียกเซลล์ แต่ละเซลล์จะเปลี่ยนสถานะไปยังสถานะใหม่พร้อมกันด้วยการอาศัยกฎการส่งผ่านที่ขึ้นอยู่กับเซลล์รอบ ๆ ด้วยเวลาแบบเต็มหน่วย แม้ว่าเซลลูลาร์ออโตมาตามีโครงสร้างและนิยามในแบบพื้นฐาน แต่สามารถสร้างระบบที่พฤติกรรมมีความซับซ้อนได้ สมบัติในการผันกลับได้ของเซลลูลาร์ออโตมาตาถือเป็นสมบัติสำคัญที่ได้รับความสนใจในหลายงานวิจัยและสามารถนำไปประยุกต์ใช้ได้ในงานหลาย ๆ ด้านในทางวิทยาศาสตร์ แต่สำหรับเซลลูลาร์ออโตมาตาหนึ่งมิติภายใต้เงื่อนไขการกำหนดขอบเขตแบบไม่มีค่ายังถือมีข้อจำกัดของจำนวนกฎที่มีไม่มากที่มีสมบัติดังกล่าว ในงานวิจัยนี้ศึกษาและเสนออัลกอริทึมการระบุการผันกลับของเซลลูลาร์ออโตมาตาหนึ่งมิติด้วยกราฟสับเซตย่อยภายใต้เงื่อนไขการกำหนดขอบเขตแบบไม่มีค่านิยามเซลล์เพื่อนบ้านด้วยเวกเตอร์ ด้วยการแทนเซลลูลาร์ออโตมาตาด้วยกราฟสับเซตย่อยเราเสนอวิธีในการระบุสมบัติการผันกลับได้ในกราฟโดยการพิจารณาเส้นเชื่อมและจุดยอดที่เชื่อมถึงกัน นอกจากนี้งานวิจัยนี้ยังเสนอวิธีในการคำนวณสถานะก่อนหน้าสำหรับสถานะใด ๆ ของเซลลูลาร์ออโตมาตาหนึ่งมิติที่มีสมบัติผันกลับได้ภายใต้เงื่อนไขการกำหนดขอบเขตแบบไม่มีค่า ซึ่งวิธีที่ได้เสนออยู่บนพื้นฐานของการพิจารณาลักษณะของเซลล์เพื่อนบ้านด้วยการคำนวณทางเดินบนกราฟด้วยการดำเนินการของเมตริกซ์
Other Abstract (Other language abstract of ETD)
Cellular automata (CA) are mathematical dynamical systems that are comprising numerous finite state automata represented by cells. Each cell is updated to the new state simultaneously according to the current states of its neighbors at a discrete time. Although CA has a simple structure and definition, but it can generate a complex behavior. Reversibility of CA is an important property of the CA, which is attracted by many researchers and has been applied to a wide range of fields in science. In the case of a one-dimensional CA under null boundary condition, there are not many rules that emerge with that property. This dissertation studies and proposes one-dimensional reversible CA determination algorithm based on subset graph under null boundary condition with a vector-defined neighborhood. With the representation of subset graph of CA, we propose a method for determining the reversible property of a graph by considering its connected edges and vertices. The reversible rule can be considered on the path in the graph. In addition, we also introduce a method for calculating the previous state of a given state of a reversible CA under null boundary condition. The proposed method is based on the considering the de Bruijn graph path with the matrix operation.
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
วงศ์นิล, วรยุทธ, "อัลกอริทึมการระบุการผันกลับของเซลลูลาร์ออโตมาตาหนึ่งมิติด้วยกราฟสับเซตย่อยภายใต้เงื่อนไขการกำหนดขอบเขตแบบไม่มีค่า" (2020). Chulalongkorn University Theses and Dissertations (Chula ETD). 3791.
https://digital.car.chula.ac.th/chulaetd/3791