Optimal and suboptimal regional control of probabilistic cellular automata

Natural Computing - Probabilistic cellular automata are extended stochastic systems, widely used for modelling phenomena in many disciplines. The possibility of controlling their behaviour is...     

On the relationship between fuzzy and Boolean cellular automata

Fuzzy cellular automata (FCA) are continuous cellular automata where the local rule is defined as the “fuzzification” of the local rule of a corresponding Boolean cellular automaton in disjunctive normal form. In this paper, we are interested in the relationship between Boolean and fuzzy models and, for the first time, we analytically show the existence of a strong connection between them by focusing on two properties: density conservation and additivity.We begin by showing that the density conservation property, extensively studied in the Boolean domain, is preserved in the fuzzy domain: a Boolean CA is density conserving if and only if the corresponding FCA is sum preserving. A similar result is established for another novel “spatial” density conservation property. Second, we prove an interesting parallel between the additivity of Boolean CA and oscillations of the corresponding fuzzy CA around its fixed point. In fact, we show that a Boolean CA is additive if and only if the behaviour of the corresponding fuzzy CA around its fixed point coincides with the Boolean behaviour. Finally, we give a probabilistic interpretation of our fuzzification which establishes an equivalence between convergent fuzzy CA and the mean field approximation on Boolean CA, an estimation of their asymptotic density.These connections between the Boolean and the fuzzy models are the first formal proofs of a relationship between them.     

Learning cellular automata rules for binary classification problem

This paper proposes a cellular automata-based solution of a binary classification problem. The proposed method is based on a two-dimensional, three-state cellular automaton (CA) with the von Neumann neighborhood. Since the number of possible CA rules (potential CA-based classifiers) is huge, searching efficient rules is conducted with use of a genetic algorithm (GA). Experiments show an excellent performance of discovered rules in solving the classification problem. The best found rules perform better than the heuristic CA rule designed by a human and also better than one of the most widely used statistical method: the k-nearest neighbors algorithm (k-NN). Experiments show that CAs rules can be successfully reused in the process of searching new rules.     

Solving the parity problem in one-dimensional cellular automata

The parity problem is a well-known benchmark task in various areas of computer science. Here we consider its version for one-dimensional, binary cellular automata, with periodic boundary conditions: if the initial configuration contains an odd number of 1s, the lattice should converge to all 1s; otherwise, it should converge to all 0s. Since the problem is ill-defined for even-sized lattices (which, by definition, would never be able to converge to 1), it suffices to account for odd-sized lattices only. We are interested in determining the minimal neighbourhood size that allows the problem to be solvable for any arbitrary initial configuration. On the one hand, we show that radius 2 is not sufficient, proving that there exists no radius 2 rule that can solve the parity problem, even in the simpler case of prime-sized lattices. On the other hand, we design a radius 4 rule that converges correctly for any initial configuration and formally prove its correctness. Whether or not there exists a radius 3 rule that solves the parity problem remains an open problem; however, we review recent data against a solution in radius 3, thus providing strong empirical evidence that there may not exist a radius 3 solution even for prime-sized lattices only, contrary to a recent conjecture in the literature.     

Optimal control problem of singular Boolean control networks

In this paper, the optimal control problem of singular Boolean control networks is considered via semi-tensor product. Using an analogous needle variation, for multi-input case, a necessary condition for the existence of optimal control is provided based on the algebraic form of singular Boolean control networks, and the result is specialized to the single-input case. Then, an algorithm is presented to calculate an optimal control. Illustrative examples, including the single-input case, are given to show the feasibility of the theoretical results.     

Affine continuous cellular automata solving the fixed-length density classification problem

In this paper, the classical density classification problem is considered in the context of affine continuous cellular automata. It has been shown earlier that there exists no general solution to this problem that is valid for any number of cells. Here, we consider this problem in the case of a fixed number of cells. Necessary conditions for solving the problem are formulated. Based on this knowledge, a specific class of affine continuous cellular automata is evaluated experimentally for 23 cells. A rich solution set is analysed and visualised.     

Stability criterion for a lexicographic Boolean optimization problem

A vector Boolean sequential minimization problem for absolute values of linear functions is considered. Necessary and sufficient condition for stability of this type that is a discrete analogue of the upper Hausdorff semicontinuity of a point-to-set mapping is established. This mapping associates a set of lexicographic optima with each set of problem parameters. The study was sponsored by the Fundamental and Applied Research Interuniversity Program of the Republic of Belarus (Grant 492/28). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 127–132, July–August 2007.     

Decision procedures for inductive Boolean functions based on alternating automata

We show how alternating automata provide decision procedures for the equality of inductively defined Boolean functions and present applications to reasoning about parameterized families of circuits. We use alternating word automata to formalize families of linearly structured circuits and alternating tree automata to formalize families of tree structured circuits. We provide complexity bounds for deciding the equality of function (or circuit) families and show how our decision procedures can be implemented using BDDs. In comparison to previous work, our approach is simpler, has better complexity bounds, and, in the case of tree-structured families, is more general.     

Optimal boundary control of a tracking problem for a parabolic distributed parameter system

