Bisimulations for weighted automata over an additively idempotent semiring

Autor: Miroslav Ćirić, Nada Damljanović, Jelena Ignjatović
Rok vydání: 2014
Předmět:
Zdroj: Theoretical Computer Science. 534:86-100
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2014.02.032
Popis: Weshowthatthemethodologyfordecidingtheexistenceandcomputationofthegreatestsimulationsandbisimulations, developed in the framework of fuzzy automata (M. ´ Ciric et al., Fuzzy Sets and Systems 186 (2012) 100-139, 208 (2012) 22-42), can be applied in a similar form to weighted automata over an additively idempotent semiring. We define two types of simulations and four types of bisimulations for weighted automata over an additively idempotent semiring as solutions to particular systems of matrix inequalities, and we provide polynomial-time algorithms for deciding whether there is a simulation or bisimulation of a given type between two weighted automata, and for computing the greatest one, if it exists. The algorithms are based on the concept of relative Boolean residuation for matrices over an additively idempotent semiring, that we introduce here. We also prove that two weighted automata A and B are forward bisimulation equivalent, i.e., there is a row and column complete forward bisimulation between them, if and only if the factor weighted automata with respect to the greatest forward bisimulation equivalence matrices on A and B are isomorphic. In addition, we show that the factor weighted automaton with respect to the greatest forward bisimulationequivalence matrix on aweighted automaton A is the unique (upto an isomorphism)minimal automaton in the class of all weighted automata which are forward bisimulation equivalent to A.
Databáze: OpenAIRE
Externí odkaz: