Decidability of DPDA equivalence

DOI10.1016/S0304-3975(00)00389-3zbMath0974.68056MaRDI QIDQ5941060

Colin Stirling

Publication date: 20 August 2001

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

decidability; bisimulation; DPDA; fundamental study; language equivalence

Mathematics Subject Classification ID

Related Items

Bisimilar and logically equivalent programs in PDL, A logic of separating modalities, Reducing behavioural to structural properties of programs with procedures, Model-checking hierarchical structures, Model-checking process equivalences, Constructive semantics for instantaneous reactions, On the computational complexity of bisimulation, redux, Decision problems for pushdown threads, Compositional verification of sequential programs with procedures, Deterministic finite automata with recursive calls and DPDAs, \(L(A)=L(B)\)? A simplified decidability proof., First-order \(\mu\)-calculus over generic transition systems and applications to the situation calculus, A delayed promotion policy for parity games, Some decision problems concerning semilinearity and commutation., An approach to deciding the observational equivalence of Algol-like languages, Deciding probabilistic simulation between probabilistic pushdown automata and finite-state systems, The Hennessy-Milner equivalence for continuous time stochastic logic with mu-operator, A generic framework for checking semantic equivalences between pushdown automata and finite-state automata, When not losing is better than winning: abstraction and refinement for the full \(\mu\)-calculus, Inverse monoids: decidability and complexity of algebraic questions., Bisimulation-based Non-deterministic Admissible Interference and its Application to the Analysis of Cryptographic Protocols, Model-Checking Games for Typed λ-Calculi, Modular Games for Coalgebraic Fixed Point Logics, A Propositional Dynamic Logic for CCS Programs, Selected Ideas Used for Decidability and Undecidability of Bisimilarity, A Complete Axiomatic System for a Process-Based Spatial Logic

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