loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
39th Annual Symposium on Foundations of Computer Science
Decidability of Bisimulation Equivalence for Equational Graphs of Finite Out-Degree
Palo Alto, California
November 08-November 11
ISBN: 0-8186-9172-7
ASCII Text
x 
 
Géraud Sénizergues, "Decidability of Bisimulation Equivalence for Equational Graphs of Finite Out-Degree," Foundations of Computer Science, IEEE Annual Symposium on, pp. 120, 39th Annual Symposium on Foundations of Computer Science, 1998.
 
 
BibTex
x
 
@article{ 10.1109/SFCS.1998.743435,
author = {Géraud Sénizergues},
title = {Decidability of Bisimulation Equivalence for Equational Graphs of Finite Out-Degree},
journal ={Foundations of Computer Science, IEEE Annual Symposium on},
volume = {0},
year = {1998},
issn = {0272-5428},
pages = {120},
doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.1998.743435},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, IEEE Annual Symposium on
TI - Decidability of Bisimulation Equivalence for Equational Graphs of Finite Out-Degree
SN - 0272-5428
SP
EP
A1 - Géraud Sénizergues,
PY - 1998
KW - bisimulation; equational graphs; deterministic pushdown automata; rational languages; matrix semi-groups; decidability; complete formal systems.
VL - 0
JA - Foundations of Computer Science, IEEE Annual Symposium on
ER -
 
Géraud Sénizergues, LaBRI,Universit? de Bordeaux
The bisimulation problem for equational graphs of finite out-degree is shown to be decidable. We reduce this problem to the eta-bisimulation problem for deterministic rational (vectors of) boolean series on the alphabet of a dpda M. We then exhibit a complete formal system for deducing equivalent pairs of such vectors.
Index Terms:
bisimulation; equational graphs; deterministic pushdown automata; rational languages; matrix semi-groups; decidability; complete formal systems.
Citation:
Géraud Sénizergues, "Decidability of Bisimulation Equivalence for Equational Graphs of Finite Out-Degree," focs, pp.120, 39th Annual Symposium on Foundations of Computer Science, 1998
Usage of this product signifies your acceptance of the Terms of Use.