Undecidability of domino games and hhp-bisimilarity.

DOI10.1016/S0890-5401(03)00064-6zbMath1054.68094OpenAlexW2029027766MaRDI QIDQ1401953

Jiří Srba, Marcin Jurdziński, Mogens Nielsen

Publication date: 19 August 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0890-5401(03)00064-6

zbMATH Keywords

1-safe Petri netshereditary history preserving bisimilarityfinite elementary net systems

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items

History-preserving bisimilarity for higher-dimensional automata via open maps ⋮ A hierarchy of reverse bisimulations on stable configuration structures ⋮ The decidability border of hereditary history preserving bisimilarity ⋮ Causality, Behavioural Equivalences, and the Security of Cyberphysical Systems ⋮ Local Model Checking in a Logic for True Concurrency ⋮ Causality versus true-concurrency ⋮ Partial-order Boolean games: informational independence in a logic-based model of strategic interaction ⋮ Event Identifier Logic ⋮ A Logic for True Concurrency ⋮ Minimisation of event structures ⋮ Non-interleaving bisimulation equivalences on basic parallel processes

Cites Work

• Petri nets and bisimulation
• CCS expressions, finite state processes, and three problems of equivalence
• A calculus of communicating systems
• On the solvability of domino snake problems
• Undecidable equivalences for basic process algebra
• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• Deciding true concurrency equivalences on safe, finite nets
• Bisimulation equivalence is decidable for all context-free processes
• Bisimulation from open maps
• Domino Games and Complexity
• Algebraic laws for nondeterminism and concurrency
• Three Partition Refinement Algorithms
• Bisimulation, modal logic and model checking games
• On the Ehrenfeucht-Fraïssé game in theoretical computer science
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item