Please use this identifier to cite or link to this item: https://scidar.kg.ac.rs/handle/123456789/12373
Title: Bisimulations for weighted automata over an additively idempotent semiring
Authors: Damljanovic, Nada
Ciric, Miroslav
Ignjatović, Jelena
Issue Date: 2014
Abstract: © 2014 Elsevier B.V. We show that the methodology for deciding the existence and computation of the greatest simulations and bisimulations, developed in the framework of fuzzy automata (C´iric´ et al., 2012) [13,14], 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 bisimulation equivalence matrix on a weighted automaton A is the unique (up to an isomorphism) minimal automaton in the class of all weighted automata which are forward bisimulation equivalent to A.
URI: https://scidar.kg.ac.rs/handle/123456789/12373
Type: article
DOI: 10.1016/j.tcs.2014.02.032
ISSN: 0304-3975
SCOPUS: 2-s2.0-84904135512
Appears in Collections:Faculty of Technical Sciences, Čačak

Page views(s)

105

Downloads(s)

5

Files in This Item:
File Description SizeFormat 
PaperMissing.pdf
  Restricted Access
29.86 kBAdobe PDFThumbnail
View/Open


Items in SCIDAR are protected by copyright, with all rights reserved, unless otherwise indicated.