Latin Hypercubes and Cellular Automata

Maximilien Gadouleau, Luca Mariot

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

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. 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.

Original languageEnglish
Title of host publicationCellular Automata and Discrete Complex Systems
Subtitle of host publication26th IFIP WG 1.5 International Workshop, AUTOMATA 2020, Proceedings
EditorsHector Zenil
Place of PublicationCham
PublisherSpringer
Pages139-151
Number of pages13
ISBN (Electronic)978-3-030-61588-8
ISBN (Print)978-3-030-61587-1
DOIs
Publication statusPublished - 2020
Event26th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems, AUTOMATA 2020 - Stockholm, Sweden
Duration: 10 Aug 202012 Aug 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer
Volume12286
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference26th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems, AUTOMATA 2020
Country/TerritorySweden
CityStockholm
Period10/08/2012/08/20

Keywords

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

Fingerprint

Dive into the research topics of 'Latin Hypercubes and Cellular Automata'. Together they form a unique fingerprint.

Cite this