# Article

Full entry | PDF   (0.2 MB)
Keywords:
systems of nonlinear equations; residuation theory; max-algebras
Summary:
The structure of solution-sets for the equation $F(x)=G(y)$ is discussed, where $F,G$ are given residuated functions mapping between partially-ordered sets. An algorithm is proposed which produces a solution in the event of finite termination: this solution is maximal relative to initial trial values of $x,y$. Properties are defined which are sufficient for finite termination. The particular case of max-based linear algebra is discussed, with application to the synchronisation problem for discrete-event systems; here, if data are rational, finite termination is assured. Numerical examples are given. For more general residuated real functions, lower semicontinuity is sufficient for convergence to a solution, if one exists.
References:
[1] Baccelli F.L., Cohen G., Olsder G.J., Quadrat J.-P.: Synchronization and Linearity, An Algebra for Discrete Event Systems. Wiley, Chichester, 1992. MR 1204266 | Zbl 0824.93003
[2] Blyth T.S., Janowitz M.: Residuation Theory. Pergamon, Oxford, 1972. MR 0396359 | Zbl 0301.06001
[3] Cuninghame-Green R.A., Butkovic P.: The Equation $A øtimes x = B øtimes y$ over $(\{ - \infty \} \cup {\Bbb R}, \max,+)$. Theoretical Computer Science, Special Issue on $(\max,+)$ Algebra, to appear. MR 1957609
[4] Cuninghame-Green R.A., Cechlarova K.: Residuation in fuzzy algebra and some applications. Fuzzy Sets and Systems 71 227-239 (1995). MR 1329610 | Zbl 0845.04007
[5] Cuninghame-Green R.A.: Minimax Algebra. Lecture Notes in Economics and Mathematical Systems No. 166, Springer-Verlag, Berlin, 1979. MR 0580321 | Zbl 0739.90073
[6] Walkup E.A., Borriello G.: A General Linear Max-Plus Solution Technique. in Idempotency (ed. J. Gunawardena), Cambridge, 1998. Zbl 0898.68035
[7] Zimmermann U.: Linear and Combinatorial Optimization in Ordered Algebraic Structures. North Holland, Amsterdam, 1981. MR 0609751 | Zbl 0466.90045

Partner of