{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:10:25Z","timestamp":1725484225595},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540438649"},{"type":"electronic","value":"9783540454656"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45465-9_64","type":"book-chapter","created":{"date-parts":[[2007,5,27]],"date-time":"2007-05-27T01:12:57Z","timestamp":1180228377000},"page":"752-763","source":"Crossref","is-referenced-by-count":2,"title":["On the Theory of One-Step Rewriting in Trace Monoids"],"prefix":"10.1007","author":[{"given":"Dietrich","family":"Kuske","sequence":"first","affiliation":[]},{"given":"Markus","family":"Lohrey","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,6,25]]},"reference":[{"key":"64_CR1","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0079468","volume-title":"Probl\u00e8mes combinatoires de commutation et r\u00e9arrangements","author":"P. Cartier","year":"1969","unstructured":"P. Cartier and D. Foata. Probl\u00e8mes combinatoires de commutation et r\u00e9arrangements. Lecture Notes in Mathematics vol. 85. Springer, Berlin-Heidelberg-New York, 1969."},{"key":"64_CR2","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0304-3975(92)90278-N","volume":"106","author":"D. Caucal","year":"1992","unstructured":"D. Caucal. On the regular structure of prefix rewriting. Theoretical Computer Science, 106:61\u201386, 1992.","journal-title":"Theoretical Computer Science"},{"key":"64_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0168-0072(90)90080-L","volume":"48","author":"K. Compton","year":"1990","unstructured":"K. Compton and C. Henson. A uniform method forproving lower bounds on the computational complexity of logical theories. Annals of Pure and Applied Logic, 48:1\u201379, 1990.","journal-title":"Annals of Pure and Applied Logic"},{"key":"64_CR4","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/BF02088013","volume":"21","author":"B. Courcelle","year":"1989","unstructured":"B. Courcelle. The monadic second-order logic of graphs, II: Infinite graphs of bounded width. Mathematical Systems Theory, 21:187\u2013221, 1989.","journal-title":"Mathematical Systems Theory"},{"key":"64_CR5","doi-asserted-by":"crossref","unstructured":"M. Dauchet and S. Tison. The theory of ground rewrite systems is decidable. In Proceedings of the 5th Annual IEEE Symposium on Logic in Computer Science (LICS\u2019 90), pages 242\u2013256. IEEE Computer Society Press, 1990.","DOI":"10.1109\/LICS.1990.113750"},{"key":"64_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1007\/3-540-18088-5_5","volume-title":"Proceedings of the14th International Colloquium on Automata, Languages and Programming (ICALP 87), Karlsruhe (Germany)","author":"V. Diekert","year":"1987","unstructured":"V. Diekert. On the Knuth-Bendix completion for concurrent processes. In Th. Ottmann, editor, Proceedings of the14th International Colloquium on Automata, Languages and Programming (ICALP 87), Karlsruhe (Germany), number 267 in Lecture Notes in Computer Science, pages 42\u201353. Springer, 1987."},{"key":"64_CR7","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, 1990."},{"issue":"1\u20132","key":"64_CR8","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/S0304-3975(98)00313-2","volume":"224","author":"V. Diekert","year":"1999","unstructured":"V. Diekert, Y. Matiyasevich, and A. Muscholl. Solving word equations modulo partial commutations. Theoretical Computer Science, 224(1\u20132):215\u2013235, 1999.","journal-title":"Theoretical Computer Science"},{"key":"64_CR9","doi-asserted-by":"crossref","unstructured":"V. Diekert and G. Rozenberg, editors. The Book of Traces. World Scientific, Singapore, 1995.","DOI":"10.1142\/2563"},{"key":"64_CR10","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/0304-3975(86)90028-9","volume":"46","author":"C. Duboc","year":"1986","unstructured":"C. Duboc. On some equations in free partially commutative monoids. Theoretical Computer Science, 46:159\u2013174, 1986.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"64_CR11","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0304-3975(93)90230-Q","volume":"108","author":"C. Frougny","year":"1993","unstructured":"C. Frougny and J. Sakarovitch. Synchronized rational relations of finite and infinite words. Theoretical Computer Science, 108(1):45\u201382, 1993.","journal-title":"Theoretical Computer Science"},{"key":"64_CR12","doi-asserted-by":"crossref","unstructured":"H. Gaifman. On local and nonlocal properties. In J. Stern, editor, Logic Colloquium\u2019 81, pages 105\u2013135, 1982, North Holland.","DOI":"10.1016\/S0049-237X(08)71879-2"},{"key":"64_CR13","unstructured":"F. Jacquemard. Automates d\u2019arbres et R\u00e9\u00e9criture de termes. PhD thesis, Universit\u00e9 de Paris-Sud, 1996."},{"key":"64_CR14","doi-asserted-by":"crossref","unstructured":"D. Kuske and M. Lohrey. On the theory of one-step rewriting in trace monoids. Technical Report 2002-01, Department of Mathematics and Computer Science, University of Leicester. Available at http:\/\/www.mcs.le.ac.uk\/~dkuske\/pub-rest.html#UNP9 .","DOI":"10.1007\/3-540-45465-9_64"},{"key":"64_CR15","unstructured":"L. Libkin. Logics capturing local properties. ACM Transactions on Computational Logic. To appear."},{"key":"64_CR16","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/978-3-540-49382-2_30","volume-title":"Proceedings of the 18th Conference on Foundations of Software Technology and Theoretical Computer Science, (FSTTCS\u201998), Chennai (India)","author":"M. Lohrey","year":"1998","unstructured":"M. Lohrey. On the confluence of trace rewriting systems. In V. Arvind and R. Ramanujam, editors, Proceedings of the 18th Conference on Foundations of Software Technology and Theoretical Computer Science, (FSTTCS\u201998), Chennai (India), number 1530 in Lecture Notes in Computer Science, pages 319\u2013330. Springer, 1998."},{"key":"64_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.2001.3055","volume":"170","author":"M. Lohrey","year":"2001","unstructured":"M. Lohrey. Confluence problems for trace rewriting systems. Information and Computation. 170:1\u201325, 2001.","journal-title":"Information and Computation"},{"key":"64_CR18","first-page":"587","volume":"55","author":"A. Markov","year":"1947","unstructured":"A. Markov. On the impossibility of certain algorithms in the theory of associative systems. Doklady Akademii Nauk SSSR, 55, 58:587\u2013590, 353\u2013356, 1947.","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"64_CR19","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1007\/3-540-63045-7_25","volume-title":"Proceedings of the 4th International Symposium on Logical Foundations of Computer Science (LFCS\u201997), Yaroslavl (Russia)","author":"Y. Matiyasevich","year":"1997","unstructured":"Y. Matiyasevich. Some decision problems for traces. In S. Adian and A. Nerode, editors, Proceedings of the 4th International Symposium on Logical Foundations of Computer Science (LFCS\u201997), Yaroslavl (Russia), number 1234 in Lecture Notes in Computer Science, pages 248\u2013257. Springer, 1997."},{"key":"64_CR20","doi-asserted-by":"crossref","unstructured":"A. Mazurkiewicz. Concurrent program schemes and their interpretation. Technical report, DAIMI Report PB-78, Aarhus University, 1977.","DOI":"10.7146\/dpb.v6i78.7691"},{"key":"64_CR21","doi-asserted-by":"crossref","unstructured":"A. Meyer. Weak monadic second order theory of one successor is not elementary recursive. In Proc. Logic Colloquium, Lecture Notes in Mathematics vol. 453, pages 132\u2013154. Springer, 1975.","DOI":"10.1007\/BFb0064872"},{"key":"64_CR22","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":"64_CR23","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1006\/inco.1999.2842","volume":"160","author":"J. Nurmonen","year":"1996","unstructured":"J. Nurmonen. Counting modulo quantifiers on finite structures. Information and Computation, 160:62\u201387, 2000. LICS 1996, Part I (New Brunswick, NJ).","journal-title":"Information and Computation"},{"issue":"1","key":"64_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/2267170","volume":"12","author":"E. Post","year":"1947","unstructured":"E. Post. Recursive unsolvability of aproblemofThue. Journal of Symbolic Logic, 12(1):1\u201311, 1947.","journal-title":"Journal of Symbolic Logic"},{"key":"64_CR25","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1006\/inco.1995.1067","volume":"118","author":"H. Straubing","year":"1995","unstructured":"H. Straubing, D. Th\u00e9rien, and W. Thomas. Regular languages defined with generalized quantifiers. Information and Computation, 118:289\u2013301, 1995.","journal-title":"Information and Computation"},{"key":"64_CR26","unstructured":"Terese. Term Rewriting Systems. To appear with Cambridge University Press, 2001."},{"key":"64_CR27","unstructured":"W. Thomas. On logical definability of trace languages. In V. Diekert, editor, Proceedings of a workshop of the ESPRIT Basic Research Action No 3166: Algebraic and Syntactic Methods in Computer Science (ASMICS), Kochel am See (Germany), Report TUM-I9002, Technical University of Munich, pages 172\u2013182, 1990."},{"key":"64_CR28","unstructured":"A. Thue. Probleme \u00fcber die Ver\u00e4nderungen von Zeichenreihen nach gegebenen Regeln. Skr. Vid. Kristiania, I Math. Natuv. Klasse, No. 10, 34 S., 1914."},{"issue":"1\u20132","key":"64_CR29","first-page":"149","volume":"208","author":"R. Treinen","year":"1998","unstructured":"R. Treinen. The first-order theory of linear one-step rewriting is undecidable. Theoretical Computer Science, 208(1\u20132): 149\u2013177, 1998.","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45465-9_64","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T11:05:54Z","timestamp":1556449554000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45465-9_64"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540438649","9783540454656"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/3-540-45465-9_64","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}