{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,7,23]],"date-time":"2022-07-23T09:12:44Z","timestamp":1658567564388},"reference-count":37,"publisher":"EDP Sciences","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"published-print":{"date-parts":[[1994]]},"DOI":"10.1051\/ita\/1994280100511","type":"journal-article","created":{"date-parts":[[2017,2,2]],"date-time":"2017-02-02T15:18:15Z","timestamp":1486048695000},"page":"51-71","source":"Crossref","is-referenced-by-count":2,"title":["On deciding some equivalences for concurrent processes"],"prefix":"10.1051","volume":"28","author":[{"given":"Dung T.","family":"Huynh","sequence":"first","affiliation":[]},{"given":"Lu","family":"Tian","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2011,1,8]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"1. ALVAREZ C., BALC\u00c1ZAR J. L., GABARR\u00d3 J. and SANTHA M., Parallel Complexity in the Design and Analysis of Concurrent Systems, Lecture Notes in Computer Science, 1991, 505, pp. 288-303.1121745","DOI":"10.1007\/978-3-662-25209-3_20"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"2. BAETEN J. C. M., BERGSTRA J. A. and KLOP J. W., Decidability of Bisimulation Equivalence for Process Generating Context-Free Languages, Lecture Notes in Computer Science, 1987, 259, pp. 94-113.9103050635.68014","DOI":"10.1007\/3-540-17945-3_5"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"3. BAETEN J. C. M., BERGSTRA J. A. and KLOP J. M., Ready-Trace Semantics for Concrete Process Algebra with the Priority Operator, Computer Journal, 1987, 30, pp. 498-506.9200650627.68016","DOI":"10.1093\/comjnl\/30.6.498"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"4. BROOKES S. D., HOARE C. A. R. and ROSCOE A. W., A Theory of Communicating Sequential Processes, J. Assoc. Comput. Mach., 1984, 31, pp. 560-599.8191580628.68025","DOI":"10.1145\/828.833"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"5. BLOOM B., ISTRAIL S. and MEYER A. R., Bisimulation Can't Be Traced, Proc. of the 15th ACM Symp. on Principles of Programming Languages, 1988, pp. 229-239.","DOI":"10.1145\/73560.73580"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"6. BERGSTRA J. A., KLOP J. W. and OLDEROG E. R., Readies and Failures in the Algebra of Communicating Processes, SIAM J. on Computing, 1988, 17, pp. 1134-1177.9726660677.68089","DOI":"10.1137\/0217073"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"7. CAUCAL D., Graphes Canoniques de Graphes Alg\u00e9briques, Theoretical Informatics and Application, 1990, 24, pp. 339-352.9236210797190701.68082","DOI":"10.1051\/ita\/1990240403391"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"8. CHO S. and HUYNH D. T., The Parallel Complexity of Coarset Set Partition Problems, Information Processing Letters, 1992, 42, pp. 89-94.11708730780.68056","DOI":"10.1016\/0020-0190(92)90095-D"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"9. ENGELFRIET J., Determinacy \u2192 (Observation Equivalence = Trace Equivalence), Theoretical Computer Science, 1985, 36, pp. 21-25.7926380571.68018","DOI":"10.1016\/0304-3975(85)90028-3"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"10. FRIEDMAN E. P., The Inclusion Problem for Simple Languages, Theoretical Computer Science, 1976, 1, pp. 297-316.4059360349.68032","DOI":"10.1016\/0304-3975(76)90074-8"},{"key":"R11","unstructured":"11. GARY M. R. and JOHNSON D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979.5190660411.68039"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"12. VAN GLABBEEK R. J., The Linear Time - Branching Time Spectrum, Lecture Notes in Computer Science, 1990, 458, pp. 278-297.","DOI":"10.1007\/BFb0039066"},{"key":"R13","unstructured":"13. GROOTE J. F., A Short Proof of the Decidability of Bisimulation for Normed BPA-Processes, Technical Report CS-R9151, CWI, 1991, to appear in Information Processing Letters.11687730779.68029"},{"key":"R14","unstructured":"14. GROOTE J. F. and H\u00dcTTEL H., Undecidable Equivalences for Basic Process Algebra, Technical Report CS-R9137, CWI, 1991.0834.68069"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"15. GROOTE J. F. and VAANDRAGER F. W., Structured Operational Semantics and Bisimulation as a Congruence, Lecture Notes in Computer Science, 1989, 372, pp. 423-438 (to appear in Information and Computation).0752.68053","DOI":"10.1007\/BFb0035774"},{"key":"R16","unstructured":"16. HARRISON M. A., Introduction to Formal Language Theory, Addison-Wesley, 1978.5263970411.68058"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"17. H\u00dcTTEL H. and STIRLING C., Actions Speak Louder than Words: Proving Bisimilarity for Context-Free Processes, Proc. 6th Annual Symp. on Logic in Computer Science, 1991, pp. 376-386.0904.68129","DOI":"10.1109\/LICS.1991.151661"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"18. HUYNH D. T. and TIAN L., Complexity of Deciding Readiness and Failure Equivalences for Processes, Proc. of the 3rd IEEE Symp. on Parallel and Distributed Processing, 1991, pp. 738-745.","DOI":"10.1109\/SPDP.1991.218189"},{"key":"R19","unstructured":"19. HUYNH D. T. and TIAN L., On Deciding Trace Equivalences for Processes, Technical Report UTDCS-4-91, University of Texas at Dallas, 1991, to appear in Information Sciences.12287970783.68043"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"20. HUYNH D. T. and TIAN L., On Some Equivalence Relations for Probabilistic Processes, Fundamenta Informaticae, 1992, 17, pp. 211-234.12085890766.68099","DOI":"10.3233\/FI-1992-17304"},{"key":"R21","unstructured":"21. HUYNH D. T. and TIAN L., Deciding Bisimilarity of Normed Context-Free Processes Is in \u2211P2. Technical Report UTDCS-1-92, University of Texas at Dallas, 1992, to appear in Theoretical Computer Science.0801.68058"},{"key":"R22","unstructured":"22. HUYNH D. T. and TIAN L., A Note on Complexity of Deciding Bisimilarity of Normed Unary Processes, Technical Report UTDCS-2-92, University of Texas at Dallas, 1992.0809.68066"},{"key":"R23","unstructured":"23. HOPCROFT J. E. and ULLMAN J. D., Formal Languages and Their Relation to Automata, Addison-Wesley Publishing Co., 1969.2372430196.01701"},{"key":"R24","unstructured":"24. HOPCROFT J. E. and ULLMAN J. D., Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing Co., 1979.6455390426.68001"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"25. IMMERMAN N., Nondeterministic Space is Closed under Complement, SIAM J. on Computing, 1988, 17, pp. 935-938.9610490668.68056","DOI":"10.1137\/0217058"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"26. LARSEN K. G. and SKOU A., Bisimulation through Probabilistic Testing, Information and Computation, 1991, 94, pp. 1-28.11231530756.68035","DOI":"10.1016\/0890-5401(91)90030-6"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"27. KANELLAKIS P. C. and SMOLKA S. A., CCS Expressions, Finite State Processes and Three Problems of Equivalence, Information and Computation, 1990, 86, pp. 43-68.10492670705.68063","DOI":"10.1016\/0890-5401(90)90025-D"},{"key":"R28","unstructured":"28. MILNER R., Communication and Concurrency, Prentice-Hall, 1989.0683.68008"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"29. DE NICOLA R. and HENNESSY M. C. B., Testing Equivalences for Processes, Theoretical Computer Science, 1984, 34, pp.83-133.7740410985.68518","DOI":"10.1016\/0304-3975(84)90113-0"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"30. OLDEROG E. R. and HOARE C. A. R., Specification-Oriented Semantics for Communicating Processes, Acta Informatica, 1986, 23, pp. 9-66.8456230569.68019","DOI":"10.1007\/BF00268075"},{"key":"R31","unstructured":"31. PARK D., Concurrency and Automata on Infinite Sequences, Lecture Notes in Computer Science, 1981, 104, pp. 168-183.0457.68049"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"32. PHILLIPS I. C. C., Refusal Testing, Theoretical Computer Science, 1987, 50, pp. 241-284.9110760626.68011","DOI":"10.1016\/0304-3975(87)90117-4"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"33. PAIGE R. and TARJAN R. E., Three Partition Refinement Algorithm, SIAM J. on Computing, 1987, 16, pp. 937-989.9170350654.68072","DOI":"10.1137\/0216062"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"34. ROUNDS W. S. and BROOKS S. D., Possible Futures, Acceptances, Refusals and Communicating Processes, Proc. 22-nd Annual Symp. on Foundations of Computer science, 1981, pp. 140-149.","DOI":"10.1109\/SFCS.1981.36"},{"key":"R35","doi-asserted-by":"crossref","unstructured":"35. STOCKMEYER L. J., The Polynomial Time Hierarchy, 1977, 3, pp. 1-22.4388100353.02024","DOI":"10.1016\/0304-3975(76)90061-X"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"36. SUDBOROUGH I. H., On Tape-Bounded Complexity Classes and Multi-Head Finite Automata, Comput. Syst. Sci., 1975, 10, pp.62-76.3638320299.68031","DOI":"10.1016\/S0022-0000(75)80014-6"},{"key":"R37","doi-asserted-by":"crossref","unstructured":"37. SZELEPCS\u00c9NYI R., The Method of Forced Enumeration for Nondeterministic Automata, Acta Information, 1988, 29, pp. 279-284.9753340638.68046","DOI":"10.1007\/BF00299636"}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/1994280100511\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,23]],"date-time":"2022-07-23T08:38:19Z","timestamp":1658565499000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/1994280100511"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"references-count":37,"journal-issue":{"issue":"1"},"alternative-id":["ita1994280100511"],"URL":"https:\/\/doi.org\/10.1051\/ita\/1994280100511","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"1290-385X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994]]}}}