๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Computing matrix period in max-min algebra

โœ Scribed by Martin Gavalec

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
527 KB
Volume
75
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

โœฆ Synopsis

Periodicity of matrix powers in max-min algebra is studied. The period of a matrix A is shown to be the least common multiple of the periods of at most n non-trivial strongly connected components in some threshold digraphs of A. An O(n3) algorithm for computing the period is described.

๐Ÿ“œ SIMILAR VOLUMES

Orbits in maxโ€“min algebra
Orbits in maxโ€“min algebra
โœ Blanka Semanฤรญkovรก ๐Ÿ“‚ Article ๐Ÿ“… 2006 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 283 KB
On matrix powers in max-algebra
On matrix powers in max-algebra
โœ P. Butkoviฤ; R.A. Cuninghame-Green ๐Ÿ“‚ Article ๐Ÿ“… 2007 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 165 KB
Strong regularity of matrices in general
Strong regularity of matrices in general maxโ€“min algebra
โœ Martin Gavalec; Jรกn Plรกvka ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 144 KB

The problem of the strong regularity of a square matrix in a general max-min algebra is considered and a necessary and sufficient condition using the trapezoidal property is described. The results are valid without any restrictions on the underlying max-min algebra, concerning the density, or the bo

Orbits and critical components of matric
Orbits and critical components of matrices in maxโ€“min algebra
โœ Blanka Semanฤฤฑยดkovรก ๐Ÿ“‚ Article ๐Ÿ“… 2007 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 645 KB

A speed-up of a known O(n 3 ) algorithm computing the period of a periodic orbit in max-min algebra is presented. If the critical components (or the transitive closure A + ) of the transition matrix A are known, the computational complexity of the algorithm is O(n 2 ). This is achieved by using only