A note on the complexity of deciding bisimilarity of normed unary processes

DOI10.1016/0304-3975(94)90183-XzbMath0809.68066MaRDI QIDQ1331934

Dung T. Huynh, L. Tian

Publication date: 29 August 1994

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

zbMATH Keywords

\(\text{NC}^ 1\) reductionunary context-free processes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items

On deciding some equivalences for concurrent processes ⋮ Deciding bisimilarity of normed context-free processes is in \(\Sigma_ 2^ p\)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \(\sum ^ p_ 2\)-complete
• CCS expressions, finite state processes, and three problems of equivalence
• A short proof of the decidability of bisimulation for normed BPA- processes
• Deciding bisimilarity of normed context-free processes is in \(\Sigma_ 2^ p\)
• Undecidable equivalences for basic process algebra
• Decidability of bisimulation equivalence for process generating context-free languages
• Graphes canoniques de graphes algébriques
• A taxonomy of problems with fast parallel algorithms