(Max, +)-automata with partial observations. Issue 7 (2018)

• Record Type: Journal Article
• Authors: Komenda, J.; Lahaye, S.; Boimond, J.L.
• Is Part Of: IFAC-PapersOnLine. Volume 51:Issue 7(2018)
• Page Start: 192
• Page End: 197
• Publication Date: 2018
• Subjects: (Max, +)-automata -- partial observations -- weak bisimulation -- residuation theory; Automatic control -- Periodicals; 629.805
• DOI: 10.1016/j.ifacol.2018.06.300
• Languages: English
• ISSNs: 2405-8963

Abstract

Abstract: (Max, +)-automata are weighted automata over the (max, +) semiring. In this paper we investigate simulation like equivalences between (max, +)-automata. Since (max, +)-automata are nondetermin-istic (weighted) automata, there exist extensions of bisimilarity properties that are weaker than equality of their weighted languages (formal power series). The main advantage of bisimulation like properties is that they can be checked in polynomial time, while equality (as well as inequality) of formal power series is undecidable. We show that a form of weak simulation can be used as a sufficient condition for comparing the formal power series.