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

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