Deciding bisimilarity of normed context-free processes is in \(\Sigma_ 2^ p\)

DOI10.1016/0304-3975(92)00078-6zbMath0801.68058OpenAlexW2004114987MaRDI QIDQ1314379

Dung T. Huynh, L. Tian

Publication date: 22 February 1994

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

Full work available at URL: https://doi.org/10.1016/0304-3975(92)00078-6

zbMATH Keywords

concurrencybisimulation equivalencedecision algorithmscontext-free processescalculus of communicating systems

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Semantics in the theory of computing (68Q55)

Related Items (9)

A note on the complexity of deciding bisimilarity of normed unary processes ⋮ A polynomial algorithm for deciding bisimilarity of normed context-free processes ⋮ Infinite results ⋮ On deciding some equivalences for concurrent processes ⋮ Deciding bisimulation and trace equivalences for systems with many identical processes ⋮ A short proof of the decidability of bisimulation for normed BPA- processes ⋮ Decidability of Weak Bisimilarity for a Subset of BPA ⋮ Pushdown automata, multiset automata, and Petri nets ⋮ A polynomial-time algorithm for deciding bisimulation equivalence of normed Basic Parallel Processes

Cites Work

• CCS expressions, finite state processes, and three problems of equivalence
• The polynomial-time hierarchy
• A note on the complexity of deciding bisimilarity of normed unary processes
• Graphes canoniques de graphes algébriques
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Deciding bisimilarity of normed context-free processes is in \(\Sigma_ 2^ p\)