{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:44:43Z","timestamp":1725493483988},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540664086"},{"type":"electronic","value":"9783540483403"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48340-3_11","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T13:04:52Z","timestamp":1184591092000},"page":"114-124","source":"Crossref","is-referenced-by-count":2,"title":["Complexity Results for Confluence Problems"],"prefix":"10.1007","author":[{"given":"Markus","family":"Lohrey","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0304-3975(82)90036-6","volume":"19","author":"R.V. Book","year":"1982","unstructured":"R.V. Book, M. Jantzen, and C. Wrathall. Monadic Thue systems. Theoretical Computer Science, 19:231\u2013251, 1982.","journal-title":"Theoretical Computer Science"},{"key":"11_CR2","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/0898-1221(81)90115-2","volume":"7","author":"A. M. Ballantyne","year":"1981","unstructured":"A. M. Ballantyne and D. S. Lankford. New decision algorithms for finitely presented commutative semigroups. Comput. and Maths. with Appls., 7:159\u2013165, 1981.","journal-title":"Comput. and Maths. with Appls."},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0890-5401(89)90051-5","volume":"82","author":"A. Bertoni","year":"1989","unstructured":"A. Bertoni, G. Mauri, and N. Sabadini. Membership problems for regular and context free trace languages. Information and Computation, 82:135\u2013150, 1989.","journal-title":"Information and Computation"},{"key":"11_CR4","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0304-3975(81)90078-5","volume":"16","author":"R.V. Book","year":"1981","unstructured":"R.V. Book and C.P. O\u2019Dunlaing. Testing for the Church-Rosser property (note). Theoretical Computer Science, 16:223\u2013229, 1981.","journal-title":"Theoretical Computer Science"},{"key":"11_CR5","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/0020-0190(85)90122-X","volume":"20","author":"R.V. Book","year":"1985","unstructured":"R.V. Book and F. Otto. Cancellation rules and extended word problems. Information Processing Letters, 20:5\u201311, 1985.","journal-title":"Information Processing Letters"},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"R.V. Book and F. Otto. String-Rewriting Systems. Springer, 1993.","DOI":"10.1007\/978-1-4613-9771-7"},{"issue":"1","key":"11_CR7","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1145\/322290.322301","volume":"29","author":"R.V. Book","year":"1982","unstructured":"R.V. Book. Confluent and other types of Thue systems. Journal of the ACM, 29(1):171\u2013182, January 1982.","journal-title":"Journal of the ACM"},{"key":"11_CR8","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1051\/ita\/1985190100211","volume":"19","author":"R. Cori","year":"1985","unstructured":"R. Cori and D. Perrin. Automates et commutations partielles. R.A.I.R.O. \u2014 Informatique Th\u00e9orique et Applications, 19:21\u201332, 1985.","journal-title":"R.A.I.R.O. \u2014 Informatique Th\u00e9orique et Applications"},{"key":"11_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-53031-2","volume-title":"Combinatorics on Traces","author":"V. Diekert","year":"1990","unstructured":"V. Diekert. Combinatorics on Traces. Number 454 in Lecture Notes in Computer Science. Springer, Berlin-Heidelberg-New York, 1990."},{"volume-title":"The Book of Traces","year":"1995","key":"11_CR10","unstructured":"V. Diekert and G. Rozenberg, editors. The Book of Traces. World Scientific, Singapore, 1995."},{"key":"11_CR11","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":"11_CR12","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0304-3975(77)90014-7","volume":"4","author":"N. D. Jones","year":"1977","unstructured":"N. D. Jones, L. H. Landweber, and Y. E. Lien. Complexity of some problems in Petri nets. Theoretical Computer Science, 4:277\u2013299, 1977.","journal-title":"Theoretical Computer Science"},{"key":"11_CR13","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R. M. Karp","year":"1972","unstructured":"R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85\u2013103. Plenum Press, New York, 1972."},{"issue":"1","key":"11_CR14","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(85)90008-8","volume":"35","author":"D. Kapur","year":"1985","unstructured":"D. Kapur, M. S. Krishnamoorthy, R. McNaughton, and P. Narendran. An O(|T|3) algorithm for testing the Church-Rosser property of Thue systems. Theoretical Computer Science, 35(1):109\u2013114, January 1985.","journal-title":"Theoretical Computer Science"},{"key":"11_CR15","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/978-3-540-49382-2_30","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"M. Lohrey","year":"1998","unstructured":"M. Lohrey. On the confluence of trace rewriting systems. In V. Arvind and R. Ramanujam, editors, Foundations of Software Technology and Theoretical Computer Science, volume 1530 of Lecture Notes in Computer Science, pages 319\u2013330. Springer, 1998."},{"key":"11_CR16","series-title":"Technical Report","volume-title":"Complexity results for confluence problems","author":"M. Lohrey","year":"1999","unstructured":"M. Lohrey. Complexity results for confluence problems. Technical Report 1999\/05, University of Stuttgart, Germany, 1999. Available via ftp.informatik.uni-stuttgart.de\/pub\/library\/ncstrl.ustuttgart_fi\/TR-1999-05\/."},{"key":"11_CR17","series-title":"DAIMI Rep.","volume-title":"Concurrent program schemes and their interpretations","author":"A. Mazurkiewicz","year":"1977","unstructured":"A. Mazurkiewicz. Concurrent program schemes and their interpretations. DAIMI Rep. PB 78, Aarhus University, Aarhus, 1977."},{"key":"11_CR18","unstructured":"M. Nivat and M. Benois. Congruences parfaites et quasi-parfaites. Seminaire Dubreil, 25(7-01\u201309), 1971\u20131972."},{"key":"11_CR19","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0020-0190(88)90049-X","volume":"29","author":"P. Narendran","year":"1988","unstructured":"P. Narendran and F. Otto. Preperfectness is undecidable for Thue systems containing only length-reducing rules and a single commutation rule. Information Processing Letters, 29:125\u2013130, 1988.","journal-title":"Information Processing Letters"},{"key":"11_CR20","first-page":"56","volume":"27","author":"E. Ochma\u0144ski","year":"1985","unstructured":"E. Ochma\u0144ski. Regular behaviour of concurrent systems. Bulletin of the European Association for Theoretical Computer Science (EATCS), 27:56\u201367, October 1985.","journal-title":"Bulletin of the European Association for Theoretical Computer Science (EATCS)"},{"key":"11_CR21","unstructured":"C.H. Papadimitriou. Computational Complexity. Addison Wesley, 1994."},{"key":"11_CR22","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1007\/BFb0052369","volume-title":"Proceedings 9th Conference on Rewriting Techniques and Applications, Tsukuba (Japan)","author":"R. M. Verma","year":"1998","unstructured":"R. M. Verma, M. Rusinowitch, and D. Lugiez. Algorithms and reductions for rewriting problems. In Proceedings 9th Conference on Rewriting Techniques and Applications, Tsukuba (Japan), volume 1379 of Lecture Notes in Computer Science, pages 166\u2013180. Springer, 1998."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1999"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48340-3_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,19]],"date-time":"2021-08-19T08:09:28Z","timestamp":1629360568000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48340-3_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540664086","9783540483403"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-48340-3_11","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}