On deciding some equivalences for concurrent processes

 Access to full text

 Full (PDF)

1. 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. MR1121745
2. 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. Zbl0635.68014MR910305
3. 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. Zbl0627.68016MR920065
4. 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. Zbl0628.68025MR819158
5. 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. 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. Zbl0677.68089MR972666
7. 7. D. CAUCAL, Graphes Canoniques de Graphes Algébriques, Theoretical Informatics and Application, 1990, 24, pp. 339-352. Zbl0701.68082MR1079719
8. 8. S. CHO and D. T. HUYNH, The Parallel Complexity of Coarset Set Partition Problems, Information Processing Letters, 1992, 42, pp. 89-94. Zbl0780.68056MR1170873
9. 9. J. ENGELFRIET, Determinacy → (Observation Equivalence = Trace Equivalence), Theoretical Computer Science, 1985, 36, pp. 21-25. Zbl0571.68018MR792638
10. 10. E. P. FRIEDMAN, The Inclusion Problem for Simple Languages, Theoretical Computer Science, 1976, 1, pp. 297-316. Zbl0349.68032MR405936
11. 11. M. R. GARY and D. S. JOHNSON, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979. Zbl0411.68039MR519066
12. 12. R. J. VAN GLABBEEK, The Linear Time - Branching Time Spectrum, Lecture Notes in Computer Science, 1990, 458, pp. 278-297. 
13. 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. Zbl0779.68029MR1168773
14. 14. J. F. GROOTE and H. HÜTTEL, Undecidable Equivalences for Basic Process Algebra, Technical Report CS-R9137, CWI, 1991. Zbl0834.68069
15. 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). Zbl0752.68053
16. 16. M. A. HARRISON, Introduction to Formal Language Theory, Addison-Wesley, 1978. Zbl0411.68058MR526397
17. 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. Zbl0904.68129
18. 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. 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. Zbl0783.68043MR1228797
20. 20. D. T. HUYNH and L. TIAN, On Some Equivalence Relations for Probabilistic Processes, Fundamenta Informaticae, 1992, 17, pp. 211-234. Zbl0766.68099MR1208589
21. 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. Zbl0801.68058
22. 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. Zbl0809.68066
23. 23. J. E. HOPCROFT and J. D. ULLMAN, Formal Languages and Their Relation to Automata, Addison-Wesley Publishing Co., 1969. Zbl0196.01701MR237243
24. 24. J. E. HOPCROFT and J. D. ULLMAN, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing Co., 1979. Zbl0426.68001MR645539
25. 25. N. IMMERMAN, Nondeterministic Space is Closed under Complement, SIAM J. on Computing, 1988, 17, pp. 935-938. Zbl0668.68056MR961049
26. 26. K. G. LARSEN and A. SKOU, Bisimulation through Probabilistic Testing, Information and Computation, 1991, 94, pp. 1-28. Zbl0756.68035MR1123153
27. 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. Zbl0705.68063MR1049267
28. 28. R. MILNER, Communication and Concurrency, Prentice-Hall, 1989. Zbl0683.68008
29. 29. R. DE NICOLA and M. C. B. HENNESSY, Testing Equivalences for Processes, Theoretical Computer Science, 1984, 34, pp.83-133. Zbl0985.68518MR774041
30. 30. E. R. OLDEROG and C. A. R. HOARE, Specification-Oriented Semantics for Communicating Processes, Acta Informatica, 1986, 23, pp. 9-66. Zbl0569.68019MR845623
31. 31. D. PARK, Concurrency and Automata on Infinite Sequences, Lecture Notes in Computer Science, 1981, 104, pp. 168-183. Zbl0457.68049
32. 32. I. C. C. PHILLIPS, Refusal Testing, Theoretical Computer Science, 1987, 50, pp. 241-284. Zbl0626.68011MR911076
33. 33. R. PAIGE and R. E. TARJAN, Three Partition Refinement Algorithm, SIAM J. on Computing, 1987, 16, pp. 937-989. Zbl0654.68072MR917035
34. 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. 35. L. J. STOCKMEYER, The Polynomial Time Hierarchy, 1977, 3, pp. 1-22. Zbl0353.02024MR438810
36. 36. I. H. SUDBOROUGH, On Tape-Bounded Complexity Classes and Multi-Head Finite Automata, Comput. Syst. Sci., 1975, 10, pp.62-76. Zbl0299.68031MR363832
37. 37. R. SZELEPCSÉNYI, The Method of Forced Enumeration for Nondeterministic Automata, Acta Information, 1988, 29, pp. 279-284. Zbl0638.68046MR975334