Remote Access St. Petersburg Mathematical Journal

St. Petersburg Mathematical Journal

ISSN 1547-7371(online) ISSN 1061-0022(print)



Tropical semimodules of dimension two

Author: Ya. Shitov
Original publication: Algebra i Analiz, tom 26 (2014), nomer 2.
Journal: St. Petersburg Math. J. 26 (2015), 341-350
MSC (2010): Primary 15A03, 15A23, 15A80
Published electronically: February 3, 2015
MathSciNet review: 3242042
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in St. Petersburg Mathematical Journal with MSC (2010): 15A03, 15A23, 15A80

Retrieve articles in all journals with MSC (2010): 15A03, 15A23, 15A80

Additional Information

Ya. Shitov
Affiliation: National Research University–Higher School of Economics, Myasnitskaya Ulitsa 20, Moscow 101000, Russia

Keywords: Tropical mathematics, linear algebra, computational complexity
Received by editor(s): June 27, 2013
Published electronically: February 3, 2015
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society