Volume
OASIcs, Volume 90
27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)
Publication Details
- published at: 2021-06-28
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-189-4
- DBLP: db/conf/automata/automata2021
Access Numbers
- Detailed Access Statistics available here
-
Total Document Accesses (updated on a weekly basis):
0PDF Downloads
Documents
No documents found matching your filter selection.
Document
Complete Volume
OASIcs, Volume 90, AUTOMATA 2021, Complete Volume
Abstract
OASIcs, Volume 90, AUTOMATA 2021, Complete Volume
Cite as
27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 1-186, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@Proceedings{castilloramirez_et_al:OASIcs.AUTOMATA.2021,
title = {{OASIcs, Volume 90, AUTOMATA 2021, Complete Volume}},
booktitle = {27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
pages = {1--186},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-189-4},
ISSN = {2190-6807},
year = {2021},
volume = {90},
editor = {Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.AUTOMATA.2021},
URN = {urn:nbn:de:0030-drops-140087},
doi = {10.4230/OASIcs.AUTOMATA.2021},
annote = {Keywords: OASIcs, Volume 90, AUTOMATA 2021, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization
Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as
27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{castilloramirez_et_al:OASIcs.AUTOMATA.2021.0,
author = {Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
title = {{Front Matter, Table of Contents, Preface, Conference Organization}},
booktitle = {27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
pages = {0:i--0:x},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-189-4},
ISSN = {2190-6807},
year = {2021},
volume = {90},
editor = {Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.AUTOMATA.2021.0},
URN = {urn:nbn:de:0030-drops-140092},
doi = {10.4230/OASIcs.AUTOMATA.2021.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
Dynamical Properties of Disjunctive Boolean Networks (Invited Talk)
Abstract
A Boolean network is a mapping f :{0,1}ⁿ → {0,1}ⁿ, which can be used to model networks of n interacting entities, each having a local Boolean state that evolves over time according to a deterministic function of the current configuration of states. In this paper, we are interested in disjunctive networks, where each local function is simply the disjunction of a set of variables. As such, this network is somewhat homogeneous, though the number of variables may vary from entity to entity, thus yielding a generalised cellular automaton. The aim of this paper is to review some of the main results, derive some additional fundamental results, and highlight some open problems on the dynamics of disjunctive networks. We first review the different defining characteristics of disjunctive networks and several ways of representing them using graphs, Boolean matrices, or binary relations. We then focus on three dynamical properties of disjunctive networks: their image points, their periodic points, and their fixed points. For each class of points, we review how they can be characterised and study how many they could be. The paper finishes with different avenues for future work on the dynamics of disjunctive networks and how to generalise them.
Cite as
Maximilien Gadouleau. Dynamical Properties of Disjunctive Boolean Networks (Invited Talk). In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{gadouleau:OASIcs.AUTOMATA.2021.1,
author = {Gadouleau, Maximilien},
title = {{Dynamical Properties of Disjunctive Boolean Networks}},
booktitle = {27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
pages = {1:1--1:15},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-189-4},
ISSN = {2190-6807},
year = {2021},
volume = {90},
editor = {Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.AUTOMATA.2021.1},
URN = {urn:nbn:de:0030-drops-140105},
doi = {10.4230/OASIcs.AUTOMATA.2021.1},
annote = {Keywords: Boolean networks, disjunction, conjunction, fixed points, rank}
}
Document
Invited Talk
Regular Languages: To Finite Automata and Beyond (Invited Talk)
Abstract
It is well known that the class of regular languages coincides with the class of languages recognized by finite automata. Nevertheless, many other characterizations of this class in terms of computational devices and generative models are present in the literature. For example, by suitably restricting more powerful models such as context-free grammars, pushdown automata, and Turing machines, it is possible to obtain formal models that generate or recognize regular languages only. These restricted formalisms provide alternative representations of regular languages that may be significantly more concise than other models that share the same expressive power.
The goal of this work is to provide an overview of old and recent results on these formal systems from a descriptional complexity perspective, that is by considering the relationships between the sizes of such devices. We also present some results related to the investigation of the famous question posed by Sakoda and Sipser in 1978, concerning the size blowups from nondeterministic finite automata to two-way deterministic finite automata.
Cite as
Luca Prigioniero. Regular Languages: To Finite Automata and Beyond (Invited Talk). In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{prigioniero:OASIcs.AUTOMATA.2021.2,
author = {Prigioniero, Luca},
title = {{Regular Languages: To Finite Automata and Beyond}},
booktitle = {27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
pages = {2:1--2:16},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-189-4},
ISSN = {2190-6807},
year = {2021},
volume = {90},
editor = {Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.AUTOMATA.2021.2},
URN = {urn:nbn:de:0030-drops-140115},
doi = {10.4230/OASIcs.AUTOMATA.2021.2},
annote = {Keywords: Regular languages, descriptional complexity, finite automata}
}
Document
Invited Talk
Reversible Cellular Automata in Presence of Noise Rapidly Forget Everything (Invited Talk)
Abstract
We consider reversible and surjective cellular automata perturbed with noise. We show that, in the presence of positive additive noise, the cellular automaton forgets all the information regarding its initial configuration exponentially fast. In particular, the state of a finite collection of cells with diameter n becomes indistinguishable from pure noise after O(log n) time steps. This highlights the seemingly unavoidable need for irreversibility in order to perform scalable reliable computation in the presence of noise.
Cite as
Siamak Taati. Reversible Cellular Automata in Presence of Noise Rapidly Forget Everything (Invited Talk). In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{taati:OASIcs.AUTOMATA.2021.3,
author = {Taati, Siamak},
title = {{Reversible Cellular Automata in Presence of Noise Rapidly Forget Everything}},
booktitle = {27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
pages = {3:1--3:15},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-189-4},
ISSN = {2190-6807},
year = {2021},
volume = {90},
editor = {Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.AUTOMATA.2021.3},
URN = {urn:nbn:de:0030-drops-140128},
doi = {10.4230/OASIcs.AUTOMATA.2021.3},
annote = {Keywords: Reversible cellular automata, surjective cellular automata, noise, probabilistic cellular automata, ergodicity, entropy, reversible computing, reliable computing, fault tolerance}
}
Document
Invited Talk
Fixed Point Constructions in Tilings and Cellular Automata (Invited Talk)
Abstract
The fixed point construction is a method for designing tile sets and cellular automata with highly nontrivial dynamical and computational properties. It produces an infinite hierarchy of systems where each layer simulates the next one. The simulations are implemented entirely by computations of Turing machines embedded in the tilings or spacetime diagrams. We present an overview of the construction and list its applications in the literature.
Cite as
Ilkka Törmä. Fixed Point Constructions in Tilings and Cellular Automata (Invited Talk). In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 4:1-4:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{torma:OASIcs.AUTOMATA.2021.4,
author = {T\"{o}rm\"{a}, Ilkka},
title = {{Fixed Point Constructions in Tilings and Cellular Automata}},
booktitle = {27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
pages = {4:1--4:13},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-189-4},
ISSN = {2190-6807},
year = {2021},
volume = {90},
editor = {Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.AUTOMATA.2021.4},
URN = {urn:nbn:de:0030-drops-140135},
doi = {10.4230/OASIcs.AUTOMATA.2021.4},
annote = {Keywords: Tilings, Wang tiles, cellular automata, multidimensional symbolic dynamics, self-simulation}
}
Document
Dynamical Algebraic Combinatorics, Asynchronous Cellular Automata, and Toggling Independent Sets
Abstract
Though iterated maps and dynamical systems are not new to combinatorics, they have enjoyed a renewed prominence over the past decade through the elevation of the subfield that has become known as dynamical algebraic combinatorics. Some of the problems that have gained popularity can also be cast and analyzed as finite asynchronous cellular automata (CA). However, these two fields are fairly separate, and while there are some individuals who work in both, that is the exception rather than the norm. In this article, we will describe our ongoing work on toggling independent sets on graphs. This will be preceded by an overview of how this project arose from new combinatorial problems involving homomesy, toggling, and resonance. Though the techniques that we explore are directly applicable to ECA rule 1, many of them can be generalized to other cellular automata. Moreover, some of the ideas that we borrow from cellular automata can be adapted to problems in dynamical algebraic combinatorics. It is our hope that this article will inspire new problems in both fields and connections between them.
Cite as
Laurent David, Colin Defant, Michael Joseph, Matthew Macauley, and Alex McDonough. Dynamical Algebraic Combinatorics, Asynchronous Cellular Automata, and Toggling Independent Sets. In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{david_et_al:OASIcs.AUTOMATA.2021.5,
author = {David, Laurent and Defant, Colin and Joseph, Michael and Macauley, Matthew and McDonough, Alex},
title = {{Dynamical Algebraic Combinatorics, Asynchronous Cellular Automata, and Toggling Independent Sets}},
booktitle = {27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
pages = {5:1--5:16},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-189-4},
ISSN = {2190-6807},
year = {2021},
volume = {90},
editor = {Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.AUTOMATA.2021.5},
URN = {urn:nbn:de:0030-drops-140145},
doi = {10.4230/OASIcs.AUTOMATA.2021.5},
annote = {Keywords: Asynchronous cellular automata, Covering space, Coxeter element, Dynamical algebraic combinatorics, Group action, Homomesy, Independent set, Resonance, Toggling, Toric equivalence}
}
Document
Rice’s Theorem for Generic Limit Sets of Cellular Automata
Abstract
The generic limit set of a cellular automaton is a topologically defined set of configurations that intends to capture the asymptotic behaviours while avoiding atypical ones. It was defined by Milnor then studied by Djenaoui and Guillon first, and by Törmä later. They gave properties of this set related to the dynamics of the cellular automaton, and the maximal complexity of its language. In this paper, we prove that every non trivial property of these generic limit sets of cellular automata is undecidable.
Cite as
Martin Delacourt. Rice’s Theorem for Generic Limit Sets of Cellular Automata. In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 6:1-6:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{delacourt:OASIcs.AUTOMATA.2021.6,
author = {Delacourt, Martin},
title = {{Rice’s Theorem for Generic Limit Sets of Cellular Automata}},
booktitle = {27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
pages = {6:1--6:12},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-189-4},
ISSN = {2190-6807},
year = {2021},
volume = {90},
editor = {Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.AUTOMATA.2021.6},
URN = {urn:nbn:de:0030-drops-140151},
doi = {10.4230/OASIcs.AUTOMATA.2021.6},
annote = {Keywords: cellular automata, dynamical systems, generic-limit sets, Rice’s theorem, subshifts}
}
Document
Cellular Automata and Kan Extensions
Abstract
In this paper, we formalize precisely the sense in which the application of a cellular automaton to partial configurations is a natural extension of its local transition function through the categorical notion of Kan extension. In fact, the two possible ways to do such an extension and the ingredients involved in their definition are related through Kan extensions in many ways. These relations provide additional links between computer science and category theory, and also give a new point of view on the famous Curtis-Hedlund theorem of cellular automata from the extended topological point of view provided by category theory. These links also allow to relatively easily generalize concepts pioneered by cellular automata to arbitrary kinds of possibly evolving spaces. No prior knowledge of category theory is assumed.
Cite as
Alexandre Fernandez, Luidnel Maignan, and Antoine Spicher. Cellular Automata and Kan Extensions. In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 7:1-7:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{fernandez_et_al:OASIcs.AUTOMATA.2021.7,
author = {Fernandez, Alexandre and Maignan, Luidnel and Spicher, Antoine},
title = {{Cellular Automata and Kan Extensions}},
booktitle = {27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
pages = {7:1--7:12},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-189-4},
ISSN = {2190-6807},
year = {2021},
volume = {90},
editor = {Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.AUTOMATA.2021.7},
URN = {urn:nbn:de:0030-drops-140160},
doi = {10.4230/OASIcs.AUTOMATA.2021.7},
annote = {Keywords: Cellular Automata, Kan Extension, Category Theory, Global Transformation}
}
Document
Conjunctive Grammars, Cellular Automata and Logic
Abstract
The expressive power of the class Conj of conjunctive languages, i.e. languages generated by the conjunctive grammars of Okhotin, is largely unknown, while its restriction LinConj to linear conjunctive grammars equals the class of languages recognized by real-time one-dimensional one-way cellular automata. We prove two weakened versions of the open question Conj ⊆? RealTime1CA, where RealTime1CA is the class of languages recognized by real-time one-dimensional two-way cellular automata:
1) it is true for unary languages;
2) Conj ⊆ RealTime2OCA, i.e. any conjunctive language is recognized by a real-time two-dimensional one-way cellular automaton. Interestingly, we express the rules of a conjunctive grammar in two Horn logics, which exactly characterize the complexity classes RealTime1CA and RealTime2OCA.
Cite as
Théo Grente and Étienne Grandjean. Conjunctive Grammars, Cellular Automata and Logic. In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{grente_et_al:OASIcs.AUTOMATA.2021.8,
author = {Grente, Th\'{e}o and Grandjean, \'{E}tienne},
title = {{Conjunctive Grammars, Cellular Automata and Logic}},
booktitle = {27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
pages = {8:1--8:19},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-189-4},
ISSN = {2190-6807},
year = {2021},
volume = {90},
editor = {Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.AUTOMATA.2021.8},
URN = {urn:nbn:de:0030-drops-140170},
doi = {10.4230/OASIcs.AUTOMATA.2021.8},
annote = {Keywords: Computational complexity, Real-time, One-dimensional/two-dimensional cellular automaton, One-way/two-way communication, Grid-circuit, Unary language, Descriptive complexity, Existential second-order logic, Horn formula}
}
Document
An Effective Construction for Cut-And-Project Rhombus Tilings with Global n-Fold Rotational Symmetry
Abstract
We give an explicit and effective construction for rhombus cut-and-project tilings with global n-fold rotational symmetry for any n. This construction is based on the dualization of regular n-fold multigrids. The main point is to prove the regularity of these multigrids, for this we use a result on trigonometric diophantine equations. A SageMath program that computes these tilings and outputs svg files is publicly available in [Lutfalla, 2021].
Cite as
Victor H. Lutfalla. An Effective Construction for Cut-And-Project Rhombus Tilings with Global n-Fold Rotational Symmetry. In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{lutfalla:OASIcs.AUTOMATA.2021.9,
author = {Lutfalla, Victor H.},
title = {{An Effective Construction for Cut-And-Project Rhombus Tilings with Global n-Fold Rotational Symmetry}},
booktitle = {27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
pages = {9:1--9:12},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-189-4},
ISSN = {2190-6807},
year = {2021},
volume = {90},
editor = {Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.AUTOMATA.2021.9},
URN = {urn:nbn:de:0030-drops-140182},
doi = {10.4230/OASIcs.AUTOMATA.2021.9},
annote = {Keywords: Cut-and-project tiling, Rhombus tiling, Aperiodic order, Rotational symmetry, De Bruijn multigrid, Trigonometric diophantine equations}
}
Document
Non-Deterministic Updates of Boolean Networks
Abstract
Boolean networks are discrete dynamical systems where each automaton has its own Boolean function for computing its state according to the configuration of the network. The updating mode then determines how the configuration of the network evolves over time. Many of updating modes from the literature, including synchronous and asynchronous modes, can be defined as the composition of elementary deterministic configuration updates, i.e., by functions mapping configurations of the network. Nevertheless, alternative dynamics have been introduced using ad-hoc auxiliary objects, such as that resulting from binary projections of Memory Boolean networks, or that resulting from additional pseudo-states for Most Permissive Boolean networks. One may wonder whether these latter dynamics can still be classified as updating modes of finite Boolean networks, or belong to a different class of dynamical systems. In this paper, we study the extension of updating modes to the composition of non-deterministic updates, i.e., mapping sets of finite configurations. We show that the above dynamics can be expressed in this framework, enabling a better understanding of them as updating modes of Boolean networks. More generally, we argue that non-deterministic updates pave the way to a unifying framework for expressing complex updating modes, some of them enabling transitions that cannot be computed with elementary and non-elementary deterministic updates.
Cite as
Loïc Paulevé and Sylvain Sené. Non-Deterministic Updates of Boolean Networks. In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{pauleve_et_al:OASIcs.AUTOMATA.2021.10,
author = {Paulev\'{e}, Lo\"{i}c and Sen\'{e}, Sylvain},
title = {{Non-Deterministic Updates of Boolean Networks}},
booktitle = {27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
pages = {10:1--10:16},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-189-4},
ISSN = {2190-6807},
year = {2021},
volume = {90},
editor = {Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.AUTOMATA.2021.10},
URN = {urn:nbn:de:0030-drops-140196},
doi = {10.4230/OASIcs.AUTOMATA.2021.10},
annote = {Keywords: Natural computing, discrete dynamical systems, semantics}
}
Document
Von Neumann Regularity, Split Epicness and Elementary Cellular Automata
Abstract
We show that a cellular automaton on a mixing subshift of finite type is a von Neumann regular element in the semigroup of cellular automata if and only if it is split epic onto its image in the category of sofic shifts and block maps. It follows from [S.-Törmä, 2015] that von Neumann regularity is decidable condition, and we decide it for all elementary CA.
Cite as
Ville Salo. Von Neumann Regularity, Split Epicness and Elementary Cellular Automata. In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 11:1-11:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{salo:OASIcs.AUTOMATA.2021.11,
author = {Salo, Ville},
title = {{Von Neumann Regularity, Split Epicness and Elementary Cellular Automata}},
booktitle = {27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
pages = {11:1--11:10},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-189-4},
ISSN = {2190-6807},
year = {2021},
volume = {90},
editor = {Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.AUTOMATA.2021.11},
URN = {urn:nbn:de:0030-drops-140209},
doi = {10.4230/OASIcs.AUTOMATA.2021.11},
annote = {Keywords: cellular automata, elementary cellular automata, von Neumann regularity, split epicness}
}
Document
State-Based Opacity of Real-Time Automata
Abstract
State-based opacity is a special type of opacity as a confidentiality property, which describes whether an external intruder cannot make for sure whether secret states of a system have been visited by observing generated outputs, given that the intruder knows complete knowledge of the system’s structure but can only see generated outputs. When the time of visiting secret states is specified as the initial time, the current time, any past time, and at most K steps prior to the current time, the notions of state-based opacity can be formulated as initial-state opacity, current-state opacity, infinite-step opacity, and K-step opacity, respectively. In this paper, we formulate the four versions of opacity for real-time automata which are a widely-used model of real-time systems, and give 2-EXPTIME verification algorithms for the four notions by defining appropriate notions of observer and reverse observer for real-time automata that are computable in 2-EXPTIME.
Cite as
Kuize Zhang. State-Based Opacity of Real-Time Automata. In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
Copy BibTex To Clipboard
@InProceedings{zhang:OASIcs.AUTOMATA.2021.12,
author = {Zhang, Kuize},
title = {{State-Based Opacity of Real-Time Automata}},
booktitle = {27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
pages = {12:1--12:15},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-189-4},
ISSN = {2190-6807},
year = {2021},
volume = {90},
editor = {Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.AUTOMATA.2021.12},
URN = {urn:nbn:de:0030-drops-140217},
doi = {10.4230/OASIcs.AUTOMATA.2021.12},
annote = {Keywords: real-time automaton, state-based opacity, observer, verification}
}