Embedding Arbitrary Boolean Circuits into Fungal Automata

Thumbnail Image

Access rights

openAccess
publishedVersion

URL

Journal Title

Journal ISSN

Volume Title

A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)

Authors

Date

2024-07

Department

Department of Computer Science

Major/Subject

Mcode

Degree programme

Language

en

Pages

23

Series

Algorithmica, Volume 86, issue 7, pp. 2069-2091

Abstract

Fungal automata are a variation of the two-dimensional sandpile automaton of Bak et al. (Phys Rev Lett 59(4):381–384, 1987. https://doi.org/10.1103/PhysRevLett.59.381). 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(logB) space. As a consequence the prediction problem for fungal automata with update sequence HV is P-complete. This solves an open problem of Goles et al. (Phys Lett A 384(22):126541, 2020. https://doi.org/10.1016/j.physleta.2020.126541).

Description

Publisher Copyright: © The Author(s) 2024.

Keywords

Fungal automata, P-completeness, Prediction problem, Two-dimensional cellular automata

Other note

DOI

10.1007/s00453-024-01222-7

Citation

Modanese, A & Worsch, T 2024, 'Embedding Arbitrary Boolean Circuits into Fungal Automata', Algorithmica, vol. 86, no. 7, pp. 2069-2091. https://doi.org/10.1007/s00453-024-01222-7

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202408065254

Collections

[article-cris] Perustieteiden korkeakoulu / SCI