Periodicity and critical circuits in a generalized max-algebra setting

The notions introduced in Braker and Resing (1992), concerning periodicity of 2×2 matrices in a generalized setup, are extended to the case of general square matrices. The asymptotic behaviour of a series of matrices is related to a particular type of circuit, called a generalized critical circuit, which is a circuit that is critical with respect to all the nodes it contains. It is shown that the asymptotic behaviour is determined only by the lengths of some generalized critical circuits, the weights of arcs in these circuits and some critical paths. This formulation is an appealing extension of the concepts of periodicity and critical circuit in the usual max algebra. The term asymptotic may give the impression that the described behaviour is only reached after a long or even infinite transient. However, the periodic regular part may be reached in only a few steps, after which the generalized critical circuits determine the future behaviour. As a corollary we obtain that each aperiodic graph contains at least one generalized critical circuit.