Bisimulation relations for weighted automata

被引：72

作者：

Buchholz, Peter ^{[1
]}

机构：

[1] Univ Dortmund, D-44221 Dortmund, Germany

来源：

THEORETICAL COMPUTER SCIENCE | 2008年 / 393卷 / 1-3期

关键词：

finite automata; weighted automata; equivalence; bisimulation; congruence; aggregation;

D O I：

10.1016/j.tcs.2007.11.018

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Bisimulation is a well known equivalence relation for discrete event systems and has been extended to probabilistic and stochastic systems. This paper introduces a general definition of bisimulation which can be applied to finite automata where weights and labels are assigned to transitions. It is shown that this general view contains several known bisimulations as special cases and defines naturally equivalences for different classes of models. Apart from the well known forward bisimulation, also backward bisimulation is introduced and it is shown that both types of bisimulation preserve different types of results. Furthermore it is shown that forward and backward bisimulation are congruences according to commonly known composition operations for automata. (C) 2007 Elsevier B.V. All rights reserved.

引用

页码：109 / 123

页数：15

共 44 条

[1]

AJMONEMARSAN M, 1984, ACM T COMPUT SYST, V2, P93

[2]

AZIZ A, 1996, LNCS, V1102, P269, DOI [DOI 10.1007/3-540-61474-575, DOI 10.1007/3-540-61474-5_75]

[3]

Baccelli F, 1992, SYNCHRONIZATION LINE

[4] Model-checking algorithms for continuous-time Markov chains [J].

Baier, C ;

Haverkort, B ;

Hermanns, H ;

Katoen, JP .

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 2003, 29 (06) :524-541

[5] Deciding bisimilarity and similarity for probabilistic processes [J].

Baier, C ;

Engelen, B ;

Majster-Cederbaum, M .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2000, 60 (01) :187-231

[6]

Bloom S.L., 1993, EATCS MONOGRAPHS THE, DOI DOI 10.1007/978-3-642-78034-9

[7] Bisimulation for labelled Markov processes [J].

Blute, R ;

Desharnais, J ;

Edalat, A ;

Panangaden, P .

12TH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, PROCEEDINGS, 1997, :149-158

[8]

Buchholz P., 2003, Journal of Automata, Languages and Combinatorics, V8, P187

[9] Exact performance equivalence: An equivalence relation for stochastic automata [J].

Buchholz, P .

THEORETICAL COMPUTER SCIENCE, 1999, 215 (1-2) :263-287

[10] Efficient computation and representation of large reachability sets for composed automata [J].

Buchholz, P ;

Kemper, P .

DISCRETE EVENT DYNAMIC SYSTEMS-THEORY AND APPLICATIONS, 2002, 12 (03) :265-286

← 1 2 3 4 5 →