On deciding some equivalences for concurrent processes
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 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  - 
Huynh, Dung T.; Tian, Lu. On deciding some equivalences for concurrent processes. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 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 1121745

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 910305 | Zbl 0635.68014

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 920065 | Zbl 0627.68016

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 819158 | Zbl 0628.68025

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 972666 | Zbl 0677.68089

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

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

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

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

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

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 1168773 | Zbl 0779.68029

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 0752.68053

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

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 1228797 | Zbl 0783.68043

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

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 0801.68058

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 237243 | Zbl 0196.01701

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

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

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

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 1049267 | Zbl 0705.68063

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

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

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

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

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

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

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 438810 | Zbl 0353.02024

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

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