Latin Hypercubes and Cellular Automata

DOI10.1007/978-3-030-61588-8_11arXiv2004.07131MaRDI QIDQ6338752FDOQ6338752

Authors: Maximilien Gadouleau, Luca Mariot 

Publication date: 15 April 2020

Abstract: 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 $k>2$. In particular, we prove 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. Further, we derive the number of $k$-dimensional Latin hypercubes generated by LBCA by counting the number of paths of length $k-3$ on this de Bruijn graph.

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

This page was built for publication: Latin Hypercubes and Cellular Automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6338752)