Equivalence of pushdown automata via first-order grammars

DOI10.1016/j.jcss.2020.07.004zbMath1477.68153arXiv1812.03518OpenAlexW2906736223MaRDI QIDQ2208249

Petr Jančar

Publication date: 23 October 2020

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1812.03518

zbMATH Keywords

bisimulationpushdown automatonfirst-order grammar

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Grammars and rewriting systems (68Q42)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• \(L(A)=L(B)\)? decidability results from complete formal systems
• BPA bisimilarity is EXPTIME-hard
• Deciding semantic finiteness of pushdown processes and first-order grammars w.r.t. bisimulation equivalence
• Complexity Hierarchies beyond Elementary
• On Bisimilarity of Higher-Order Pushdown Automata: Undecidability at Order Two
• Decidability of DPDA Language Equivalence via First-Order Grammars
• Decidability of bisimulation equivalence for process generating context-free languages
• Undecidability of bisimilarity by defender's forcing
• An elementary bisimulation decision procedure for arbitrary context-free processes
• Higher-Order Model Checking: An Overview
• Bisimilarity on Basic Process Algebra is in 2-ExpTime (an explicit proof)
• Bisimulation Equivalence of First-Order Grammars
• Branching Bisimilarity Checking for PRS
• Bisimilarity of Pushdown Automata is Nonelementary
• The Bisimulation Problem for Equational Graphs of Finite Out-Degree
• Equivalences of Pushdown Systems Are Hard
• Second-Order Simple Grammars
• Decidability of DPDA equivalence

This page was built for publication: Equivalence of pushdown automata via first-order grammars