A comparative study is made of five methods for calculating the optimal control function for a linear parabolic tracking problem with boundary control. Questions of computational instability, numerical accuracy and economic computer usage are investigated. Open-loop methods based upon the variational equations are shown to have the advantages of efficiency, accuracy and ease of programming. Methods based on the method of lines and the Riccati equation are shown to be less straightforward in use. The fourth-order explicit Runge-Kutta algorithm has little scope for application because of its restricted stability range. The Kalman-Englar algorithm is much more robust but a Crank-Nicholson algorithm for the associated auxiliary equation is not very satisfactory in some cases. The auxiliary variable method may then confer some benefits.     

Using cellular automata for porous media simulation

A cellular automata (CA) approach is proposed for simulating a fluid flow through porous materials with tortuous channels at pore level. The approach aims to combine CA methods both for constructing computer representation of porous material morphology and for simulating fluid flow through it. Morphology representation is obtained using CA whose evolution exhibits self-organization and results in a stable configuration. The latter is then used for Lattice Gas CA application to simulate fluid flow through a porous material specimen and compute its permeability properties. Special boundary conditions are introduced allowing for different smoothness of solid pore walls surface. The model has been tested on a small 2D fragment in a PC and then implemented to investigate a porous carbon electrode of a hydrogen fuel cell on 128 processors of a multiprocessor cluster.     

A cellular automata model for edge relaxation

An edge detection method based on a fuzzy cellular automata model which serves as the relaxation labeling process constraint is described. An initial estimate of edge locations is made and the remaining ambiguities are resolved by thinning and enhancing the edges through several iterations. An efficient fixed step algorithm is presented and its performance is evaluated for different noise level images. The method is useful for the detection of linear image features in three-dimensional robot vision systems.     

Monotone methods for a discrete boundary problem

This paper is motivated by recent interests in space discrete Nagumo equations and is concerned with the existence of solutions of a nonlinear discrete boundary value problem. Monotone methods are used to derive the existence theorems. These methods, as is well known, provide constructive schemes for calculating the solutions.     

Simultaneous stabilization for a set of Boolean control networks

This paper investigates simultaneous stabilization of a collection of Boolean control networks (BCNs) by using the semi-tensor product method, and presents a number of new results. First, an algebraic expression of the BCNs is obtained by the semi-tensor product, based on which some necessary and sufficient conditions are presented to solve the simultaneous stabilization problem by a free control sequence, a state-feedback control, and an output-feedback control, respectively. Second, using the column stacking form of matrices, a new procedure is established to design both state-feedback and output-feedback controllers for the simultaneous stabilization problem. The study of two illustrative examples shows that the new results obtained in this paper are very effective in solving simultaneous stabilization of a collection of BCNs.     

Efficiency of boundary evaluation for a cellular model

Feature modeling systems usually employ a boundary representation (b-rep) to store the shape information on a product. It has, however, been shown that a b-rep has a number of shortcomings, and that a cellular representation can be a valuable alternative. A cellular model stores additional shape information on features, including the feature faces that are not on the boundary of the product. Such information can be profitably used for several purposes.A major operation in every feature modeling system is boundary evaluation, which computes the geometric model of a product, i.e. either the b-rep or the cellular model, from the features that have been specified by the user. Since boundary evaluation has to be executed each time a feature is added, removed or modified, its efficiency is of paramount importance.In this paper, boundary evaluation for a cellular model is described in some detail. Its efficiency is compared to the efficiency of boundary evaluation for a b-rep, on the basis of both complexity analysis and performance measurements for the two types of evaluation. It turns out that boundary evaluation for a cellular model is, in fact, more efficient than for a b-rep, which makes cellular models even more attractive as an alternative to b-reps.     

Time-optimal control for discrete-time hybrid automata

In this paper, the problem of time-optimal control for hybrid systems with discrete-time dynamics is considered. The hybrid controller steers all trajectories starting from a maximal set to a given target set in minimum time. We derive an algorithm that computes this maximal winning set. Also, algorithms for the computation of level sets associated with the value function rather than the value function itself are presented. We show that by solving the reachability problem for the discrete time hybrid automata we obtain the time optimal solution as well. The control synthesis is subject to hard constraints on both control inputs and states. For linear discrete-time dynamics, linear programming and quantifier elimination techniques are employed for the backward reachability analysis. Emphasis is given on the computation of operators for non-convex sets using an extended convex hull approach. A two-tank example is considered in order to demonstrate the techniques of the paper.     

Static hazard elimination for a logical circuit using quantum dot cellular automata

Microsystem Technologies - Quantum dot cellular automata (QCA) is an upcoming nano-technology for its high speed and low power operation in the field of nano-science and nano-electronics. As QCA...     

Corrosion-passivation processes in a cellular automata based simulation study

A short survey of cellular automata based models for corrosion and passivation phenomena is given. Results of simulations based on the model of spatially separated anodic and cathodic reactions are presented for a cavity development from a point-like damage of a protective layer and from an initially flat unprotected surface. We show some new peculiar examples of the symmetry breaking in the cavity development. The results for the initially flat surface show roughening of the surface at the beginning of the corrosion process. After that, pit merging causes a resmoothing of the surface. An oscillatory behavior of the surface roughness is observed caused by a peninsula formation with subsequent island detachment. These results are obtained in 2D because of computational limitations. We plan simulations in 3D and point out the problems we encounter in their realization.