Title :
Bisimilarity of Pushdown Automata is Nonelementary
Author :
Benedikt, Martin ; Goller, Stefan ; Kiefer, Stefan ; Murawski, Andrzej S.
Abstract :
Given two pushdown automata, the bisimilarity problem asks whether the infinite transition systems they induce are bisimilar. While this problem is known to be decidable our main result states that it is nonelementary, improving EXPTIME-hardness, which was the best previously known lower bound for this problem. Our lower bound result holds for normed pushdown automata as well.
Keywords :
automata theory; computational complexity; EXPTIME-hardness; bisimilarity problem; infinite transition system; pushdown automata; Games; Personal digital assistants; Poles and towers; Radiation detectors; Transducers; Turing machines; bisimilarity; pushdown automata;
Conference_Titel :
Logic in Computer Science (LICS), 2013 28th Annual IEEE/ACM Symposium on
Conference_Location :
New Orleans, LA
Print_ISBN :
978-1-4799-0413-6
DOI :
10.1109/LICS.2013.55
