2020/05/13 by Göller, Stefan, Parys, Paweł
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO)
paper · doi:10.48550/arxiv.2005.06285
We show that in case a pushdown system is bisimulation equivalent to a finite system, there is already a bisimulation equivalent finite system whose size is elementarily bounded in the description size of the pushdown system. As a consequence we obtain that it is elementarily decidable if a given pushdown system is bisimulation equivalent to some finite system. This improves a previously best-known ACKERMANN upper bound for this problem.