Молимо вас користите овај идентификатор за цитирање или овај линк до ове ставке: https://scidar.kg.ac.rs/handle/123456789/12373
Назив: Bisimulations for weighted automata over an additively idempotent semiring
Аутори: Damljanovic, Nada
Ciric, Miroslav
Ignjatović, Jelena
Датум издавања: 2014
Сажетак: © 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
Тип: article
DOI: 10.1016/j.tcs.2014.02.032
ISSN: 0304-3975
SCOPUS: 2-s2.0-84904135512
Налази се у колекцијама:Faculty of Technical Sciences, Čačak

Број прегледа

446

Број преузимања

11

Датотеке у овој ставци:
Датотека Опис ВеличинаФормат 
PaperMissing.pdf
  Ограничен приступ
29.86 kBAdobe PDFСличица
Погледајте


Ставке на SCIDAR-у су заштићене ауторским правима, са свим правима задржаним, осим ако није другачије назначено.