On deciding trace equivalences for processes

DOI10.1016/0020-0255(93)90031-GzbMath0783.68043MaRDI QIDQ1310916

Dung T. Huynh, L. Tian

Publication date: 13 March 1994

Published in: Information Sciences (Search for Journal in Brave)

zbMATH Keywords

undecidabilitycontext-free grammarsPSPACE-completeconcurrency theoryprocessesregularity problemtrace equivalenceco-\(NP\)-completeGreibach normal form\(\prod^ p_ 2\)-complete\(NL\)-complete

Mathematics Subject Classification ID

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

Related Items (1)

On deciding some equivalences for concurrent processes

Cites Work

• 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
• Specification-oriented semantics for communicating processes
• The complementation problem for Büchi automata with applications to temporal logic
• The polynomial-time hierarchy
• Testing equivalences for processes
• A taxonomy of problems with fast parallel algorithms
• Process algebra for synchronous communication
• A Theory of Communicating Sequential Processes
• Readies and Failures in the Algebra of Communicating Processes
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On deciding trace equivalences for processes