Dynamics in binary neural networks with a finite number of patterns. I: General picture of the asynchronous zero temperature dynamics.
Ergodic Properties of Certain Surjective Cellular Automata.
Exemples de classes d'automates cellulaires
Lorsqu'on observe des orbites de certains automates cellulaires, on peut penser qu'elles apparaissent comme des mélanges d'orbites d'autres automates (composants). Dans cet article, nous tentons de comprendre ce phénomène en construisant un hybride de deux automates au moyen d'un troisième. Deux types d'automates cellulaires sont introduits : les captifs et les foulards. Nous comparons des propriétés de ces hybrides dans le cadre des classifications algébriques introduites par [B. Martin...
Formal languages in dynamical systems
Gardens of Eden and amenability on cellular automata
Generalized pascal triangles: overview of new results
Gorenstein polytopes obtained from bipartite graphs.
Language classes defined by time-bounded relativised cellular automata
Limit behaviour of trajectories involving subgradients of convex functions
Modeling snow crystal growth. I: Rigorous results for Packard's digital snowflakes.
Number-conserving reversible cellular automata and their computation-universality
We introduce a new model of cellular automaton called a one-dimensional number-conserving partitioned cellular automaton (NC-PCA). An NC-PCA is a system such that a state of a cell is represented by a triple of non-negative integers, and the total (i.e., sum) of integers over the configuration is conserved throughout its evolving (computing) process. It can be thought as a kind of modelization of the physical conservation law of mass (particles) or energy. We also define a reversible version of...
Number-Conserving Reversible Cellular Automata and Their Computation-Universality
We introduce a new model of cellular automaton called a one-dimensional number-conserving partitioned cellular automaton (NC-PCA). An NC-PCA is a system such that a state of a cell is represented by a triple of non-negative integers, and the total (i.e., sum) of integers over the configuration is conserved throughout its evolving (computing) process. It can be thought as a kind of modelization of the physical conservation law of mass (particles) or energy. We also define a reversible version...
On real time and linear time cellular automata
On the computation of covert channel capacity
We address the problem of computing the capacity of a covert channel, modeled as a nondeterministic transducer. We give three possible statements of the notion of “covert channel capacity” and relate the different definitions. We then provide several methods allowing the computation of lower and upper bounds for the capacity of a channel. We show that, in some cases, including the case of input-deterministic channels, the capacity of the channel can be computed exactly (e.g. in the form...
On the equivalence of linear conjunctive grammars and trellis automata
This paper establishes computational equivalence of two seemingly unrelated concepts: linear conjunctive grammars and trellis automata. Trellis automata, also studied under the name of one-way real-time cellular automata, have been known since early 1980s as a purely abstract model of parallel computers, while linear conjunctive grammars, introduced a few years ago, are linear context-free grammars extended with an explicit intersection operation. Their equivalence implies the equivalence of several...
On the equivalence of linear conjunctive grammars and trellis automata
This paper establishes computational equivalence of two seemingly unrelated concepts: linear conjunctive grammars and trellis automata. Trellis automata, also studied under the name of one-way real-time cellular automata, have been known since early 1980s as a purely abstract model of parallel computers, while linear conjunctive grammars, introduced a few years ago, are linear context-free grammars extended with an explicit intersection operation. Their equivalence implies the equivalence of several...
Pascal's triangle, complexity and automata. (Triangle de Pascal, complexité et automates.)
Periodic Orbits for Additive Cellular Automata.
Progress of iteration theory since 1981.
QCA implementation of a multichannel filter for image processing.