Chulalongkorn University Theses and Dissertations (Chula ETD)

การทวนสอบการย้อนกลับได้ของเซลลูลาร์ออโตมาตาหนึ่งมิติโดยใช้การส่งผ่านเวกเตอร์

Other Title (Parallel Title in Other Language of ETD)

Reversibility verification of one-dimensional cellular automata using vector transitions

Year (A.D.)

2011

Document Type

Thesis

First Advisor

อรรถสิทธิ์ สุรฤกษ์

Faculty/College

Faculty of Engineering (คณะวิศวกรรมศาสตร์)

Degree Name

วิทยาศาสตรมหาบัณฑิต

Degree Level

ปริญญาโท

Degree Discipline

วิทยาศาสตร์คอมพิวเตอร์

DOI

10.58837/CHULA.THE.2011.1358

Abstract

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

Other Abstract (Other language abstract of ETD)

A problem in a reversibility of the one-dimensional Cellular Automata (CA) concerns about a less number of a transition rule of CA. Many researchers studied and focused on introducing a model with the reversible property for more complexity. Therefore, some classes of CA were proposed by adjust some feature of CA. Later, the CA with memory was introduced and could increase the number of the transition rules for the reversible CA. This CA model was appliedin another computer fields such as cryptographic etc. The transition by a vector rules (non-uniform CA) was illustrated for handle the least number of the transition rule and the vector rule could generate the large number of the transition rule. Thus, this thesis introduces the improved model and proposes an algorithm for verifying the reversibility property of CA. The alrithm could detect if the CA is reversible. From our result, the reversed CA can be construct if there exists. Furthermore, the necessary property of the reversible rule is included in the research.

Link to Full Text

Share

COinS