Weak simulations and bisimulations for max-plus automata

Abstract

Simulations and bisimulations have been recently introduced in [9] as tools for modeling state equivalence
in weighted automata, approximating language equivalence, and facilitating state reduction. The
primary goal of this paper is to present two novel types of simulations and bisimulations—weak forward
and weak backward simulations and bisimulations—which offer improved approximations of language
equivalence compared to their standard counterparts. When applied to state reduction, these new bisimulations
yield more effective simplifications. We also provide procedures for determining the existence of
weak forward and backward simulations and bisimulations, as well as methods for computing the greatest
such relations when they exist.