Foundations of block-parallel automata networks

DOI10.1016/J.TCS.2025.115572MaRDI QIDQ6891684zbMATH OpenFDO

Authors Kévin Perrot, Sylvain Sené, Léah Tapin

Publication date 2 December 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115572

zbMATH Keywords

automata networksblock-parallel update modescomputational complexitycountingenumerationequivalence classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cites work

• A complexity theory for hard enumeration problems
• A logical calculus of the ideas immanent in nervous activity
• About block-parallel Boolean networks: a position paper
• Asynchronous threshold networks
• Block-sequential update schedules and Boolean automata circuits
• Combinatorics on update digraphs in Boolean networks
• Comparison between parallel and serial dynamics of Boolean networks
• Complexity of limit-cycle problems in Boolean networks
• Complexity of the dynamics of reaction systems
• Computational complexity of minimal trap spaces in Boolean networks
• Developments in Language Theory
• scientific article; zbMATH DE number 4201618 (Why is no real title available?)
• scientific article; zbMATH DE number 4042465 (Why is no real title available?)
• scientific article; zbMATH DE number 45557 (Why is no real title available?)
• Limit cycles and update digraphs in Boolean networks
• On the computational complexity of finite cellular automata
• On the cost of simulating a parallel Boolean automata network by a block-sequential one
• On the number of different dynamics in Boolean networks with deterministic update schedules
• On the power of generalized Mod-classes
• PSPACE-completeness of majority automata networks
• Reversible space equals deterministic space
• The complexity of iterated reversible computation
• The complexity of reversible cellular automata
• Theory of reversible computing
• Turning block-sequential automata networks into smaller parallel networks with isomorphic limit dynamics

This page was built for publication: Foundations of block-parallel automata networks

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