Top

Natural Computing

Published in:

25-05-2023

Asynchronous, finite dynamical systems

Author: Henning S. Mortveit

Published in: Natural Computing | Issue 2/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Asynchronous, finite dynamical systems are constructed by composing vertex functions \(f_1\), \(f_2\) through \(f_n\) using an order \(\pi\) on \(\{1,2,\ldots ,n\}\) to form maps \(f_\pi\). This article provides a systematic review and new results for comparing the dynamics of maps \(f_\pi\) and \(f_{\pi '}\) formed using different composition orders \(\pi\) and \(\pi '\). Comparisons are done at the level of (i) entire phase spaces (functional equivalence), (ii) the periodic orbits (cycle equivalence), and (iii) topological conjugation (dynamical equivalence). Conditions and criteria are given in terms of the dependency graph G of the vertex functions along with associated structures such as the acyclic orientations of G and the automorphism group of G. For each type of equivalence, graph-theoretic measures are provided that give an upper bound for the number of distinct structures that can be observed up to the respective notion of equivalence. Several connections to existing mathematical theory (e.g., combinatorics and graphs) are presented along with open questions.

previous article Analysis of inter and intra-front operations in multi-modal multi-objective optimization problems

next article Enhancing differential evolution algorithm through a population size adaptation strategy

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

git@github.com:HenningMortveit/gds-framework-python.git

Note that the inversion result is incorrectly stated in (Mortveit and Reidys 2007) where the condition of \(\pi\)-invariance is not included. Strictly speaking, \(\pi\)-invariance is a sufficient condition, and it is not known whether a less restrictive condition may suffice.

Evaluating \({\bar{\alpha }}(Q_2^3)\) is tedious: any insights from the reader regarding systematic, efficient evaluations would be highly interesting!

Aracena J, Goles E, Moreira A et al (2009) On the robustness of update schedules in Boolean networks. Biosystems 97(1):1–8. https://doi.org/10.1016/j.biosystems.2009.03.006CrossRef

Aracena J, Fanchon E, Montalva M et al (2011) Combinatorics on update digraphs in Boolean networks. Discret Appl Math 159(6):401–409. https://doi.org/10.1016/j.dam.2010.10.010MathSciNetCrossRefMATH

Balbi PP, Formenti E, Perrot K et al (2022) Non-maximal sensitivity to synchronism in elementary cellular automata: exact asymptotic measures. Theor Comput Sci 926:21–50. https://doi.org/10.1016/j.tcs.2022.05.024MathSciNetCrossRefMATH

Barrett CL, Hunt HB III, Marathe MV et al (2006) Complexity of reachability problems for finite discrete sequential dynamical systems. J Comput Syst Sci 72:1317–1345CrossRefMATH

Cartier P, Foata D (1969) Problemes combinatoires de commutation et reárrangements. Lecture notes in mathematics. Springer, BerlinCrossRefMATH

Chen RXF, McNitt JA, Mortveit HS et al (2023) Lipschitz continuity under toric equivalence for asynchronous Boolean networks. Chaos 33(023):118. https://doi.org/10.1063/5.0119621MathSciNetCrossRef

Demongeot J, Elena A, Sené S (2008) Robustness in regulatory networks: a multi-disciplinary approach. Acta Biotheor 56(1):27–49. https://doi.org/10.1007/s10441-008-9029-xCrossRef

Demongeot J, Goles E, Morvan M et al (2010) Attraction basins as gauges of robustness against boundary conditions in biological complex systems. PLoS ONE 5(8):e11,793. https://doi.org/10.1371/journal.pone.0011793CrossRef

Develin M, Macauley M, Reiner V (2015) Toric partial orders. Trans Am Math Soc 368(4):2263–2287. https://doi.org/10.1090/tran/6356MathSciNetCrossRefMATH

Diestel R (2005) Graph theory, 3rd edn. Springer, BerlinMATH

Eriksson H, Eriksson K (2009) Conjugacy of Coxeter elements. Electron J Comb 16:4MathSciNetCrossRefMATH

Fatès N (2013) A guided tour of asynchronous cellular automata. In: Kari J, Kutrib M, Malcher A (eds) Cellular automata and discrete complex systems. Springer, Berlin, Heidelberg, pp 15–30CrossRefMATH

Fatès N (2020) A tutorial on elementary cellular automata with fully asynchronous updating. Nat Comput 10:179–197. https://doi.org/10.1007/s11047-020-09782-7MathSciNetCrossRef

Gioan E (2007) Enumerating degree sequences in digraphs and a cycle-cocycle reversing system. Eur J Comb 28:1351–1366MathSciNetCrossRefMATH

Goles E, Montalva-Medel M, Mortveit H et al (2015) Block invariance in elementary cellular automata. J Cell Autom 10(1–2):119–135MathSciNetMATH

Goles E, Montalva-Medel M, MacLean S et al (2018) Block invariance in a family of elementary cellular automata. J Cell Autom 13(1–2):15–32MathSciNetMATH

Jaeger F, Vertigan DL, Welsh DJA (1990) On the computational complexity of the Jones and Tutte polynomials. Math Proc Camb Philos Soc 108:35–53MathSciNetCrossRefMATH

Liebchen C, Rizzi R (2007) Classes of cycle bases. Discret Appl Math 155(3):337–355. https://doi.org/10.1016/j.dam.2006.06.007MathSciNetCrossRefMATH

Macauley M, Mortveit HS (2008) On enumeration of conjugacy classes of Coxeter elements. Proc Am Math Soc 136(12):4157–4165. https://doi.org/10.1090/S0002-9939-09-09884-0. arXiv:math.CO/0711.1140MathSciNetCrossRefMATH

Macauley M, Mortveit HS (2009) Cycle equivalence of graph dynamical systems. Nonlinearity 22(2):421–436. https://doi.org/10.1088/0951-7715/22/2/010. arXiv:math.DS/0709.0291MathSciNetCrossRefMATH

Macauley M, Mortveit HS (2011) Posets from admissible coxeter sequences. Electron J Comb 18:197MathSciNetCrossRefMATH

Macauley M, Mortveit HS (2013) An atlas of limit set dynamics for asynchronous elementary cellular automata. Theor Comput Sci 504:26–37. https://doi.org/10.1016/j.tcs.2012.09.015. (discrete Mathematical Structures: From Dynamics to Complexity - DISCO 2011 24-26 November, 2011, Santiago, Chile)MathSciNetCrossRefMATH

Macauley M, McCammond J, Mortveit HS (2008) Order independence in asynchronous cellular automata. J Cell Autom 3(1):37–56 arXiv:Math.DS/0707.2360MathSciNetMATH

Macauley M, McCammond J, Mortveit HS (2011) Dynamics groups of asynchronous cellular automata. J Algebr Comb 33(1):11–35. https://doi.org/10.1007/s10801-010-0231-y. arXiv:math.DS/0808.1238MathSciNetCrossRefMATH

Mortveit HS, Pederson RD (2019) Attractor stability in finite asynchronous biological system models. Bull Math Biol. https://doi.org/10.1007/s11538-018-00565-xMathSciNetCrossRefMATH

Mortveit HS, Reidys CM (2001) Discrete, sequential dynamical systems. Discret Math 226:281–295. https://doi.org/10.1016/S0012-365X(00)00115-1MathSciNetCrossRefMATH

Mortveit HS, Reidys CM (2007) An introduction to sequential dynamical systems. Universitext, Springer, ChamMATH

Novik I, Postnikov A, Sturmfels B (2002) Syzygies of oriented matroids. Duke Math J 111:287–317MathSciNetCrossRefMATH

Palma E, Salinas L, Aracena J (2015) Enumeration and extension of non-equivalent deterministic update schedules in Boolean networks. Bioinformatics 32(5):722–729. https://doi.org/10.1093/bioinformatics/btv628CrossRef

Perrot K, Sené S, Venturini L (2020) #p-completeness of counting update digraphs, cacti, and series-parallel decomposition method. In: Anselmo M, Della Vedova G, Manea F et al (eds) Beyond the horizon of computability. Springer, Cham, pp 326–338CrossRefMATH

Reidys CM (1998) Acyclic orientations of random graphs. Adv Appl Math 21(2):181–192MathSciNetCrossRefMATH

Rosenkrantz DJ, Marathe MV, Hunt III HB, et al (2015) Analysis problems for graphical dynamical systems: a unified approach through graph predicates. In: Proceedings of the 2015 international conference on autonomous agents and multiagent systems pages, pp 1501–1509, https://www.ifaamas.org/Proceedings/aamas2015/aamas/p1501.pdf

Shi JY (2001) Conjugacy relation on Coxeter elements. Adv Math 161:1–19MathSciNetCrossRefMATH

Stanley R (2007) Geometric combinatorics, IAS park city mathematics series. American Mathematical Society, Providence

Stanley RP (2000) Enumerative combinatorics. Cambridge University Press, CambridgeMATH

Title: Asynchronous, finite dynamical systems
Author: Henning S. Mortveit
Publication date: 25-05-2023
Publisher: Springer Netherlands
Published in: Natural Computing / Issue 2/2023
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-023-09944-3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 2/2023

Enhancing differential evolution algorithm through a population size adaptation strategy

The objective that freed me: a multi-objective local search approach for continuous single-objective optimization

What’s in a distance? Exploring the interplay between distance measures and internal cluster validity in multi-objective clustering

MOEA/D with gradient-enhanced kriging for expensive multiobjective optimization

Preface

A general framework for enhancing relaxed Pareto dominance methods in evolutionary many-objective optimization

Premium Partner