%0 Conference Proceedings
%T Tropical Two-Way Automata
%+ Laboratoire d'Informatique Gaspard-Monge (LIGM)
%+ Laboratoire Bordelais de Recherche en Informatique (LaBRI)
%A Carnino, Vincent
%A Lombardy, Sylvain
%Z Part 2: Track B: Logic, Semantics, Specification and Verification
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 8th IFIP International Conference on Theoretical Computer Science (TCS)
%C Rome, Italy
%Y Josep Diaz
%Y Ivan Lanese
%Y Davide Sangiorgi
%I Springer
%3 Theoretical Computer Science
%V LNCS-8705
%P 195-206
%8 2014-09-01
%D 2014
%R 10.1007/978-3-662-44602-7_16
%K Two-way automata
%K Weighted automata
%K Tropical semiring
%Z Computer Science [cs]/Discrete Mathematics [cs.DM]Conference papers
%X In this paper we study two-way min-plus automata. We prove that two-way distance automata are equivalent to one-way distance automata. In the second part of the paper we show that, with general min-plus semirings, it is decidable whether every accepted word has a finite weight and that, in contrast, it is undecidable whether there exists a word accepted with a finite weight.
%G English
%Z TC 1
%Z TC 2
%Z WG 2.2
%2 https://hal.science/hal-01069637/document
%2 https://hal.science/hal-01069637/file/minplus-pub.pdf
%L hal-01069637
%U https://hal.science/hal-01069637
%~ ENPC
%~ CNRS
%~ INSMI
%~ PARISTECH
%~ LIGM
%~ CV_LIGM
%~ LIGM_MOA
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ TDS-MACS
%~ IFIP-TC2
%~ IFIP-LNCS-8705
%~ IFIP-TCS
%~ IFIP-WG2-2
%~ ESIEE-PARIS
%~ UNIV-EIFFEL
%~ UPEM-UNIVEIFFEL
%~ ESIEE-UNIVEIFFEL
%~ TEST3-HALCNRS
%~ LIGM_BAAM