{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:45:39Z","timestamp":1725493539202},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422877"},{"type":"electronic","value":"9783540482246"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-48224-5_49","type":"book-chapter","created":{"date-parts":[[2007,10,28]],"date-time":"2007-10-28T06:29:04Z","timestamp":1193552944000},"page":"591-602","source":"Crossref","is-referenced-by-count":1,"title":["The Star Problem in Trace Monoids: Reductions Beyond C4"],"prefix":"10.1007","author":[{"given":"Daniel","family":"Kirsten","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,7,4]]},"reference":[{"key":"49_CR1","doi-asserted-by":"crossref","unstructured":"J. Berstel. Transductions and Context-Free Languages. B.G.Teubner, Stutt., 1979.","DOI":"10.1007\/978-3-663-09367-1"},{"key":"49_CR2","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, vol. 85 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 1969."},{"key":"49_CR3","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. Inf. and Comp., 73:59\u201374, 1987.","journal-title":"Inf. and Comp."},{"key":"49_CR4","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.-Informatique Th\u00e9orique et Applications, 19:21\u201332, 1985.","journal-title":"R.A.I.R.O.-Informatique Th\u00e9orique et Applications"},{"key":"49_CR5","series-title":"Beyond Words","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1007\/978-3-642-59126-6_8","volume-title":"Handbook of Formal Languages","author":"V. Diekert","year":"1997","unstructured":"V. Diekert and Y. M\u00e9tivier. Partial commutation and traces. In G. Rozenberg and A. Salomaa, eds., Handbook of Formal Languages, Vol. 3, Beyond Words, pages 457\u2013534. Springer-Verlag, Berlin, 1997."},{"key":"49_CR6","doi-asserted-by":"crossref","unstructured":"V. Diekert and G. Rozenberg, eds., The Book of Traces. World Scient., 1995.","DOI":"10.1142\/2563"},{"key":"49_CR7","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0304-3975(86)90094-0","volume":"48","author":"C. Duboc","year":"1986","unstructured":"C. Duboc. Mixed product and asynchronous automata. Theoretical Computer Science, 48:183\u2013199, 1986.","journal-title":"Theoretical Computer Science"},{"key":"49_CR8","first-page":"197","volume":"53","author":"M. Fliess","year":"1974","unstructured":"M. Fliess. Matrices de Hankel. J. de Math. Pures et Appl., 53:197\u2013224, 1974.","journal-title":"J. de Math. Pures et Appl."},{"issue":"2","key":"49_CR9","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/0020-0190(92)90187-Z","volume":"44","author":"P. Gastin","year":"1992","unstructured":"P. Gastin, E. Ochma\u0144ski, A. Petit, and B. Rozoy. Decidability of the star problem in A\u2217 \u00d7{b}\u2217. Information Processing Letters, 44(2):65\u201371, 1992.","journal-title":"Information Processing Letters"},{"key":"49_CR10","doi-asserted-by":"crossref","first-page":"285","DOI":"10.2140\/pjm.1966.16.285","volume":"16","author":"S. Ginsburg","year":"1966","unstructured":"S. Ginsburg and E. Spanier. Semigroups, Presburger formulas, and languages. Pacific Journal of Mathematics, 16:285\u2013296, 1966.","journal-title":"Pacific Journal of Mathematics"},{"key":"49_CR11","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0304-3975(79)90057-4","volume":"8","author":"K. Hashiguchi","year":"1979","unstructured":"K. Hashiguchi. A decision procedure for the order of regular events. Theoretical Computer Science, 8:69\u201372, 1979.","journal-title":"Theoretical Computer Science"},{"key":"49_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1007\/3-540-48523-6_44","volume-title":"ICALP\u201999 Proceedings","author":"D. Kirsten","year":"1999","unstructured":"D. Kirsten. A connection between the star problem and the finite power property in trace monoids. In P. van Emde Boas et al., eds., ICALP\u201999 Proceedings, vol. 1644 of LNCS, pages 473\u2013482. Springer-Verlag, Berlin, 1999."},{"key":"49_CR13","doi-asserted-by":"crossref","unstructured":"D. Kirsten. The star problem in trace monoids: Reductions beyond C4. Technical Report MATH-AL-01-2001, Dresden University of Technology, 2001. (submitted)","DOI":"10.1007\/3-540-48224-5_49"},{"issue":"3","key":"49_CR14","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s002240011006","volume":"34","author":"D. Kirsten","year":"2001","unstructured":"D. Kirsten and G. Richomme. Decidability equivalence between the star problem and the finite power problem in trace monoids. Theory of Computing Systems, 34:3:193\u2013227, 2001.","journal-title":"Theory of Computing Systems"},{"key":"49_CR15","doi-asserted-by":"crossref","unstructured":"A. Mazurkiewicz. Concurrent program schemes and their interpretations. DAIMI Rep. PB 78, Aarhus University, 1977.","DOI":"10.7146\/dpb.v6i78.7691"},{"key":"49_CR16","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1051\/ita\/1986200201211","volume":"20","author":"Y. M\u00e9tivier","year":"1986","unstructured":"Y. M\u00e9tivier. Une condition suffisante de reconnaissabilit\u00e9 dans un mono\u00efde partiellement commutatif. R.A.I.R.O.-Inform. Th\u00e9or. et Appl., 20:121\u2013127, 1986.","journal-title":"R.A.I.R.O.-Inform. Th\u00e9or. et Appl."},{"issue":"2","key":"49_CR17","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1006\/inco.1995.1088","volume":"119","author":"Y. M\u00e9tivier","year":"1995","unstructured":"Y. M\u00e9tivier and G. Richomme. New results on the star problem in trace monoids. Information and Computation, 119(2):240\u2013251, 1995.","journal-title":"Information and Computation"},{"key":"49_CR18","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1007\/3-540-45315-6_22","volume-title":"FoSSaCS\u20192001 Proceedings","author":"R. Morin","year":"2001","unstructured":"R. Morin. On regular MSC languages and relationships to Mazurkiewicz trace theory. In F. Honsell and M. Miculan, eds., FoSSaCS\u20192001 Proceedings, vol. 2030 of LNCS, pages 332\u2013346. Springer-Verlag, Berlin, 2001."},{"key":"49_CR19","doi-asserted-by":"crossref","unstructured":"E. Ochma\u0144ski. Recognizable trace languages. Chapter 6 in [6], pages 167\u2013204.","DOI":"10.1142\/9789814261456_0006"},{"key":"49_CR20","unstructured":"E. Ochma\u0144ski. Regular Trace Languages (in Polish). PhD thesis, Warszawa, 1984."},{"key":"49_CR21","first-page":"252","volume":"40","author":"E. Ochma\u0144ski","year":"1990","unstructured":"E. Ochma\u0144ski. Notes on a star mystery. Bulletin of the EATCS, 40:252\u2013257, 1990.","journal-title":"Bulletin of the EATCS"},{"key":"49_CR22","unstructured":"G. Pighizzini. Synthesis of nondeterministic asynchronous automata. In M. Droste and Y. Gurevich, eds., Semantics of Progr. Lang. and Model Theory, number 5 in Algebra, Logic and Appl., p. 109\u2013126. Gordon and Breach Sc. Publ., 1993."},{"key":"49_CR23","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1007\/3-540-58338-6_104","volume-title":"MFCS\u201994 Proceedings","author":"G. Richomme","year":"1994","unstructured":"G. Richomme. Some trace monoids where both the star problem and the finite power property problem are decidable. In I. Privara et al., eds., MFCS\u201994 Proceedings, vol. 841 of LNCS, pages 577\u2013586. Springer-Verlag, Berlin, 1994."},{"key":"49_CR24","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1007\/BFb0023848","volume-title":"LATIN\u201992 Proc.","author":"J. Sakarovitch","year":"1992","unstructured":"J. Sakarovitch. The\u201clast\u201d decision problem for rational trace languages. In I. Simon, ed., LATIN\u201992 Proc., vol. 583 of LNCS, p. 460\u2013473. Springer-Verlag, 1992."},{"key":"49_CR25","doi-asserted-by":"crossref","unstructured":"I. Simon. Limited subsets of a free monoid. In Proceedings of the 19th IEEE Annual Symposium on Found. of Comp. Sc., pages 143\u2013150. North Carolina Press, 1978.","DOI":"10.1109\/SFCS.1978.21"}],"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-48224-5_49","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,26]],"date-time":"2021-08-26T10:39:40Z","timestamp":1629974380000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48224-5_49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422877","9783540482246"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-48224-5_49","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}