Embedding arbitrary Boolean circuits into fungal automata

DOI10.1007/978-3-031-20624-5_24MaRDI QIDQ6109020zbMATH OpenFDO

Authors Augusto Modanese, Thomas Worsch

Publication date 26 July 2023

Published in LATIN 2022: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2208.08779

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Abstract: Fungal automata are a variation of the two-dimensional sandpile automaton of Bak, Tang, and Wiesenfeld (Phys. Rev. Lett. 1987). In each step toppling cells emit grains only to some of their neighbors chosen according to a specific update sequence. We show how to embed any Boolean circuit into the initial configuration of a fungal automaton with update sequence $HV$. In particular we give a constructor that, given the description $B$ of a circuit, computes the states of all cells in the finite support of the embedding configuration in $O(log|B|)$ space. As a consequence the prediction problem for fungal automata with update sequence $HV$ is $mathsfP$-complete. This solves an open problem of Goles et al. (Phys. Lett. A, 2020).

Cites work

• Computational universality of fungal sandpile automata
• Crossing information in two-dimensional sandpiles
• Embedding arbitrary Boolean circuits into fungal automata
• How hard is it to predict sandpiles on lattices? A survey
• scientific article; zbMATH DE number 3555903 (Why is no real title available?)
• On uniform circuit complexity
• The computational complexity of one-dimensional sandpiles
• The computational complexity of sandpiles

Cited in

(4)

• On fungal automata
• Computational universality of fungal sandpile automata
• Embedding arbitrary Boolean circuits into fungal automata
• Embedding arbitrary Boolean circuits into fungal automata

This page was built for publication: Embedding arbitrary Boolean circuits into fungal automata

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