The equation \(A \otimes x = B \otimes y\) over \((\max,+)\) (Q1870582)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The equation \(A \otimes x = B \otimes y\) over \((\max,+)\) |
scientific article |
Statements
The equation \(A \otimes x = B \otimes y\) over \((\max,+)\) (English)
0 references
14 May 2003
0 references
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.
0 references
max-algebra
0 references
pseudopolynomial algorithm
0 references
two-sided homogeneous system
0 references
linear equations
0 references
convergence
0 references