Decidability of DPDA equivalence
From MaRDI portal
Publication:5941060
DOI10.1016/S0304-3975(00)00389-3zbMath0974.68056MaRDI QIDQ5941060
Publication date: 20 August 2001
Published in: Theoretical Computer Science (Search for Journal in Brave)
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (30)
Some decision problems concerning semilinearity and commutation. ⋮ Bisimilar and logically equivalent programs in PDL ⋮ A logic of separating modalities ⋮ An approach to deciding the observational equivalence of Algol-like languages ⋮ The Hennessy-Milner equivalence for continuous time stochastic logic with mu-operator ⋮ When not losing is better than winning: abstraction and refinement for the full \(\mu\)-calculus ⋮ Inverse monoids: decidability and complexity of algebraic questions. ⋮ A generic framework for checking semantic equivalences between pushdown automata and finite-state automata ⋮ Reducing behavioural to structural properties of programs with procedures ⋮ Decision problems for pushdown threads ⋮ Generalized abstraction-refinement for game-based CTL lifted model checking ⋮ Model-checking hierarchical structures ⋮ A Propositional Dynamic Logic for CCS Programs ⋮ Constructive semantics for instantaneous reactions ⋮ First-order \(\mu\)-calculus over generic transition systems and applications to the situation calculus ⋮ Equivalence of pushdown automata via first-order grammars ⋮ Selected Ideas Used for Decidability and Undecidability of Bisimilarity ⋮ Model-checking process equivalences ⋮ Compositional verification of sequential programs with procedures ⋮ Nested session types ⋮ Deciding the Bisimilarity of Context-Free Session Types ⋮ On the computational complexity of bisimulation, redux ⋮ Deciding probabilistic simulation between probabilistic pushdown automata and finite-state systems ⋮ A Complete Axiomatic System for a Process-Based Spatial Logic ⋮ A delayed promotion policy for parity games ⋮ Deterministic finite automata with recursive calls and DPDAs ⋮ Bisimulation-based Non-deterministic Admissible Interference and its Application to the Analysis of Cryptographic Protocols ⋮ Model-Checking Games for Typed λ-Calculi ⋮ \(L(A)=L(B)\)? A simplified decidability proof. ⋮ Modular Games for Coalgebraic Fixed Point Logics
Cites Work
- Unnamed Item
- Unnamed Item
- On equivalence of grammars through transformation trees
- Decidability of bisimulation equivalence for normed pushdown processes
- \(L(A)=L(B)\)? decidability results from complete formal systems
- Bisimulation equivalence is decidable for all context-free processes
- Strict deterministic grammars
- The equivalence problem for real-time strict deterministic languages
- The equivalence problem for deterministic pushdown automata is decidable
- Deterministic context free languages
This page was built for publication: Decidability of DPDA equivalence
