Symmetry groups of automata Article

•  
• Overview
•  
• Identity
•  
• Additional Document Info
•  
• View All
•  

Overview

abstract

• Symmetry transformations on the input and output code spaces of deterministic finite automata (DFA) are introduced. We show that the symmetry groups of transformations are produced by group DFA (gDFA) whose set of states and set of inputs are subgroups of the symmetric groups Sq and Sk, respectively (q is the number of states and k the number of input symbols). The set of transitions of a gDFA is also a group. The symmetries of the n-moment delay DFA, relevant for cellular automata, are studied in detail. In particular, we show that the n-moment delay DFA on two symbols are self-symmetric. The symmetry gDFA of the 2-moment delay DFA on two symbols is displayed in detail. An algorithm to construct the symmetry gDFA of arbitrary DFA is given. An application of gDFA to cellular automata dynamics is mentioned. © 1994.

authors

• Ugalde Saldaña Edgardo
• Urías Hermosillo Jesús

publication date

• 1994-01-01

published in

• Physica D: Nonlinear Phenomena  Journal

Identity

Digital Object Identifier (DOI)

• 10.1016/0167-2789(94)90064-7

Additional Document Info

start page

• 178

end page

• 184

volume

• 70

issue

• 1-2