{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:16:53Z","timestamp":1725664613598},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540614401"},{"type":"electronic","value":"9783540685807"}],"license":[{"start":{"date-parts":[[1996,1,1]],"date-time":"1996-01-01T00:00:00Z","timestamp":820454400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[1996,1,1]],"date-time":"1996-01-01T00:00:00Z","timestamp":820454400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61440-0_151","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:38:39Z","timestamp":1330292319000},"page":"466-477","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["On the complexity of relational problems for finite state processes"],"prefix":"10.1007","author":[{"given":"Sandeep K.","family":"Shukla","sequence":"first","affiliation":[]},{"suffix":"III","given":"Harry B.","family":"Hunt","sequence":"additional","affiliation":[]},{"given":"Daniel J.","family":"Rosenkrantz","sequence":"additional","affiliation":[]},{"given":"Richard E.","family":"Stearns","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"39_CR1","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0743-1066(84)90014-1","volume":"3","author":"W.F. Dowling","year":"1984","unstructured":"W.F. Dowling and J.H. Gallier. Linear time algorithm for testing the satisfiability of propositional horn formulae. Journal of Logic Programming, 3:267\u2013284, 1984.","journal-title":"Journal of Logic Programming"},{"key":"39_CR2","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, SanFrancisco, 1979."},{"key":"39_CR3","doi-asserted-by":"crossref","unstructured":"R. Greenlaw, H. J. Hoover, and W. L. Ruzzo. Limits to Parallel Computation: P-completeness Theory. Oxford University Press, 1995.","DOI":"10.1093\/oso\/9780195085914.001.0001"},{"key":"39_CR4","doi-asserted-by":"crossref","unstructured":"C. A. R. Hoare. Communicating Sequential Processes. Prentice Hall International, 1984.","DOI":"10.1007\/978-3-662-09507-2_19"},{"issue":"1","key":"39_CR5","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1051\/ita\/1994280100511","volume":"28","author":"D. T. Huynh","year":"1994","unstructured":"Dung T. Huynh and Lu Tian. On deciding some equivalences for concurrent processes. Theoretical Informatics and Applications, 28(1):51\u201371, 1994.","journal-title":"Theoretical Informatics and Applications"},{"key":"39_CR6","doi-asserted-by":"crossref","unstructured":"R. Kurshan. Computer Aided Verification of Coordinating processes: An Automata Theoretic Approach. Princeton University Press, 1994.","DOI":"10.1515\/9781400864041"},{"key":"39_CR7","doi-asserted-by":"crossref","unstructured":"Nancy Lynch and Frits Vaandrager. Forward and backward simulations-part i: Untimes systems. Information and Computation, 1995.","DOI":"10.1006\/inco.1995.1134"},{"key":"39_CR8","unstructured":"R. Milner. Communication and Concurrency. International Series in Computer Science. Prentice Hall, 1989. SU Fisher Research 511\/24."},{"key":"39_CR9","doi-asserted-by":"crossref","unstructured":"A. Rabinovich. Checking equivalences between concurrent systems of finite state agents. In ICALP, Lecture Notes in Computer Science 623, pages 696\u2013707, 1992. A more recent draft is available from the author (May 1995).","DOI":"10.1007\/3-540-55719-9_115"},{"key":"39_CR10","doi-asserted-by":"crossref","unstructured":"Thomas J. Schaefer. The complexity of satisfiability problems. In Tenth Annual Symposium on Theory of Computing, 1978.","DOI":"10.1145\/800133.804350"},{"key":"39_CR11","series-title":"Research Report","volume-title":"A uniform approach for proving polynomial time decidability simulation relations for finite state processes","author":"S. K. Shukla","year":"1995","unstructured":"S. K. Shukla, D. J. Rosenkrantz, H. B. Hunt III, S. S. Ravi, and R. E. Stearns. A uniform approach for proving polynomial time decidability simulation relations for finite state processes. Research Report TR-95-6, Department of Computer Science, SUNY Albany, 1995."},{"key":"39_CR12","unstructured":"L. J. Stockmeyer. Dexp-time hardness of bisimulation equivalence of concurrent system of finite state processes with hiding. (Unpublished Notes), 1992."},{"key":"39_CR13","volume-title":"The linear time \u2014 branching time spectrum. Technical Report CS-R9029","author":"R.J. Glabbeek van","year":"1990","unstructured":"R.J. van Glabbeek. The linear time \u2014 branching time spectrum. Technical Report CS-R9029, Computer Science Department, CWI, Centre for Mathematics and Computer Science, Netherlands, 1990."},{"key":"39_CR14","unstructured":"P. Wolper. Private communications. 1995."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61440-0_151","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T10:35:05Z","timestamp":1640946905000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61440-0_151"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540614401","9783540685807"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-61440-0_151","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]},"assertion":[{"value":"2 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}