Other formats:
BibTeX
LaTeX
RIS
@article{1409287,
author = {Kučera, Antonín and Mayr, Richard},
article_number = {1},
doi = {http://dx.doi.org/10.1016/j.jcss.2017.09.004},
keywords = {pushdown automata; equivalence-checking},
language = {eng},
issn = {0022-0000},
journal = {Journal of Computer and System Sciences},
title = {A generic framework for checking semantic equivalences between pushdown automata and finite-state automata},
url = {http://dx.doi.org/10.1016/j.jcss.2017.09.004},
volume = {91},
year = {2018}
}
TY - JOUR
ID - 1409287
AU - Kučera, Antonín - Mayr, Richard
PY - 2018
TI - A generic framework for checking semantic equivalences between pushdown automata and finite-state automata
JF - Journal of Computer and System Sciences
VL - 91
IS - 1
SP - 82-103
EP - 82-103
PB - Academic Press
SN - 00220000
KW - pushdown automata
KW - equivalence-checking
UR - http://dx.doi.org/10.1016/j.jcss.2017.09.004
N2 - For a given process equivalence, we say that a process g is fully equivalent to a process f of a transition system T if g is equivalent to f and every reachable state of g is equivalent to some state of T . We propose a generic method for deciding full equivalence between pushdown processes and finite-state processes applicable to every process equivalence satisfying certain abstract conditions. Then, we show that these conditions are satisfied by bisimulation-like equivalences (including weak and branching bisimilarity), weak simulation equivalence, and weak trace equivalence, which are the main conceptual representatives of the linear/branching time spectrum. The list of particular results obtained by applying our method includes items which are first of their kind, and the associated upper complexity bounds are essentially optimal.
ER -
KUČERA, Antonín and Richard MAYR. A generic framework for checking semantic equivalences between pushdown automata and finite-state automata. \textit{Journal of Computer and System Sciences}. Academic Press, 2018, vol.~91, No~1, p.~82-103. ISSN~0022-0000. Available from: https://dx.doi.org/10.1016/j.jcss.2017.09.004.
|
