Complete simulation of automata networks

DOI10.1016/J.JCSS.2019.12.001MaRDI QIDQ2301357zbMATH OpenOpenAlexFDO

Authors Florian Bridoux, Alonso Castillo-Ramirez, Maximilien Gadouleau

Publication date 24 February 2020

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.00169, http://dro.dur.ac.uk/29811/1/29811.pdf

zbMATH Keywords

automata networkscomplete simulationcomputational difficultymemoryless computationmodels of computationsymmetric grouptransformation semigroups

Mathematics Subject Classification ID

Other nonclassical models of computation (68Q09) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Abstract: Consider a finite set $A$ and an integer $ngeq1$. This paper studies the concept of complete simulation in the context of semigroups of transformations of $A^n$, also known as finite state-homogeneous automata networks. For $mgeqn$, a transformation of $A^m$ is emph{$n$-complete of size $m$} if it may simulate every transformation of $A^n$ by updating one coordinate (or register) at a time. Using tools from memoryless computation, it is established that there is no $n$-complete transformation of size $n$, but there is such a transformation of size $n+1$. By studying the the time of simulation of various $n$-complete transformations, it is conjectured that the maximal time of simulation of any $n$-complete transformation is at least $2n$. A transformation of $A^m$ is emph{sequentially $n$-complete of size $m$} if it may sequentially simulate every finite sequence of transformations of $A^n$; in this case, minimal examples and bounds for the size and time of simulation are determined. It is also shown that there is no $n$-complete transformation that updates all the registers in parallel, but that there exists a sequentally $n$-complete transformation that updates all but one register in parallel. This illustrates the strengths and weaknesses of parallel models of computation, such as cellular automata.

Recommendations

• scientific article; zbMATH DE number 1355187
• scientific article; zbMATH DE number 4078823
• Sequential simulation of parallel iterations and applications
• scientific article; zbMATH DE number 1270383
• Complete system of equivalent transformations for multitape automata

Cites work

• A note on isomorphic simulation of automata by networks of two-state automata
• Algebraic Theory of Automata Networks
• Closed iterative calculus
• Computation of Boolean functions on networks of binary automata
• Computation on binary tree-networks
• Computation with no memory, and rearrangeable multicast networks
• Computing in matrix groups without memory
• Computing in permutation groups without memory
• Elementary decompositions of arbitrary maps over finite sets
• scientific article; zbMATH DE number 4078823 (Why is no real title available?)
• Mapping Computation with No Memory
• Memoryless computation: new results, constructions, and extensions
• Network information flow
• Parallel calculation of a linear mapping on a computer network
• Parallel realization of permutations over trees
• Permutation Factorization on Star-Connected Networks of Binary Automata
• Quadratic sequential computations of Boolean mappings
• Sequential computation of linear Boolean mappings
• Sequentialization and procedural complexity in automata networks
• Three generators for minimal writing-space computations

Cited in

(4)

• Sequentialization and procedural complexity in automata networks
• On simulation in automata networks
• scientific article; zbMATH DE number 1355187 (Why is no real title available?)
• On the influence of the interaction graph on a finite dynamical system

This page was built for publication: Complete simulation of automata networks

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