Other formats:
BibTeX
LaTeX
RIS
@inproceedings{557150, author = {Kučera, Antonín and Mayr, Richard}, address = {Boston, Dordrecht, London}, booktitle = {Exploring New Frontiers of Theoretical Informatics : IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science (TCS2004)}, keywords = {Formal verification; Pushdown automata; Semantic equivalences}, language = {eng}, location = {Boston, Dordrecht, London}, isbn = {1-4020-8140-5}, pages = {395-408}, publisher = {Kluwer}, title = {A Generic Framework for Checking Semantic Equivalences between Pushdown Automata and Finite-State Automata}, year = {2004} }
TY - JOUR ID - 557150 AU - Kučera, Antonín - Mayr, Richard PY - 2004 TI - A Generic Framework for Checking Semantic Equivalences between Pushdown Automata and Finite-State Automata PB - Kluwer CY - Boston, Dordrecht, London SN - 1402081405 KW - Formal verification KW - Pushdown automata KW - Semantic equivalences N2 - We propose a generic method for deciding semantic equivalences between pushdown automata and finite-state automata. The abstract part of the method is applicable to every process equivalence which is a right PDA congruence. Practical usability of the method is demonstrated on selected equivalences which are conceptual representatives of the whole spectrum. In particular, special attention is devoted to bisimulation-like equivalences (including weak, early, delay, branching, and probabilistic bisimilarity), and it is also shown how the method applies to simulation-like and trace-like equivalences. The generality does not lead to the loss of efficiency; the algorithms obtained by applying our method are essentially time-optimal and sometimes even polynomial. The list of particular results obtained by our method includes items which are first of their kind. ER -
KUČERA, Antonín and Richard MAYR. A Generic Framework for Checking Semantic Equivalences between Pushdown Automata and Finite-State Automata. In \textit{Exploring New Frontiers of Theoretical Informatics : IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science (TCS2004)}. Boston, Dordrecht, London: Kluwer, 2004, p.~395-408. ISBN~1-4020-8140-5.
|