Classification of Non-linear Boolean functions is a long-standing problem in the area of theoretical computer science. In this paper, effort has been made to achieve a systematic classification of all n-variable Boolean functions, where only one affi
ne Boolean function belongs to each class. Two different methods are proposed to achieve this classification. The first method is a recursive procedure that uses the Cartesian product of sets starting from the set of 1-variable Boolean function and in the second method classification is achieved through a set of invariant bit positions with respect to an affine function belonging to that class. The invariant bit positions also provide information concerning the size and symmetry properties of the classes/sub-classes, such that the members of classes/sub-classes satisfy certain similar properties.
In this paper, linear Cellular Automta (CA) rules are recursively generated using a binary tree rooted at 0. Some mathematical results on linear as well as non-linear CA rules are derived. Integers associated with linear CA rules are defined as linea
r numbers and the properties of these linear numbers are studied.
The notion of Carry Value Transformation (CVT) is a model of Discrete Deterministic Dynamical System. In this paper, we have studied some interesting properties of CVT and proved that (1) the addition of any two non-negative integers is same as the s
um of their CVT and XOR values. (2) While performing the repeated addition of CVT and XOR of two non-negative integers a and b (where a >= b), the number of iterations required to get either CVT=0 or XOR=0 is at most the length of a when both are expressed as binary strings. A similar process of addition of Modified Carry Value Transformation (MCVT) and XOR requires a maximum of two iterations for MCVT to be zero. (3) An equivalence relation is defined in the set (Z x Z) which divides the CV table into disjoint equivalence classes.
In this paper the theory of 2-Variable Boolean Operation (2-VBO) has been discussed on a pair of n-bit strings. 2-VBO serves to bring out the relation between numbers which when plot on a 2-D surface form interesting patterns; patterns that may be fi
xed, periodic, chaotic or complex. Some of these patterns represent natural fractals. This paper also provides mathematical analysis corresponding to each of the obtained patterns, which would aid to understanding their formation. 2-VBO is an attempt towards the production and classification of patterns which represent various mathematical models and naturally occurring phenomena.
This paper presents solutions to Density Classification Task (DCT) using a variant of Cellular Automata (CA) called Programmable Cellular Automata (PCA). The translation property as well as the density preserving property of fundamental CA rules in 1
D and 2D, and the advantage of PCA are embedded together to obtain the DCT solution. The advantage of PCA over standard CA is reported. A general 2D DCT of arbitrary shapes and sizes, its applicability and its solution using PCA is newly introduced.
This paper proposes several algorithms and their Cellular Automata Machine (CAM) for drawing the State Transition Diagram (STD) of an arbitrary Cellular Automata (CA) Rule (any neighborhood, uniform/ hybrid and null/ periodic boundary) and length of
the CA n. It also discusses the novelty, hardware cost and the complexities of these algorithms.
Global dynamics of a non-linear Cellular Automata is, in general irregular, asymmetric and unpredictable as opposed to that of a linear CA, which is highly systematic and tractable. In the past efforts have been made to systematize non-linear CA evol
utions in the light of Boolean derivatives and Jacobian Matrices. In this paper two different efforts have been made: first we try to systematize non-linear CA evolution in the light of deviant states and non-deviant states. For all the non-deviant states the nearest linear rule matrix is applicable where as for the deviant states we have a set of other matrices. Second using algebraic manipulation, an efficient algorithm is proposed by which every Non-linear Boolean function can be characterized by a sequence of binary matrices.
In this paper, we analyze the algebraic structure of some null boundary as well as some periodic boundary 2-D Cellular Automata (CA) rules by introducing a new matrix multiplication operation using only AND, OR instead of most commonly used AND, EX-O
R. This class includes any CA whose rule, when written as an algebra, is a finite Abelean cyclic group in case of periodic boundary and a finite commutative cyclic monoid in case of null boundary CA respectively. The concept of 1-D Multiple Attractor Cellular Automata (MACA) is extended to 2-D. Using the family of 2-D MACA and the finite Abelian cyclic group, an efficient encompression algorithm is proposed for binary images.
This paper deals with the theory and application of 2-Dimensional, nine-neighborhood, null- boundary, uniform as well as hybrid Cellular Automata (2D CA) linear rules in image processing. These rules are classified into nine groups depending upon the
number of neighboring cells influences the cell under consideration. All the Uniform rules have been found to be rendering multiple copies of a given image depending on the groups to which they belong where as Hybrid rules are also shown to be characterizing the phenomena of zooming in, zooming out, thickening and thinning of a given image. Further, using hybrid CA rules a new searching algorithm is developed called Sweepers algorithm which is found to be applicable to simulate many inter disciplinary research areas like migration of organisms towards a single point destination, Single Attractor and Multiple Attractor Cellular Automata Theory, Pattern Classification and Clustering Problem, Image compression, Encryption and Decryption problems, Density Classification problem etc.
In this paper an algorithm is designed which generates in-equivalent Boolean functions of any number of variables from the four Boolean functions of single variable. The grammar for such set of Boolean function is provided. The Turing Machine that accepts such set is constructed.
