{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:18:51Z","timestamp":1725664731211},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540602491"},{"type":"electronic","value":"9783540447702"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60249-6_71","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T12:58:10Z","timestamp":1330261090000},"page":"393-403","source":"Crossref","is-referenced-by-count":2,"title":["On the synchronization of semi-traces"],"prefix":"10.1007","author":[{"given":"Klaus","family":"Reinhardt","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,30]]},"reference":[{"key":"34_CR1","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/0020-0190(91)90224-6","volume":"38","author":"C. \u00c0lvarez","year":"1991","unstructured":"C. \u00c0lvarez and J. Gabarr\u00f3. The parallel complexity of two problems on concurrency. Information Processing Letters, 38:61\u201370, 1991.","journal-title":"Information Processing Letters"},{"key":"34_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02088289","volume":"22","author":"I. J. Aalbersberg","year":"1989","unstructured":"IJ. J. Aalbersberg and H. J. Hoogeboom. Characterizations of the decidability of some problems for regular trace languages. Mathematical Systems Theory, 22:1\u201319, 1989.","journal-title":"Mathematical Systems Theory"},{"key":"34_CR3","volume-title":"EATCS Monographs on Theoretical Computer Science","author":"J. L. Balc\u00e1zar","year":"1988","unstructured":"J. L. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity I. Number 11 in EATCS Monographs on Theoretical Computer Science. Springer, Berlin-Heidelberg-New York, 1988."},{"key":"34_CR4","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"D.M. Barrington","year":"1990","unstructured":"D.M. Barrington, N. Immerman, and H. Straubing. On uniformity within NC1. J. of Comp. and Syst. Sciences, 41:274\u2013306, 1990.","journal-title":"J. of Comp. and Syst. Sciences"},{"key":"34_CR5","volume-title":"Tech. Rep. LIFL I.T.-238","author":"M. Clerbout","year":"1992","unstructured":"M. Clerbout, D. Gonzalez, M. Latteux, E. Ochmanski, Y. Roos, and P.A. Wacrenier. Recognizable morphisms on semi commutations. Tech. Rep. LIFL I.T.-238, Universit\u00e9 des Sciences et Technologies de Lille (France), 1992."},{"key":"34_CR6","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0890-5401(87)90040-X","volume":"73","author":"M. Clerbout","year":"1987","unstructured":"M. Clerbout and M. Latteux. Semi-Commutations. Information and Computation, 73:59\u201374, 1987.","journal-title":"Information and Computation"},{"key":"34_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":"34_CR8","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0304-3975(94)90280-1","volume":"134","author":"V. Diekert","year":"1994","unstructured":"V. Diekert. A partial trace semantics for Petri nets. Theoretical Computer Science, 134:87\u2013105, 1994. Special issue of ICWLC 92, Kyoto (Japan).","journal-title":"Theoretical Computer Science"},{"key":"34_CR9","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1006\/inco.1994.1029","volume":"110","author":"V. Diekert","year":"1994","unstructured":"V. Diekert, E. Ochma\u0144ski, and K. Reinhardt. On confluent semi-commutation systems \u2014 decidability and complexity results. Information and Computation, 110:164\u2013182, 1994. A preliminary version was presented at ICALP'91, Lecture Notes in Computer Science 510 (1991).","journal-title":"Information and Computation"},{"volume-title":"The Book of Traces","year":"1995","key":"34_CR10","unstructured":"V. Diekert and G. Rozenberg, editors. The Book of Traces. World Scientific, Singapore, 1995."},{"key":"34_CR11","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/BF02088296","volume":"22","author":"V. Diekert","year":"1989","unstructured":"V. Diekert and W. Vogler. On the synchronization of traces. Mathematical Systems Theory, 22:161\u2013175, 1989. A preliminary extended abstract appeared at MFCS 88, Lecture Notes in Computer Science 324 (1988) 271\u2013279.","journal-title":"Mathematical Systems Theory"},{"key":"34_CR12","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0304-3975(89)90098-4","volume":"64","author":"D. V. Hung","year":"1989","unstructured":"D. V. Hung and E. Knuth. Semi-commutations and Petri nets. Theoretical Computer Science, 64:67\u201381, 1989.","journal-title":"Theoretical Computer Science"},{"issue":"5","key":"34_CR13","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"N. Immerman. Nondeterministic space is closed under complement. SIAM Journal on Computing, 17(5):935\u2013938, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"34_CR14","doi-asserted-by":"crossref","unstructured":"D. S. Johnson. A catalog of complexity classes. In J. van Leeuwen, editor, Algorithms and Complexity, volume A of Handbook of Theoretical Computer Science, chapter 2, pages 67\u2013161. Elsevier, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50007-2"},{"key":"34_CR15","series-title":"number 255 in Lecture Notes in Computer Science","first-page":"279","volume-title":"Petri Nets, Applications and Relationship to other Models of Concurrency","author":"A. Mazurkiewicz","year":"1987","unstructured":"A. Mazurkiewicz. Trace theory. In W. Brauer et al., editors, Petri Nets, Applications and Relationship to other Models of Concurrency, number 255 in Lecture Notes in Computer Science, pages 279\u2013324, Berlin-Heidelberg-New York, 1987. Springer."},{"key":"34_CR16","unstructured":"E. Ochma\u0144ski. Semi-Commutation and Petri Nets. In V. Diekert, editor, Proceedings of the ASMICS workshop Free Partially Commutative Monoids, Kochel am See 1989, Report TUM-I9002, Technical University of Munich, pages 151\u2013166, 1990."},{"key":"34_CR17","first-page":"412","volume-title":"Lecture Notes in Computer Science","author":"E. Ochma\u0144ski","year":"1992","unstructured":"E. Ochma\u0144ski. Modelling concurrency with semi-commutations. In I. M. Havel and V. Koubek, editors, Proceedings of the 17th Symposium on Mathematical Foundations of Computer Science (MFCS'92), Prague, (Czechoslovakia), 1992, number 629 in Lecture Notes in Computer Science, pages 412\u2013420, Berlin-Heidelberg-New York, 1992. Springer."},{"key":"34_CR18","first-page":"445","volume-title":"Lecture Notes in Computer Science","author":"E. Ochma\u0144ski","year":"1993","unstructured":"E. Ochma\u0144ski and P. A. Wacrenier. On regular compatibility of semi-commutations. In Andrzej Lingas, Rolf Karlsson, and Svante Carlsson, editors, Proceedings of the 20th International Colloquium on Automata, Languages and Programming (ICALP'93), Lund (Sweden) 1993, number 700 in Lecture Notes in Computer Science, pages 445\u2013456, Berlin-Heidelberg-New York, 1993. Springer."},{"key":"34_CR19","volume-title":"Formal Techniques in Artificial Intelligence","author":"I. Parberry","year":"1990","unstructured":"Ian Parberry. A primer on the complexity theory of neural networks. In R.B. Banerji, editor, Formal Techniques in Artificial Intelligence, Amsterdam, 1990. North-Holland."},{"key":"34_CR20","unstructured":"K. Reinhardt. Priorit\u00e4tsz\u00e4hlerautomaten und die Synchronisation von Halbspursprachen. Dissertation, Institut f\u00fcr Informatik, Universit\u00e4t Stuttgart, 1994."},{"key":"34_CR21","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"W. L. Ruzzo","year":"1981","unstructured":"W. L. Ruzzo. On uniform circuit complexity. Journal of Computer and System Sciences, 22:365\u2013383, 1981.","journal-title":"Journal of Computer and System Sciences"},{"key":"34_CR22","first-page":"406","volume-title":"Lecture Notes in Computer Science","author":"Y. Roos","year":"1991","unstructured":"Y. Roos and P. A. Wacrenier. Composition of two semi commutations. In A. Tarlecki, editor, Proceedings of the 16th Symposium on Mathematical Foundations of Computer Science (MFCS'91), Kazimierz Dolny (Poland) 1991, number 520 in Lecture Notes in Computer Science, pages 406\u2013414, Berlin-Heidelberg-New York, 1991. Springer."},{"key":"34_CR23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. J. Stockmeyer","year":"1977","unstructured":"L. J. Stockmeyer. The polynomial time hierarchy. Theoret. Comput. Sci., 3:1\u201322, 1977.","journal-title":"Theoret. Comput. Sci."},{"key":"34_CR24","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF00299636","volume":"26","author":"R. Szelepcs\u00e9nyi","year":"1988","unstructured":"R. Szelepcs\u00e9nyi. The method of forced enumeration for nondeterministic automata. Acta Informatica, 26:279\u2013284, 1988.","journal-title":"Acta Informatica"},{"key":"34_CR25","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","volume":"3","author":"C. Wrathall","year":"1977","unstructured":"C. Wrathall. Complete sets and the polynomial hierarchie. Theoret. Comput. Sci., 3:23\u201333, 1977.","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60249-6_71.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T21:34:21Z","timestamp":1619559261000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60249-6_71"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602491","9783540447702"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-60249-6_71","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}