Sequentialization and procedural complexity in automata networks
From MaRDI portal
Publication:2055976
Abstract: In this article we consider finite automata networks (ANs) with two kinds of update schedules: the parallel one (all automata are updated all together) and the sequential ones (the automata are updated periodically one at a time according to a total order w). The cost of sequentialization of a given AN h is the number of additional automata required to simulate h by a sequential AN with the same alphabet. We construct, for any n and q, an AN h of size n and alphabet size q whose cost of sequentialization is at least n/3. We also show that, if q 4, we can find one whose cost is at least n/2 -- log q (n). We prove that n/2 + log q (n/2 + 1) is an upper bound for the cost of sequentialization of any AN h of size n and alphabet size q. Finally, we exhibit the exact relation between the cost of sequentialization of h and its procedural complexity with unlimited memory and prove that its cost of sequentialization is less than or equal to the pathwidth of its interaction graph.
Recommendations
Cites work
- A logical calculus of the ideas immanent in nervous activity
- A new necessary condition on interaction graphs for multistationarity
- Asynchronous simulation of Boolean networks by monotone Boolean networks
- Closed iterative calculus
- Combinatorics on update digraphs in Boolean networks
- Comparison between parallel and serial dynamics of Boolean networks
- Computation with no memory, and rearrangeable multicast networks
- Dichotomy results for fixed-point existence problems for Boolean dynamical systems
- Digraph searching, directed vertex separation and directed pathwidth
- Fixed points and connections between positive and negative cycles in Boolean networks
- Fixed points in conjunctive networks and maximal independent sets in graph contractions
- scientific article; zbMATH DE number 45557 (Why is no real title available?)
- Limit cycles and update digraphs in Boolean networks
- Mapping Computation with No Memory
- Memoryless computation: new results, constructions, and extensions
- 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 number of update digraphs and its relation with the feedback arc sets and tournaments
- Sequential simulation of parallel iterations and applications
- Static Analysis of Boolean Networks Based on Interaction Graphs: A Survey
- The vertex separation and search number of a graph
Cited in
(8)- Sequential dynamics of high order polynomial automata networks: An application to the Erlang fixed-point equations
- Complete simulation of automata networks
- On the cost of simulating a parallel Boolean automata network by a block-sequential one
- An order parameter for networks of automata
- scientific article; zbMATH DE number 32620 (Why is no real title available?)
- Invariance under the order of updating in automata networks
- Turning block-sequential automata networks into smaller parallel networks with isomorphic limit dynamics
- Nets, sequential components and concurrency relations
This page was built for publication: Sequentialization and procedural complexity in automata networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2055976)
