Decidability, undecidability, and PSPACE-completeness of the twins property in the tropical semiring

摘要

We solve a problem already investigated by Mohri in 1997: we show that the twins property for weighted finite automata over the tropical semiring is decidable and PSPACE-complete. We also point out that it is undecidable whether two given states are twins.