Selected Ideas Used for Decidability and Undecidability of Bisimilarity

DOI10.1007/978-3-540-85780-8_4MaRDI QIDQ3532999zbMATH OpenOpenAlexFDO

Publication date 30 October 2008

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85780-8_4

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

Recommendations

scientific article; zbMATH DE number 1361117
Completeness results for undecidable bisimilarity problems
Decidability of weak bisimilarity for a subset of BPA
Refining the undecidability border of weak bisimilarity
Undecidability of bisimilarity by defender's forcing
Deciding bisimilarity is P-complete
Undecidability of theories of Boolean algebras with selected ideals
Foundations of Software Science and Computation Structures
scientific article; zbMATH DE number 1231553
FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science

Cites work

scientific article; zbMATH DE number 42752 (Why is no real title available?)
scientific article; zbMATH DE number 2155191 (Why is no real title available?)
scientific article; zbMATH DE number 2086674 (Why is no real title available?)
scientific article; zbMATH DE number 1405656 (Why is no real title available?)
A polynomial algorithm for deciding bisimilarity of normed context-free processes
A polynomial-time algorithm for deciding bisimulation equivalence of normed Basic Parallel Processes
An elementary bisimulation decision procedure for arbitrary context-free processes
Bisimulation equivalence is decidable for all context-free processes
CCS expressions, finite state processes, and three problems of equivalence
Comparing expressibility of normed BPA and normed BPP processes
Decidability of DPDA equivalence
Decidability of bisimulation equivalence for normed pushdown processes
Decidability of bisimulation equivalence for process generating context-free languages
Deciding bisimilarity between BPA and BPP processes.
Equivalence and preorder checking for finite-state systems
Equivalence-checking on infinite-state systems: Techniques and results
Faster Algorithm for Bisimulation Equivalence of Normed Context-Free Processes
Normed BPA vs. Normed BPP Revisited
On the regular structure of prefix rewriting
Strong bisimilarity of simple process algebras: Complexity lower bounds
The Bisimulation Problem for Equational Graphs of Finite Out-Degree
Three Partition Refinement Algorithms
Undecidability of bisimilarity by defender's forcing
Verification on infinite structures.
\(L(A)=L(B)\)? A simplified decidability proof.
\(L(A)=L(B)\)? decidability results from complete formal systems

Cited in

(2)

Undecidability of bisimilarity by defender's forcing
Deciding the bisimilarity of context-free session types

This page was built for publication: Selected Ideas Used for Decidability and Undecidability of Bisimilarity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3532999)