# De Bruijn Graphs and Linear Cellular Automata

@article{Sutner1991DeBG, title={De Bruijn Graphs and Linear Cellular Automata}, author={Klaus Sutner}, journal={Complex Syst.}, year={1991}, volume={5} }

De Bruij n graphs provide a convenient way to describe configura tions of linear cellular automata (CAs). Using t hese gra phs, we give a simple quadra t ic t ime algorithm to det ermine whet her a linear CA is reversible. Similarly, one can decide in quadrat ic time whet her t he global map of th e auto mato n is surjective. We also show tha t every recursive configuration that has a predecessor on a linear CA already has a recursive pr edecessor. By contradist inction, it is in genera l… Expand

#### 116 Citations

Linear Cellular Automata and de Bruijn Automata

- Computer Science
- 1999

It is shown that linear cellular automata have a canonical representation in terms of labeled de Bruijn graphs, construed as semiautomata, and a simple algorithm is given to determine reversibility and surjectivity of the global maps. Expand

Linear Cellular Automata and de

- 2007

Linear cellular automata have a canonical representation in terms of labeled de Bruijn graphs. We will show that these graphs, construed as semiau-tomata, provide a natural setting for the study of… Expand

Linear Cellular Automata and Finite Automata

- 2003

Linear cellular automata have a canonical representation in terms of labeled de Bruijn graphs. We will show that these graphs, construed as semiautomata, provide a natural setting for the study of… Expand

Inversion of Mutually Orthogonal Cellular Automata

- Computer Science
- ACRI
- 2018

This work designs an algorithm based on coupled de Bruijn graphs which solves the inversion problem of pairs of configurations in MOCA, and shows how to design a (2, n) threshold Secret Sharing Scheme (SSS) based on MocA where any combination of two players can reconstruct the secret by applying this inversion algorithm. Expand

Computation of Explicit Preimages in One-Dimensional Cellular Automata Applying the De Bruijn Diagram

- Computer Science, Mathematics
- J. Cell. Autom.
- 2008

The problem of calculating preimages is reduced to solving the classic Path-finding Problem in graph theory, where all possible paths are the preimages of the cellular automaton. Expand

Latin Hypercubes and Cellular Automata

- Computer Science, Mathematics
- Automata
- 2020

It is proved that linear bipermutive CA (LBCA) yielding Latin hypercubes of dimension $k>2$ are defined by sequences of invertible Toeplitz matrices with partially overlapping coefficients, which can be described by a specific kind of regular de Bruijn graph induced by the support of the determinant function. Expand

A Random NP-Complete Problem for Inversion of 2D Cellular Automata

- Computer Science, Chemistry
- Theor. Comput. Sci.
- 1995

The co-RNP-completeness (RNP=Random NP) of the following decision problem: “Given a 2-dimensional cellular automaton A, is A reversible when restricted to finite configurations extending a given row?” is proved. Expand

A Random NP-Complete Problem for Inversion of 2D Cellular Automata

- Computer Science
- STACS
- 1995

The co-RNP-completeness (RNP=Random NP) of the following decision problem: “Given a 2-dimensional cellular automaton A, is A reversible when restricted to finite configurations extending a given row?” is proved. Expand

Complex dynamics in life-like rules described with de Bruijn diagrams: Complex and chaotic cellular automata

- Computer Science
- 2012 International Conference on High Performance Computing & Simulation (HPCS)
- 2012

This paper offers a way to explore systematically such patterns by de Bruijn diagrams from initial configurations in two dimensions of the famous Game of Life and the Diffusion Rule. Expand

Cellular automata based S-boxes

- Computer Science
- Cryptography and Communications
- 2018

A systematic investigation of the cryptographic properties of S-boxes defined by CA, proving some upper bounds on their nonlinearity and differential uniformity and proposing a “reverse engineering” method based on De Bruijn graphs to determine whether a specific S-box is expressible through a single CA rule. Expand

#### References

SHOWING 1-10 OF 36 REFERENCES

Computation theory of cellular automata

- Mathematics
- 1984

Self-organizing behaviour in cellular automata is discussed as a computational process. Formal language theory is used to extend dynamical systems theory descriptions of cellular automata. The sets… Expand

Nonrecursive Tilings of the Plane. I

- Mathematics, Computer Science
- J. Symb. Log.
- 1974

The main theorem of this paper is that there exists a finite set of tiles such that the plane can be tiled using T1 at the origin but no such tiling is recursive. Expand

Introduction to Automata Theory, Languages and Computation

- Computer Science
- 1979

This book is a rigorous exposition of formal languages and models of computation, with an introduction to computational complexity, appropriate for upper-level computer science undergraduates who are comfortable with mathematical arguments. Expand

Nonrecursive Tilings of the Plane. II

- Mathematics, Computer Science
- J. Symb. Log.
- 1974

It is shown that there is a finite set of tiles which can tile the plane but not in any recursive way, and an elaboration of Robinson's method of transforming origin-constrained problems into unconstrained Problems is applied to Hanf's origin- Constrained tiling of Part I. Expand

Mot ion P lan ning among Time-Dependent Ob st acles

- Acta Inform atica
- 1988

Mot ion P lan ning among Time-Dependent Obst acles

- Acta Inform atica, 26 (1988) 93-122.
- 1988

On In verti ble Cellular Automata Com plex System s

- On In verti ble Cellular Automata Com plex System s
- 1987

Comp utation T heory of Cellular Au tom at a Communicat ions in Mat bem at ical Ph ysics

- Comp utation T heory of Cellular Au tom at a Communicat ions in Mat bem at ical Ph ysics
- 1984

Comp utation T heory of Cellular Au tomata

- Communicat ions in Matbemat ical Physics, 96 (1) (1984) 15- 57.
- 1984