Regularity of matrices in min-algebra and its time-complexity
type: Item
instance of: scholarly article
title: Regularity of matrices in min-algebra and its time-complexity
zbMATH Open document ID: 0820.15003
DOI: 10.1016/0166-218X(94)00099-Y
published in: Discrete Applied Mathematics
publication date: 1995-04-10T00:00:00Z
review text: Let \({\mathcal G}= (G, \otimes, \leq)\) be a linearly ordered commutative group and \(\oplus\) be defined by \(a\oplus b= \min(a, b)\) for all \(a, b\in G\). An \(n\times n\) matrix \(A\) with columns \(A_ 1,\dots, A_ n\) is called regular if \[ \sum_{j\in U}^ \oplus \lambda_ j\otimes A_ j= \sum_{j\in V}^ \oplus \lambda_ j\otimes A_ j \] does not hold for any \(\lambda_ 1,\dots, \lambda_ n\in G\), \(\varnothing\neq U, V\subseteq \{1,2,\dots, n\}\), \(U\cap V= \varnothing\). The author studies the time-complexity of the problem of checking regularity of matrices. Since addition is now not a group operation, there are several non-equivalent ways of defining the regularity. He investigates three different such definitions. Two of these can be checked efficiently in \(O(n^ 3)\) operations but the third, which plays a central role in minimal-realization of the discrete event dynamic systems, is shown to be polynomially equivalent to the problem of the existence of an even cycle in a digraph.
Mathematics Subject Classification ID: 15A30
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 65Y20
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 741470
zbMATH Keywords: min-algebra
zbMATH Keywords: algorithm
zbMATH Keywords: normal matrix
zbMATH Keywords: linearly ordered commutative group
zbMATH Keywords: time-complexity
zbMATH Keywords: checking regularity of matrices
zbMATH Keywords: discrete event dynamic systems
zbMATH Keywords: even cycle
author: Peter Butkovič
reviewed by: Nikolai I. Osetinski
MaRDI profile type: Publication
cites work: Strong regularity of matrices -- a survey of results
cites work: A condition for the strong regularity of matrices in the minimax algebra
cites work: Q3964346
cites work: Discrete-event dynamic systems: The strictly convex case
cites work: Q4140383
cites work: Q4739657
cites work: Even cycles in directed graphs
cites work: The Even Cycle Problem for Directed Graphs
cites work: Q3793731
description: scientific article; zbMATH DE number 741470