Defining the speed independence of the Boolean asynchronous systems, ITM Web Conf. 49 02008 (2022), DOI: 10.1051/itmconf/20224902008

Mathematical Subject Classification (2020): 94C11, 06E30, 94D10

Keywords and phrases : Boolean function, omega limit set, final set

A discrete time Boolean asynchronous system consists in a function Φ:{0,1}ⁿ→{0,1}ⁿ which iterates its coordinates Φ₁,...,Φ_n independently of each other. The durations of computation of Φ₁,...,Φ_n are supposed to be unknown. The analysis of such systems has as main challenge characterizing their dynamics in conditions of uncertainty. For this, a very cited classical paper is [1], where the fundamental concept of speed independence is introduced. The point is, like in most of these cases, that the engineers receive from such a work intuition, combined with a certain lack of rigor. Our aim is to try a mathematical reinforcement of the Muller's theory of the asynchronous circuits, which should be a modest homage, over time, to its authors.
A list of models used in asynchronous systems theory is given in [3]. The mathematical tools used in this analysis may be found in [2].

References
[1] David E. Muller, Scott W. Bartky, A theory of asynchronous circuits, in "Proceedings of an International Symposium on the Switching Theory," Vol. 29 of the Annals of the Computation Laboratory of Harvard University, pp. 204-243, Harvard University Press, Cambridge, Mass., 1959.
[2] Serban E. Vlad, Boolean Systems: Topics in Asynchronicity, Academic Press, 2023 (to appear).
[3] Alexandre Yakovlev, Luciano Lavagno, Alberto Sangiovanni-Vincentelli, A unified signal transition graph model for asynchronous control circuit synthesis. Form Method Syst Des 9, 139-188 (1996). https://doi.org/10.1007/BF00122081.