On deciding some equivalences for concurrent processes
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 28 (1994) no. 1, pp. 51-71.
@article{ITA_1994__28_1_51_0,
author = {Huynh, Dung T. and Tian, Lu},
title = {On deciding some equivalences for concurrent processes},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {51--71},
publisher = {EDP-Sciences},
volume = {28},
number = {1},
year = {1994},
zbl = {1004.68521},
mrnumber = {1271126},
language = {en},
url = {http://www.numdam.org/item/ITA_1994__28_1_51_0/}
}
TY  - JOUR
AU  - Huynh, Dung T.
AU  - Tian, Lu
TI  - On deciding some equivalences for concurrent processes
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1994
DA  - 1994///
SP  - 51
EP  - 71
VL  - 28
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1994__28_1_51_0/
UR  - https://zbmath.org/?q=an%3A1004.68521
UR  - https://www.ams.org/mathscinet-getitem?mr=1271126
LA  - en
ID  - ITA_1994__28_1_51_0
ER  - 
%0 Journal Article
%A Huynh, Dung T.
%A Tian, Lu
%T On deciding some equivalences for concurrent processes
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1994
%P 51-71
%V 28
%N 1
%I EDP-Sciences
%G en
%F ITA_1994__28_1_51_0
Huynh, Dung T.; Tian, Lu. On deciding some equivalences for concurrent processes. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 28 (1994) no. 1, pp. 51-71. http://www.numdam.org/item/ITA_1994__28_1_51_0/

1. C. Alvarez, J. L. Balcázar, J. Gabarró and M. Santha, Parallel Complexity in the Design and Analysis of Concurrent Systems, Lecture Notes in Computer Science, 1991, 505, pp. 288-303. | MR

2. J. C. M. Baeten, J. A. Bergstra and J. W. Klop, Decidability of Bisimulation Equivalence for Process Generating Context-Free Languages, Lecture Notes in Computer Science, 1987, 259, pp. 94-113. | MR | Zbl

3. J. C. M. Baeten, J. A. Bergstra and J. M. Klop, Ready-Trace Semantics for Concrete Process Algebra with the Priority Operator, Computer Journal, 1987, 30, pp. 498-506. | MR | Zbl

4. S. D. Brookes, C. A. R. Hoare and A. W. Roscoe, A Theory of Communicating Sequential Processes, J. Assoc. Comput. Mach., 1984, 31, pp. 560-599. | MR | Zbl

5. B. Bloom, S. Istrail and A. R. Meyer, Bisimulation Can't Be Traced, Proc. of the 15th ACM Symp. on Principles of Programming Languages, 1988, pp. 229-239.

6. J. A. Bergstra, J. W. Klop and E. R. Olderog, Readies and Failures in the Algebra of Communicating Processes, SIAM J. on Computing, 1988, 17, pp. 1134-1177. | MR | Zbl

7. D. Caucal, Graphes Canoniques de Graphes Algébriques, Theoretical Informatics and Application, 1990, 24, pp. 339-352. | Numdam | MR | Zbl

8. S. Cho and D. T. Huynh, The Parallel Complexity of Coarset Set Partition Problems, Information Processing Letters, 1992, 42, pp. 89-94. | MR | Zbl

9. J. Engelfriet, Determinacy → (Observation Equivalence = Trace Equivalence), Theoretical Computer Science, 1985, 36, pp. 21-25. | MR | Zbl

10. E. P. Friedman, The Inclusion Problem for Simple Languages, Theoretical Computer Science, 1976, 1, pp. 297-316. | MR | Zbl

11. M. R. Gary and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979. | MR | Zbl

12. R. J. Van Glabbeek, The Linear Time - Branching Time Spectrum, Lecture Notes in Computer Science, 1990, 458, pp. 278-297.

13. J. F. Groote, A Short Proof of the Decidability of Bisimulation for Normed BPA-Processes, Technical Report CS-R9151, CWI, 1991, to appear in Information Processing Letters. | MR | Zbl

14. J. F. Groote and H. Hüttel, Undecidable Equivalences for Basic Process Algebra, Technical Report CS-R9137, CWI, 1991.

15. J. F. Groote and F. W. Vaandrager, Structured Operational Semantics and Bisimulation as a Congruence, Lecture Notes in Computer Science, 1989, 372, pp. 423-438 (to appear in Information and Computation). | Zbl

16. M. A. Harrison, Introduction to Formal Language Theory, Addison-Wesley, 1978. | MR | Zbl

17. H. Hüttel and C. Stirling, Actions Speak Louder than Words: Proving Bisimilarity for Context-Free Processes, Proc. 6th Annual Symp. on Logic in Computer Science, 1991, pp. 376-386.

18. D. T. Huynh and L. Tian, Complexity of Deciding Readiness and Failure Equivalences for Processes, Proc. of the 3rd IEEE Symp. on Parallel and Distributed Processing, 1991, pp. 738-745.

19. D. T. Huynh and L. Tian, On Deciding Trace Equivalences for Processes, Technical Report UTDCS-4-91, University of Texas at Dallas, 1991, to appear in Information Sciences. | MR | Zbl

20. D. T. Huynh and L. Tian, On Some Equivalence Relations for Probabilistic Processes, Fundamenta Informaticae, 1992, 17, pp. 211-234. | MR | Zbl

21. D. T. Huynh and L. Tian, Deciding Bisimilarity of Normed Context-Free Processes Is in ∑P2. Technical Report UTDCS-1-92, University of Texas at Dallas, 1992, to appear in Theoretical Computer Science. | Zbl

22. D. T. Huynh and L. Tian, A Note on Complexity of Deciding Bisimilarity of Normed Unary Processes, Technical Report UTDCS-2-92, University of Texas at Dallas, 1992.

23. J. E. Hopcroft and J. D. Ullman, Formal Languages and Their Relation to Automata, Addison-Wesley Publishing Co., 1969. | MR | Zbl

24. J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing Co., 1979. | MR | Zbl

25. N. Immerman, Nondeterministic Space is Closed under Complement, SIAM J. on Computing, 1988, 17, pp. 935-938. | MR | Zbl

26. K. G. Larsen and A. Skou, Bisimulation through Probabilistic Testing, Information and Computation, 1991, 94, pp. 1-28. | MR | Zbl

27. P. C. Kanellakis and S. A. Smolka, CCS Expressions, Finite State Processes and Three Problems of Equivalence, Information and Computation, 1990, 86, pp. 43-68. | MR | Zbl

28. R. Milner, Communication and Concurrency, Prentice-Hall, 1989. | Zbl

29. R. De Nicola and M. C. B. Hennessy, Testing Equivalences for Processes, Theoretical Computer Science, 1984, 34, pp.83-133. | MR | Zbl

30. E. R. Olderog and C. A. R. Hoare, Specification-Oriented Semantics for Communicating Processes, Acta Informatica, 1986, 23, pp. 9-66. | MR | Zbl

31. D. Park, Concurrency and Automata on Infinite Sequences, Lecture Notes in Computer Science, 1981, 104, pp. 168-183. | Zbl

32. I. C. C. Phillips, Refusal Testing, Theoretical Computer Science, 1987, 50, pp. 241-284. | MR | Zbl

33. R. Paige and R. E. Tarjan, Three Partition Refinement Algorithm, SIAM J. on Computing, 1987, 16, pp. 937-989. | MR | Zbl

34. W. S. Rounds and S. D. Brooks, Possible Futures, Acceptances, Refusals and Communicating Processes, Proc. 22-nd Annual Symp. on Foundations of Computer science, 1981, pp. 140-149.

35. L. J. Stockmeyer, The Polynomial Time Hierarchy, 1977, 3, pp. 1-22. | MR | Zbl

36. I. H. Sudborough, On Tape-Bounded Complexity Classes and Multi-Head Finite Automata, Comput. Syst. Sci., 1975, 10, pp.62-76. | MR | Zbl

37. R. Szelepcsényi, The Method of Forced Enumeration for Nondeterministic Automata, Acta Information, 1988, 29, pp. 279-284. | MR | Zbl