(Max,+)-automata with partial observations

摘要

(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.