Equivalence of pushdown automata via first-order grammars
From MaRDI portal
Publication:2208249
DOI10.1016/j.jcss.2020.07.004zbMath1477.68153arXiv1812.03518OpenAlexW2906736223MaRDI QIDQ2208249
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
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
