The equation \(A \otimes x = B \otimes y\) over \((\max,+)\) (Q1870582)

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.