Beyond Language Equivalence on Visibly Pushdown Automata

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Název česky	Pres Jazyk ekvivalence na Viditelně Pushdown Automata
Autoři	SRBA Jiří
Rok publikování	2009
Druh	Článek v odborném periodiku
Časopis / Zdroj	Logical Methods in Computer Science
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
Obor	Informatika
Klíčová slova	visibly pushdown automat; equivalence checking; complexity
Popis	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.
Související projekty:	Institut Teoretické Informatiky