An algebraical system for polynomial representation of k-valued logical functions (Q1112805)

The study of a number of classes of parallel discrete dynamical systems (PDDS) as a new environment for mathematical modelling is closely linked with the investigation of so-called local transition functions (LTF) \(R^{(n)}(x_ 1,...,x_ n)\) which present themselves as k-valued logical functions. For the rest of the review, a LTF \(R^{(n)}\) in the alphabet \(A_ k=(0,1,...,k-1)\) is any mapping \(R^{(n)}: A^ n_ k\to A_ k\). Among different approaches to investigate such LTF the theoretical method takes special place. The method essentially used the alphabet \(A_ k\) (k prime) since the LTF \(R^{(n)}\) in this alphabet can be represented in the form of a polynomial modulo k of maximal degree n(k-1) over the field \(A_ k\), and vice versa. In the case of a composite integer k, ``almost all'' LTF in the alphabet \(A_ k\) cannot be represented in the form of a polynomial modulo k for enough large integers n and/or k. In the paper an algebraic system, in which ``almost all'' LTF \(R^{(n)}\) in the alphabet \(A_ k\) (k composite integer) have polynomial representation, is presented. The algebraic system \(<A_ k;+;\otimes >\) is defined in the following way. On the set \(A_ k\) (k composite) the usual operation \((+)\) of addition modulo k is defined. At the same time, on the set \(A_ k\) the binary operation of \(\otimes\)- multiplication is introduced in conformity with a special table. The operation of \(\otimes\)-multiplication on the set \(A_ k\setminus \{0\}\) forms the finite cyclic group \(A_ k^{\otimes}\) of degree (k-1). The general result of the paper is given by the following Theorem. There exists an algebraic system \(<A_ k;+;\otimes >\) in which ``almost each'' LTF \(R^{(n)}\) in the alphabet \(A_ k\) (k composite integer) can be unequivocally represented in the form of a polynomial \(P_{\otimes}(n)(mod k).\) This theorem plays a very important role in investigations of dynamical properties of the PDDS and gives comfortable analytical representation of k-valued logical functions in the case of composite integers k.