×

Tropical semimodules of dimension two. (English) Zbl 1316.15032

St. Petersbg. Math. J. 26, No. 2, 341-350 (2015) and Algebra Anal. 26, No. 2, 216-228 (2014).
Summary: The tropical arithmetic operations on \( \mathbb{R}\) are defined as \( a\oplus b=\min \{a,b\}\) and \( a\otimes b=a+b\). In the paper, the concept of a semimodule is discussed, which is rather ill-behaved in tropical mathematics. The semimodules \( S\subset \mathbb{R}^n\) having topological dimension two are studied and it is shown that any such \( S\) has a finite weak dimension not exceeding \( n\). For a fixed \( k\), a polynomial time algorithm is constructed that decides whether \( S\) is contained in some tropical semimodule of weak dimension \( k\) or not. This result provides a solution of a problem that has been open for eight years.

MSC:

15A80 Max-plus and related algebras
16D80 Other classes of modules and ideals in associative algebras
65Y20 Complexity and performance of numerical algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] [AGG] M. Akian, S. Gaubert, and A. Guterman, Linear independence over tropical semirings and beyond, Contemp. Math., vol. 495, Amer. Math. Soc., Providence, RI, 2009, pp. 1-38. · Zbl 1182.15002
[2] [BCOQ] F. Baccelli, G. Cohen, G. J. Olsder, and J. P. Quadrat, Synchronization and Linearity, An algebra for discrete event systems, John Wiley & Sons, Ltd., Chichester, 1992. · Zbl 0824.93003
[3] [Barv2] A. I. Barvinok, Two algorithmic results for the traveling salesman problem, Math. Oper. Res. 21 (1996), no. 1, 65-84. · Zbl 0846.90115
[4] [Dev1] M. Develin, The moduli space of \(n\) tropically collinear points in \(\mathbb R^d\), Collect. Math. 56 (2005), no. 1, 1-19. · Zbl 1069.52014
[5] [DS] M. Develin and B. Sturmfels, Tropical convexity, Doc. Math. 9 (2004), 1-27. (electronic) · Zbl 1054.52004
[6] [DSS] M. Develin, F. Santos, and B. Sturmfels, On the rank of a tropical matrix, Combinatorial and Computational Geometry, Math. Sci. Res. Inst. Publ., vol. 52, Cambridge Univ. Press, Cambridge, 2005, pp. 213-242. · Zbl 1095.15001
[7] [EML] M. Einsiedler, M. Kapranov, and D. Lind, Non-Archimedean amoebas and tropical varieties, J. Reine Angew. Math. 601 (2006), 139-157. · Zbl 1115.14051
[8] [FR] J. Ferrante and C. Rackoff, A decision procedure for the first order theory of real addition with order, SIAM J. Comput. 4 (1975), 69-76. · Zbl 0294.02022
[9] [Gau] S. Gaubert, Methods and applications of \((\max,+)\) linear algebra, STACS 97 (Lubek), Lecture Notes in Comput. Sci., vol. 1200, Springer, Berlin, 1997, pp. 261-282. · Zbl 1498.15034
[10] [Golan] J. S. Golan, Semirings and their applications, Kluwer Acad. Publ., Dordrecht, 1999. · Zbl 0947.16034
[11] [Mas2] G. Litvinov and V. Maslov, The correspondence principle for idempotent calculus and some computer applications, Cambridge Univ. Press, Cambridge, 1998, pp. 420-443. · Zbl 0897.68050
[12] [myTMF] Ya. Shitov, The complexity of tropical matrix factorization, Adv. in Math. 254 (2014), 138-156. · Zbl 1359.68112
[13] [Viro] O. Viro, Dequantization of real algebraic geometry on logarithmic paper, European Congress of Math., Vol. 1, Progr. Math., vol. 201, Birkh\"auser, Basel, 2001, pp. 135-146. · Zbl 1024.14026
[14] [Wag] E. Wagneur, Moduloids and pseudomodules. I, Dimension theory, Discrete Math. 98 (1991), no. 1, 57-73. · Zbl 0757.06008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.