Informace o publikaci
Beyond Language Equivalence on Visibly Pushdown Automata
| Název česky | Pres Jazyk ekvivalence na Viditelně Pushdown Automata |
|---|---|
| Autoři | |
| Rok publikování | 2009 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Logical Methods in Computer Science |
| Fakulta / Pracoviště MU | |
| 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: |