The equation \(A \otimes x = B \otimes y\) over \((\max,+)\)
type: Item
instance of: scholarly article
title: The equation \(A \otimes x = B \otimes y\) over \((\max,+)\)
zbMATH Open document ID: 1021.65022
DOI: 10.1016/S0304-3975(02)00228-1
published in: Theoretical Computer Science
publication date: 2003-05-14T00:00:00Z
review text: This paper deals with the two-sided homogeneous system of linear equations \(A\otimes x= B\otimes y\) over \((\max,+)\) with no infinite rows or columns in \(A\) or \(B\). Such system arises from the synchronization problem. A straight-forward algorithm is presented. This algorithm converges to a solution in pseudopolynomial time from any finite initial pair whenever a solution exists. It is of interest to note that this algorithm can be used to seek finite solutions for instance of the related inhomogeneous equation \(A\otimes x\oplus a= B\otimes x\oplus b\). By the way, if the finite elements of \(A\), \(B\) are all integers, convergence is in a finite number of steps.
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 15A80
Mathematics Subject Classification ID: 15A06
zbMATH DE Number: 1909919
zbMATH Keywords: max-algebra
zbMATH Keywords: pseudopolynomial algorithm
zbMATH Keywords: two-sided homogeneous system
zbMATH Keywords: linear equations
zbMATH Keywords: convergence
author: R. A. Cuninghame-Green
author: Peter Butkovič
reviewed by: Liu Xinguo
MaRDI profile type: Publication
cites work: Q4304869
cites work: Q3337246
cites work: Minimax algebra
cites work: Q4395234
cites work: Linear and combinatorial optimization in ordered algebraic structures
description: scientific article; zbMATH DE number 1909919