On the complexity of bisimulation problems for pushdown automata
| Author(s) : | Richard Mayr, |
| Publisher : | N/A |
| Publication Date : | 2000 |
| ISSN : | N/A |
| Abstract : | Abstract. 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., |