Portal de Periódicos da CAPES

On the Complexity of Bisimulation Problems for Pushdown Automata

2000; Springer Science+Business Media; Linguagem: Inglês

10.1007/3-540-44929-9_33

1611-3349

Richard Mayr,

Organoboron and organosilicon chemistry

All bisimulation problems for pushdown automata are at least PSPACE-hard. In particular, we show that (1) Weak bisimilarity of pushdown automata and finite automata is PSPACE-hard, even for a small fixed finite automaton, (2) Strong bisimilarity of pushdown automata and finite automata is PSPACE-hard, but polynomial for every fixed finite automaton, (3) Regularity (finiteness) of pushdown automata w.r.t. weak and strong bisimilarity is PSPACE-hard.