Equivalence of pushdown automata via first-order grammars
作者:
Highlights:
•
摘要
A decidability proof for bisimulation equivalence of first-order grammars is given. It is an alternative proof for a result by Sénizergues (1998, 2005) that subsumes his affirmative solution of the famous decidability question for deterministic pushdown automata. The presented proof is conceptually simpler, and a particular novelty is that it is not given as two semidecision procedures but it provides an explicit algorithm that might be amenable to a complexity analysis.
论文关键词:Pushdown automata,First-order grammars,Bisimulation equivalence
论文评审过程:Received 17 December 2018, Revised 9 March 2020, Accepted 19 July 2020, Available online 29 July 2020, Version of Record 6 August 2020.
论文官网地址:https://doi.org/10.1016/j.jcss.2020.07.004