KUČERA, Antonín a Richard MAYR. A generic framework for checking semantic equivalences between pushdown automata and finite-state automata. Journal of Computer and System Sciences, Academic Press, 2018, roč. 91, č. 1, s. 82-103. ISSN 0022-0000. doi:10.1016/j.jcss.2017.09.004.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název A generic framework for checking semantic equivalences between pushdown automata and finite-state automata
Autoři KUČERA, Antonín (203 Česká republika, garant, domácí) a Richard MAYR (276 Německo).
Vydání Journal of Computer and System Sciences, Academic Press, 2018, 0022-0000.
Další údaje
Originální jazyk angličtina
Typ výsledku Článek v odborném periodiku
Obor Computer sciences, information science, bioinformatics
Stát vydavatele Spojené státy americké
Utajení není předmětem státního či obchodního tajemství
Impakt faktor Impact factor: 1.129
Kód RIV RIV/00216224:14330/18:00100834
Organizační jednotka Fakulta informatiky
Doi http://dx.doi.org/10.1016/j.jcss.2017.09.004
UT WoS 000413130200005
Klíčová slova anglicky pushdown automata; equivalence-checking
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: prof. RNDr. Antonín Kučera, Ph.D., učo 2508. Změněno: 18. 7. 2018 19:35.
Anotace
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.
Anotace česky
Proces g je "plně ekvivalentní" procesu f pokud jsou iniciální stavy g a f ekvivalentní a každý stav dosažitelný z g je ekvivalentní nějakému stavu f. V článku je podána obecná metoda pro rozhodování plné ekvivalence mezi procesy zásobníkových automatů a konečně-stavovými procesy.
Návaznosti
GBP202/12/G061, projekt VaVNázev: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Akronym: CE-ITI)
Investor: Grantová agentura ČR, Projekty na podporu excelence v základním výzkumu
VytisknoutZobrazeno: 23. 10. 2019 03:04