Career: Theory and Applications of Reversible Cellular Automata

可逆元胞自动机（RCA）是局部计算的元胞空间到自身的并行一对一映射。它们为大规模并行非耗散计算提供了坚实的理论模型。本课题研究了RCA及其相关的量子元胞自动机（QCA）的理论，并介绍了在图像压缩和密码学中的新应用。主要的理论目标是理解RCA的结构，并根据简单的局部操作找到RCA的新表示。表示应该允许轻松生成可在应用程序中使用的新RCA规则。最有用的表示是允许将所需的属性直接编程到RCA中的表示。量子CA是RCA的泛化。第一个目标是找到QCA的正确定义，即在具有量子相互作用的实际物理世界中可以实现QCA。该定义也应该足够通用，以允许任意量子算法的实现。然后，确定了QCA与有限量子门齐次阵列之间的关系。图像压缩应用来源于子带编码的类比。可逆元胞自动机被解释为完美重构滤波器组的非线性版本。线性变换的能量压缩被RCA的信息压缩思想所取代。新的压缩技术将最适合于高效无损压缩，但也考虑有损图像压缩的应用。此外，与RCA理论的类比为高维滤波器组理论提供了新的见解。在密码学方面，该项目继续研究基于RCA的密码系统的可行性和安全性。通过标准计算理论课程，将有限自动机在图像压缩和密码学中的应用，以及在分形图像生成和压缩中的相关结果引入计算机科学课程。他们提供了自动机理论如何在看似无关的领域中发挥作用的实际例子，并增加了学生学习具有挑战性的理论概念的动机。除了传统的信号处理方法外，还将开设一门新的图像压缩研究生课程和研讨会，重点是压缩的算法方面。

Reversible Cellular Automata (RCA) are locally computed parallel one-to-one mappings of cellular space onto itself. They provide a solid theoretical model for massively parallel non-dissipative computation. This project investigates the theory of RCA and closely related Quantum Cellular Automata (QCA), and introduces new applications in image compression and cryptography. The main theoretical goal is to understand the structure of RCA and find new representations of RCA in terms of simple local operations. The representations should allow easy generation of new RCA rules that can be used in the applications. Most useful representations are ones that allow desired properties to be programmed directly into the RCA. Quantum CA are generalizations of RCA. The first goal is to find a correct definition of QCA in the sense that it is realizable in the actual physical world with quantum interactions. The definition should be also general enough to allow implementations of arbitrary quantum algorithms. Then the relation between QCA and homogeneous arrays of finite quantum gates will be determined. Image compression applications arise from analogy to subband coding. Reversible Cellular Automata are interpreted as non-linear versions of perfect reconstruction filter banks. Energy compaction by linear transforms is replaced by the idea of information compaction by RCA. The new compression techniques will be most suitable for efficient lossless compression but also lossy image compression applications are considered. In addition, analogy to RCA theory provides new insight into the theory of higher dimensional filter banks. In cryptography the project continues investigating the feasibility and security of RCA based cryptosystems. Applications to image compression and cryptography, together with related results on finite automata in fractal image generation and compression will be introduced to the computer science curriculum through standard computation theory cou rses. They provide practical examples of how automata theory can be useful in seemingly unrelated fields, and increase student motivation to study challenging theoretical concepts. A new graduate course and seminar on image compression will be developed with emphasis on algorithmic aspects of compression in addition to the traditional signal processing approach.