On deciding trace equivalences for processes

DOI10.1016/0020-0255(93)90031-GMaRDI QIDQ1310916zbMATH OpenFDO

Authors Dung T. Huynh, Lu Tian

Publication date 13 March 1994

Published in Information Sciences (Search for Journal in Brave)

zbMATH Keywords

context-free grammarsundecidabilityPSPACE-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)

Recommendations

• Deciding bisimulation and trace equivalences for systems with many identical processes
• Deciding bisimulation and trace equivalences for systems with many identical processes
• Revisiting trace and testing equivalences for nondeterministic and probabilistic processes
• Revisiting trace and testing equivalences for nondeterministic and probabilistic processes
• A coalgebraic approach to process equivalence and a coinduction principle for traces
• scientific article; zbMATH DE number 1051237
• A reduced semantics for deciding trace equivalence
• On the decidability of process equivalences for the \(\pi\)-calculus
• On the decidability of process equivalences for the \(\pi\)-calculus

Cites work

• scientific article; zbMATH DE number 3982543 (Why is no real title available?)
• scientific article; zbMATH DE number 4035115 (Why is no real title available?)
• scientific article; zbMATH DE number 4039251 (Why is no real title available?)
• scientific article; zbMATH DE number 42752 (Why is no real title available?)
• scientific article; zbMATH DE number 125884 (Why is no real title available?)
• scientific article; zbMATH DE number 149518 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• A Theory of Communicating Sequential Processes
• A taxonomy of problems with fast parallel algorithms
• CCS expressions, finite state processes, and three problems of equivalence
• Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \(\sum ^ p_ 2\)-complete
• Process algebra for synchronous communication
• Readies and Failures in the Algebra of Communicating Processes
• Specification-oriented semantics for communicating processes
• Testing equivalences for processes
• The complementation problem for Büchi automata with applications to temporal logic
• The polynomial-time hierarchy

Cited in

(7)

• Deciding bisimulation and trace equivalences for systems with many identical processes
• scientific article; zbMATH DE number 3903949 (Why is no real title available?)
• CCS expressions, finite state processes, and three problems of equivalence
• Undecidable equivalences for basic parallel processes
• On deciding some equivalences for concurrent processes
• Experimenting with process equivalence
• Deciding bisimulation and trace equivalences for systems with many identical processes

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1310916)