|
This article is cited in 2 scientific papers (total in 2 papers)
Research Papers
Tropical semimodules of dimension two
Ya. Shitov National Research University Higher School of Economics, Myasnitskaya Ulitsa, 20, 101000, Moscow, Russia
Abstract:
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.
Keywords:
tropical mathematics, linear algebra, computational complexity.
Received: 27.06.2013
Citation:
Ya. Shitov, “Tropical semimodules of dimension two”, Algebra i Analiz, 26:2 (2014), 216–228; St. Petersburg Math. J., 26:2 (2015), 341–350
Linking options:
https://www.mathnet.ru/eng/aa1382 https://www.mathnet.ru/eng/aa/v26/i2/p216
|
Statistics & downloads: |
Abstract page: | 419 | Full-text PDF : | 97 | References: | 65 | First page: | 26 |
|