Orbits in max--min algebra (Q819758)

As is well-known, max-min algebra finds application in the modelling of fuzzy systems. In this paper the author studies the ultimately periodic behaviour of the state vector sequence (orbit) in a max-min algebra. The period of this sequence (orbit period) always divides the period of the corresponding transition matrix power sequence (matrix period). The relation between the orbit and matrix periods has been studied by \textit{K. Cechlárová} [ibid. 175, 63--73 (1992; Zbl 0756.15014); ibid. 246, 97-111 (1996; Zbl 0866.15009)] and by \textit{M. Gavalec} [Discrete Appl. Math. 100, No.~1--2, 49--65 (2000; Zbl 0954.65093)]. In this paper it is shown that the period of an orbit equals the least common multiple of the periods of special scalar sequences related to the orbit and an \(O(n^3)\) algorithm for computing the period of a periodic orbit is presented. It follows readily that a periodic member of an orbit can be found in \(O(n^3\log n)\) time. The concatenation of this procedure with the above-mentioned \(O(n^3)\) procedure yields an algorithm which computes the period of an arbitrary orbit in \(O(n^3\log n)\) time. Threshold matrices and their corresponding digraphs are useful tools in this study as most propositions can be proved by considering the binary case first and then making use of the decomposition of matrices into threshold matrices. The author makes use of this method here.