A generic framework for checking semantic equivalences between pushdown automata and finite-state automata

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F18%3A00100834" target="_blank" >RIV/00216224:14330/18:00100834 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.1016/j.jcss.2017.09.004" target="_blank" >http://dx.doi.org/10.1016/j.jcss.2017.09.004</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.jcss.2017.09.004" target="_blank" >10.1016/j.jcss.2017.09.004</a>

Result language

angličtina

Original language name

A generic framework for checking semantic equivalences between pushdown automata and finite-state automata

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2018

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Journal of Computer and System Sciences

ISSN

0022-0000

e-ISSN

—

Volume of the periodical

91

Issue of the periodical within the volume

1

Country of publishing house

US - UNITED STATES

Number of pages

22

Pages from-to

82-103

UT code for WoS article

000413130200005

EID of the result in the Scopus database

2-s2.0-85029604365