2009
Beyond Language Equivalence on Visibly Pushdown Automata
SRBA, JiříZákladní údaje
Originální název
Beyond Language Equivalence on Visibly Pushdown Automata
Název česky
Pres Jazyk ekvivalence na Viditelně Pushdown Automata
Autoři
SRBA, Jiří
Vydání
Logical Methods in Computer Science, 2009, 1860-5974
Další údaje
Jazyk
angličtina
Typ výsledku
Článek v odborném periodiku
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Nizozemské království
Utajení
není předmětem státního či obchodního tajemství
Impakt faktor
Impact factor: 1.036
Označené pro přenos do RIV
Ano
Kód RIV
RIV/00216224:14330/09:00038055
Organizační jednotka
Fakulta informatiky
UT WoS
Klíčová slova anglicky
visibly pushdown automat; equivalence checking; complexity
Změněno: 7. 1. 2010 14:14, Prof. Jiří Srba, Ph.D.
V originále
We study (bi)simulation-like preorder/equivalence checking on the class of visibly pushdown automata and its natural subclasses visibly BPA (Basic Process Algebra) and visibly one-counter automata. We describe generic methods for proving complexity upper and lower bounds for a number of studied preorders and equivalences like simulation, completed simulation, ready simulation, 2-nested simulation preorders/equivalences and bisimulation equivalence. Our main results are that all the mentioned equivalences and preorders are EXPTIME-complete on visibly pushdown automata, PSPACE-complete on visibly one-counter automata and P-complete on visibly BPA. Our PSPACE lower bound for visibly one-counter automata improves also the previously known DP-hardness results for ordinary one-counter automata and one-counter nets. Finally, we study regularity checking problems for visibly pushdown automata and show that they can be decided in polynomial time.
Česky
Studujeme (bi) simulační-jako preorder / rovnocennost kontrol na třídě viditelně zásobníkové automaty a její přirozené podtřídy viditelně BPA (Základní proces Algebra) a viditelně jedno-counter automaty. Popíšeme obecné metody pro prokázání složitost horní a dolní hranice pro počet studoval preorders a ekvivalence, jako je simulace, simulace dokončena, připravena simulace, 2-vnořené simulace preorders / ekvivalence a bisimulace ekvivalence. Naše hlavní výsledky jsou, že všechny uvedené ekvivalence, a preorders jsou EXPTIME-complete na viditelně zásobníkové automaty, PSPACE-úplné viditelně na jedno-counter automaty a P-úplné viditelně na BPA. Naše PSPACE dolní mez pro viditelně jedno-counter automaty zlepšuje také dříve známé DP-tvrdost výsledky běžné jedno-counter automaty a jedno-counter sítě. Nakonec jsme se zabývají se problémy kontrolu správnosti viditelně zásobníkové automaty a ukázat, že mohou být rozhodnuto v polynomiálním čase.
Návaznosti
| 1M0545, projekt VaV |
|