Other formats:
BibTeX
LaTeX
RIS
@article{883632, author = {Kučera, Antonín and Mayr, Richard}, article_number = {February}, keywords = {pushdown automata; verification; simulation; bisimulation}, language = {eng}, issn = {0890-5401}, journal = {Information and Computation}, title = {On the Complexity of Checking Semantic Equivalences between Pushdown Processes and Finite-state Processes}, volume = {208}, year = {2010} }
TY - JOUR ID - 883632 AU - Kučera, Antonín - Mayr, Richard PY - 2010 TI - On the Complexity of Checking Semantic Equivalences between Pushdown Processes and Finite-state Processes JF - Information and Computation VL - 208 IS - February SP - 772-796 EP - 772-796 PB - Elsevier SN - 08905401 KW - pushdown automata KW - verification KW - simulation KW - bisimulation N2 - Simulation preorder/equivalence and bisimulation equivalence are the most commonly used equivalences in concurrency theory. Their standard definitions are often called strong simulation/bisimulation, while weak simulation/bisimulation abstracts from internal tau-actions. We study the computational complexity of checking these strong and weak semantic preorders/equivalences between pushdown processes and finite-state processes. ER -
KUČERA, Antonín and Richard MAYR. On the Complexity of Checking Semantic Equivalences between Pushdown Processes and Finite-state Processes. \textit{Information and Computation}. Elsevier, 2010, vol.~208, February, p.~772-796. ISSN~0890-5401.
|