{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T06:16:16Z","timestamp":1777616176387,"version":"3.51.4"},"reference-count":40,"publisher":"Elsevier BV","issue":"3","license":[{"start":{"date-parts":[[2003,4,1]],"date-time":"2003-04-01T00:00:00Z","timestamp":1049155200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":3760,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2003,4]]},"DOI":"10.1016\/s0304-3975(02)00864-2","type":"journal-article","created":{"date-parts":[[2003,4,5]],"date-time":"2003-04-05T04:26:12Z","timestamp":1049516772000},"page":"417-469","source":"Crossref","is-referenced-by-count":10,"title":["Equational theories of tropical semirings"],"prefix":"10.1016","volume":"298","author":[{"given":"Luca","family":"Aceto","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zolt\u00e1n","family":"\u00c9sik","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anna","family":"Ing\u00f3lfsd\u00f3ttir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(02)00864-2_BIB1","doi-asserted-by":"crossref","unstructured":"L. Aceto, Z. \u00c9sik, A. Ing\u00f3lfsd\u00f3ttir, The max-plus algebra of the natural numbers has no finite equational basis, BRICS Report RS-99-33, October 1999. Available at the URL http:\/\/www.brics.dk\/RS\/99\/33\/index.html. Theoretical Computer Science, to appear.","DOI":"10.7146\/brics.v6i33.20102"},{"key":"10.1016\/S0304-3975(02)00864-2_BIB2","doi-asserted-by":"crossref","unstructured":"L. Aceto, Z. \u00c9sik, A. Ing\u00f3lfsd\u00f3ttir, On the two-variable fragment of the equational theory of the max-sum algebra of the natural numbers, in: H. Reichel, S. Tison (Eds.), Proc. 17th Internat. Symp. on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 1770, Springer, Berlin, February 2000, pp. 267\u2013278. Available at the URL http:\/\/www.brics.dk\/RS\/99\/22\/index.html.","DOI":"10.1007\/3-540-46541-3_22"},{"key":"10.1016\/S0304-3975(02)00864-2_BIB3","series-title":"Proc. FoSSaCS 2001 Foundations of Software Science and Computation Structures","first-page":"42","article-title":"Axiomatizing tropical semirings","volume":"Vol. 2030","author":"Aceto","year":"2001"},{"key":"10.1016\/S0304-3975(02)00864-2_BIB4","series-title":"Proc. Workshop on Max-plus Algebras and their Applications to Discrete-event Systems, Theoretical Computer Science, and Optimization, 27\u201329 August 2001, Prague, Czech Republic","first-page":"29","article-title":"Nonfinitely based tropical semirings","author":"Aceto","year":"2001"},{"key":"10.1016\/S0304-3975(02)00864-2_BIB5","series-title":"Synchronization and Linearity, Wiley Series in Probability and Mathematical Statistics","author":"Baccelli","year":"1992"},{"key":"10.1016\/S0304-3975(02)00864-2_BIB6","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0304-3975(94)90276-3","article-title":"A complete system of identities for one-letter rational expressions with multiplicities in the tropical semiring","volume":"134","author":"Bonnier-Rigny","year":"1994","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(02)00864-2_BIB7","first-page":"230","article-title":"On an unsettled question in the theory of discontinuous groups","volume":"33","author":"Burnside","year":"1902","journal-title":"Q. J. Pure Appl. Math."},{"key":"10.1016\/S0304-3975(02)00864-2_BIB8","doi-asserted-by":"crossref","unstructured":"S. Burris, H.P. Sankappanavar, A Course in Universal Algebra, Springer, New York, 1981. The \u201cMillennium Edition\u201d is available at the URL http:\/\/thoralf.uwaterloo.ca\/htdocs\/ualg.html.","DOI":"10.1007\/978-1-4613-8130-3_4"},{"key":"10.1016\/S0304-3975(02)00864-2_BIB9","series-title":"Mathematics Series","article-title":"Regular Algebra and Finite Machines","author":"Conway","year":"1971"},{"key":"10.1016\/S0304-3975(02)00864-2_BIB10","article-title":"Minimax Algebra","volume":"Vol. 166","author":"Cuninghame-Green","year":"1979"},{"key":"10.1016\/S0304-3975(02)00864-2_BIB11","unstructured":"M.J. Fischer, M.O. Rabin, Super-exponential complexity of Presburger arithmetic, in: Complexity of Computation, Proc. SIAM-AMS Symp. New York, 1973, Vol. VII of SIAM-AMS Proc., American Mathematical Society, Providence, RI, 1974, 27\u201341."},{"key":"10.1016\/S0304-3975(02)00864-2_BIB12","series-title":"Proc. 14th Internat. Symp. on Theoretical Aspects of Computer Science","first-page":"261","article-title":"Methods and applications of (max,+) linear algebra","volume":"Vol. 1200","author":"Gaubert","year":"1997"},{"key":"10.1016\/S0304-3975(02)00864-2_BIB13","series-title":"Universal Algebra","author":"Gr\u00e4tzer","year":"1979"},{"key":"10.1016\/S0304-3975(02)00864-2_BIB14","series-title":"Publications of the Newton Institute 11","author":"Gunawardena Idempotency","year":"1998"},{"key":"10.1016\/S0304-3975(02)00864-2_BIB15","doi-asserted-by":"crossref","unstructured":"J. Gunawardena, An Introduction to Idempotency, in [14], pp. 1\u201349.","DOI":"10.1017\/CBO9780511662508.003"},{"issue":"2","key":"10.1016\/S0304-3975(02)00864-2_BIB16","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0022-0000(82)90051-4","article-title":"Limitedness theorem on finite automata with distance functions","volume":"24","author":"Hashiguchi","year":"1982","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(02)00864-2_BIB17","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/S0019-9958(82)91028-2","article-title":"Regular languages of star height one","volume":"53","author":"Hashiguchi","year":"1982","journal-title":"Inform. Control"},{"key":"10.1016\/S0304-3975(02)00864-2_BIB18","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1016\/0890-5401(88)90033-8","article-title":"Algorithms for determining relative star height and star height","volume":"78","author":"Hashiguchi","year":"1988","journal-title":"Inform. Comput."},{"key":"10.1016\/S0304-3975(02)00864-2_BIB19","series-title":"Formal Properties of Finite Automata and Applications","first-page":"74","article-title":"Relative star-height, star-height and finite automata with distance functions","volume":"Vol. 386","author":"Hashiguchi","year":"1989"},{"key":"10.1016\/S0304-3975(02)00864-2_BIB20","series-title":"Notes on Logic and Set Theory, Cambridge Mathematical Textbooks","author":"Johnstone","year":"1987"},{"key":"10.1016\/S0304-3975(02)00864-2_BIB21","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0304-3975(91)90395-I","article-title":"Complete systems of B-rational identities","volume":"89","author":"Krob","year":"1991","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(02)00864-2_BIB22","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1142\/S0218196794000063","article-title":"The equality problem for rational series with multiplicities in the tropical semiring is undecidable","volume":"4","author":"Krob","year":"1994","journal-title":"Internat. J. Algebra Comput."},{"key":"10.1016\/S0304-3975(02)00864-2_BIB23","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0022-4049(94)90090-6","article-title":"Some consequences of a Fatou property of the tropical semiring","volume":"93","author":"Krob","year":"1994","journal-title":"J. Pure Appl. Algebra"},{"key":"10.1016\/S0304-3975(02)00864-2_BIB24","doi-asserted-by":"crossref","unstructured":"D. Krob, Some automata-theoretic aspects of min-max-plus semirings, in [14], pp. 70\u201379.","DOI":"10.1017\/CBO9780511662508.005"},{"key":"10.1016\/S0304-3975(02)00864-2_BIB25","volume":"Vol. 5","author":"Kuich","year":"1986"},{"key":"10.1016\/S0304-3975(02)00864-2_BIB26","unstructured":"H. Leung, An algebraic method for solving decision problems in finite automata theory, Ph.D. Thesis, Department of Computer Science, The Pennsylvania State University, 1987."},{"key":"10.1016\/S0304-3975(02)00864-2_BIB27","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/BF02573140","article-title":"On the topological structure of a finitely generated semigroup of matrices","volume":"37","author":"Leung","year":"1988","journal-title":"Semigroup Forum"},{"key":"10.1016\/S0304-3975(02)00864-2_BIB28","doi-asserted-by":"crossref","unstructured":"H. Leung, The topological approach to the limitedness problem on distance automata, in [14], pp. 88\u2013111.","DOI":"10.1017\/CBO9780511662508.007"},{"key":"10.1016\/S0304-3975(02)00864-2_BIB29","unstructured":"J.-P. Mascle, Quelque r\u00e9sultats de d\u00e9cidabilit\u00e9 sur la finitude des semigroupes de matrices, LITP Report 85-50, 1985."},{"key":"10.1016\/S0304-3975(02)00864-2_BIB30","series-title":"Automata, Languages and Programming, 13th Internat. Colloq.","first-page":"244","article-title":"Torsion matrix semigroups and recognizable transductions","volume":"Vol. 226","author":"Mascle","year":"1986"},{"key":"10.1016\/S0304-3975(02)00864-2_BIB31","series-title":"Mathematical Logic","author":"Monk","year":"1976"},{"key":"10.1016\/S0304-3975(02)00864-2_BIB32","doi-asserted-by":"crossref","unstructured":"J.-E. Pin, Tropical semirings, in [14], pp. 50\u201369.","DOI":"10.1017\/CBO9780511662508.004"},{"key":"10.1016\/S0304-3975(02)00864-2_BIB33","first-page":"120","article-title":"On defining relations for the algebra of regular events","volume":"16","author":"Redko","year":"1964","journal-title":"Ukrainskii Matematicheskii Zhurnal"},{"key":"10.1016\/S0304-3975(02)00864-2_BIB34","series-title":"Theory of Linear and Integer Programming","author":"Schrijver","year":"1986"},{"key":"10.1016\/S0304-3975(02)00864-2_BIB35","series-title":"Proc. 19th Ann. Symp. on Foundations of Computer Science (Ann Arbor, MI., 1978)","first-page":"143","article-title":"Limited subsets of a free monoid","author":"Simon","year":"1978"},{"key":"10.1016\/S0304-3975(02)00864-2_BIB36","series-title":"Proc. Mathematical Foundations of Computer Science (Carlsbad, 1988)","first-page":"107","article-title":"Recognizable sets with multiplicities in the tropical semiring","volume":"Vol. 324","author":"Simon","year":"1988"},{"key":"10.1016\/S0304-3975(02)00864-2_BIB37","unstructured":"I. Simon, The Nondeterministic Complexity of Finite Automata, in: Mots, M. Lothaire (Ed.), Herm\u00e8s, 1990, pp. 384\u2013400."},{"key":"10.1016\/S0304-3975(02)00864-2_BIB38","unstructured":"W. Taylor, Equational logic, in [13], Appendix 4, pp. 378\u2013400."},{"key":"10.1016\/S0304-3975(02)00864-2_BIB39","series-title":"Convexity","author":"Webster","year":"1994"},{"key":"10.1016\/S0304-3975(02)00864-2_BIB40","volume":"Vol. 10","author":"Zimmermann","year":"1981"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397502008642?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397502008642?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,17]],"date-time":"2020-03-17T19:49:07Z","timestamp":1584474547000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397502008642"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,4]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2003,4]]}},"alternative-id":["S0304397502008642"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(02)00864-2","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2003,4]]}}}