Latin Hypercubes and Cellular Automata

Latin Hypercubes and Cellular Automata

Gadouleau, Maximilien (Durham University)
Mariot, L. (TU Delft Cyber Security)

Zenil, Hector (editor)

2020

Latin squares and hypercubes are combinatorial designs with several applications in statistics, cryptography and coding theory. In this paper, we generalize a construction of Latin squares based on bipermutive cellular automata (CA) to the case of Latin hypercubes of dimension. In particular, we prove that linear bipermutive CA (LBCA) yielding Latin hypercubes of dimension 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. Further, we derive the number of k-dimensional Latin hypercubes generated by LBCA by counting the number of paths of length on this de Bruijn graph.

Bipermutivity
Cellular automata
De bruijn graphs
Latin hypercubes
Latin squares
Toeplitz matrices

http://resolver.tudelft.nl/uuid:cb9aaba3-0f2c-4280-a823-4515c2a84be2

https://doi.org/10.1007/978-3-030-61588-8_11

Springer Science+Business Media, Cham

978-3-030-61587-1

Cellular Automata and Discrete Complex Systems: 26th IFIP WG 1.5 International Workshop, AUTOMATA 2020, Proceedings

26th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems, AUTOMATA 2020, 2020-08-10 → 2020-08-12, Stockholm, Sweden

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 0302-9743, 12286

Institutional Repository

conference paper

© 2020 Maximilien Gadouleau, L. Mariot