Beyond Language Equivalence on Visibly Pushdown Automata

Varování

Publikace nespadá pod Pedagogickou 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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.