{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:14:20Z","timestamp":1725664460399},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540609223"},{"type":"electronic","value":"9783540497233"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-60922-9_23","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:03:54Z","timestamp":1330290234000},"page":"269-280","source":"Crossref","is-referenced-by-count":1,"title":["Trace rewriting: Computing normal forms in time O(n log n)"],"prefix":"10.1007","author":[{"given":"Michael","family":"Bertol","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Volker","family":"Diekert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"23_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, M.A., 1974."},{"key":"23_CR2","volume-title":"Lecture Notes in Computer Science","author":"M. Bertol","year":"1995","unstructured":"M. Bertol. Efficient rewriting in cograph trace monoids. In Proceedings of the Fundamentals of Computation Theory (FCT '95), Dresden (Germany) 1995, Lecture Notes in Computer Science, Berlin-Heidelberg-New York, 1995. Springer."},{"key":"23_CR3","first-page":"114","volume-title":"Lecture Notes in Computer Science","author":"M. Bertol","year":"1993","unstructured":"M. Bertol and V. Diekert. On efficient reduction-algorithms for some trace rewriting systems. In H. Common and J.-P. Jouannaud, editors, Proceedings of the Term Rewriting., number 909 in Lecture Notes in Computer Science, pages 114\u2013126, Berlin-Heidelberg-New York, 1993. Springer."},{"key":"23_CR4","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1145\/322290.322301","volume":"29","author":"R. Book","year":"1982","unstructured":"R. Book. Confluent and other types of Thue systems. J. Assoc. Comput. Mach., 29:171\u2013182, 1982.","journal-title":"J. Assoc. Comput. Mach."},{"key":"23_CR5","volume-title":"Texts and Monographs in Computer Science","author":"R.V. Book","year":"1993","unstructured":"R.V. Book and F. Otto. String Rewriting Systems. Texts and Monographs in Computer Science. Springer Verlag, New York, 1993."},{"key":"23_CR6","volume-title":"Lecture Notes in Mathematics","author":"P. Cartier","year":"1969","unstructured":"P. Cartier and D. Foata. Probl\u00e8mes combinatoires de commutation et r\u00e9arrangements. Number 85 in Lecture Notes in Mathematics. Springer, Berlin-Heidelberg-New York, 1969."},{"key":"23_CR7","volume-title":"Th\u00e8se","author":"M. Clerbout","year":"1984","unstructured":"M. Clerbout. Commutations Partielles et Familles de Langages. Th\u00e8se, Universit\u00e9 des Sciences et Technologies de Lille (France), 1984."},{"key":"23_CR8","unstructured":"M. Clerbout, M. Latteux, Y. Roos, and P. Wacrenier. A result on confluence for one-rule trace-rewriting systems. Technical Report IT-95-275, Laboratoire d'Informatique Fondamentale de Lille, Universite des Sciences et Technologies de Lille, Apr. 1995."},{"key":"23_CR9","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":"23_CR10","first-page":"42","volume-title":"Lecture Notes in Computer Science","author":"V. Diekert","year":"1987","unstructured":"V. Diekert. On the Knuth-Bendix completion for concurrent processes. In Th. Ottmann, editor, Proceedings of the 14th International Colloquium on Automata, Languages and Programming (ICALP'87), Karlsruhe (FRG) 1987, number 267 in Lecture Notes in Computer Science, pages 42\u201353, Berlin-Heidelberg-New York, 1987. Springer. Appeared also in a revised version in Theoretical Computer Science 66:117\u2013136, 1989."},{"key":"23_CR11","first-page":"168","volume-title":"Lecture Notes in Computer Science","author":"V. Diekert","year":"1989","unstructured":"V. Diekert. Word problems over traces which are solvable in linear time. In B. Monien et al., editors, Proceedings of the 6th Annual Symposium on Theoretical Aspects of Computer Science (STACS'89), Paderborn (FRG) 1989, number 349 in Lecture Notes in Computer Science, pages 168\u2013180, Berlin-Heidelberg-New York, 1989. Springer. Revised and extended version in Theoretical Computer Science 74 (1990) 3\u201318."},{"key":"23_CR12","volume-title":"Lecture Notes in Computer Science","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":"23_CR13","unstructured":"V. Diekert and G. Rozenberg, editors. The Book of Traces. World Scientific, Singapore, 1995."},{"key":"23_CR14","volume-title":"EATCS Monographs on Theoretical Computer Science 14","author":"M. Jantzen","year":"1988","unstructured":"M. Jantzen. Confluent String Rewriting. EATCS Monographs on Theoretical Computer Science 14. Springer, Berlin-Heidelberg-New York, 1988."},{"key":"23_CR15","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1145\/321765.321782","volume":"20","author":"R. Keller","year":"1973","unstructured":"R. Keller. Parallel program schemata and maximal parallelism I. Fundamental results. Journal of the Association of Computing Machinery, 20:514\u2013537, 1973.","journal-title":"Journal of the Association of Computing Machinery"},{"key":"23_CR16","volume-title":"Combinatorics on Words","author":"M. Lothaire","year":"1983","unstructured":"M. Lothaire. Combinatorics on Words. Addison-Wesley, Reading, M.A., 1983."},{"key":"23_CR17","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0001-8708(82)90048-2","volume":"46","author":"E. W. Mayr","year":"1982","unstructured":"E. W. Mayr and A. R. Meyer. The complexity of the word problems for commutative semigroups and polynomial ideals. Advances in Math., 46:305\u2013329, 1982.","journal-title":"Advances in Math."},{"key":"23_CR18","volume-title":"DAIMI Rep. PB 78","author":"A. Mazurkiewicz","year":"1977","unstructured":"A. Mazurkiewicz. Concurrent program schemes and their interpretations. DAIMI Rep. PB 78, Aarhus University, Aarhus, 1977."},{"key":"23_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":"23_CR20","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/BF01185402","volume":"28","author":"F. Otto","year":"1995","unstructured":"F. Otto. On confluence versus strong confluence for one-rule trace-rewriting systems. Mathematical Systems Theory, 28:363\u2013384, 1995.","journal-title":"Mathematical Systems Theory"},{"key":"23_CR21","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/BF01185401","volume":"28","author":"C. Wrathall","year":"1995","unstructured":"C. Wrathall and V. Diekert. On confluence of one-rule trace-rewriting systems. Mathematical Systems Theory, 28:341\u2013361, 1995.","journal-title":"Mathematical Systems Theory"}],"container-title":["Lecture Notes in Computer Science","STACS 96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60922-9_23.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:28:07Z","timestamp":1619573287000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60922-9_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540609223","9783540497233"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-60922-9_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}