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}n→{0,1}n which iterates its coordinates Φ1,...,Φn independently of each other. The durations of computation of Φ1,...,Φ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].

[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).