{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T18:38:49Z","timestamp":1776191929058,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2007,10,27]],"date-time":"2007-10-27T00:00:00Z","timestamp":1193443200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2008,5]]},"DOI":"10.1007\/s00224-007-9064-z","type":"journal-article","created":{"date-parts":[[2007,10,26]],"date-time":"2007-10-26T12:07:28Z","timestamp":1193400448000},"page":"608-631","source":"Crossref","is-referenced-by-count":9,"title":["On Aperiodic and Star-Free Formal Power Series in Partially Commuting Variables"],"prefix":"10.1007","volume":"42","author":[{"given":"Manfred","family":"Droste","sequence":"first","affiliation":[]},{"given":"Paul","family":"Gastin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,10,27]]},"reference":[{"key":"9064_CR1","series-title":"EATCS Monographs in Theoretical Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-73235-5","volume-title":"Rational Series and Their Languages","author":"J. Berstel","year":"1988","unstructured":"Berstel, J., Reutenauer, C.: Rational Series and Their Languages. EATCS Monographs in Theoretical Computer Science, vol. 12. Springer, Berlin (1988)"},{"key":"9064_CR2","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1051\/ita\/1985190100211","volume":"19","author":"R. Cori","year":"1985","unstructured":"Cori, R., Perrin, D.: Automates et commutations partielles. R.A.I.R.O. Inform. Th\u00e9or. Appl. 19, 21\u201332 (1985)","journal-title":"R.A.I.R.O. Inform. Th\u00e9or. Appl."},{"key":"9064_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-53031-2","volume-title":"Combinatorics on Traces","author":"V. Diekert","year":"1990","unstructured":"Diekert, V.: Combinatorics on Traces. Lecture Notes in Computer Science, vol. 454. Springer, Berlin (1990)"},{"key":"9064_CR4","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1007\/978-3-642-59126-6_8","volume-title":"Handbook on Formal Languages","author":"V. Diekert","year":"1997","unstructured":"Diekert, V., M\u00e9tivier, Y.: Partial commutation and traces. In: Rozenberg, G., Salomaa, A. (eds.) Handbook on Formal Languages, vol. 3, pp. 457\u2013533. Springer, Berlin (1997)"},{"key":"9064_CR5","volume-title":"Book of Traces","year":"1995","unstructured":"Diekert, V., Rozenberg, G. (eds.): Book of Traces. World Scientific, Singapore (1995)"},{"key":"9064_CR6","first-page":"105","volume":"126","author":"M. Droste","year":"1996","unstructured":"Droste, M.: Aperiodic languages in concurrency monoids. Inf. Comput. 126, 105\u2013113 (1996)","journal-title":"Inf. Comput."},{"key":"9064_CR7","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1006\/inco.1999.2799","volume":"153","author":"M. Droste","year":"1999","unstructured":"Droste, M., Gastin, P.: The Kleene-Sch\u00fctzenberger theorem for formal power series in partially commuting variables. Inf. Comput. 153, 47\u201380 (1999)","journal-title":"Inf. Comput."},{"key":"9064_CR8","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1007\/978-3-662-04166-6_14","volume-title":"Proceedings of the 12th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC\u201900)","author":"M. Droste","year":"2000","unstructured":"Droste, M., Gastin, P.: On aperiodic and star-free formal power series in partially commuting variables. In: Krob, D., Mikhalev, A.A. (eds.) Proceedings of the 12th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC\u201900), pp. 158\u2013169. Springer, Berlin (2000)"},{"key":"9064_CR9","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/j.tcs.2007.02.055","volume":"380","author":"M. Droste","year":"2007","unstructured":"Droste, M., Gastin, P.: Weighted automata and weighted logics. Theor. Comput. Sci. 380, 69\u201386 (2007). Extended abstract in: Italiano, G.F. (ed.) Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP\u201905). Lecture Notes in Computer Science, vol. 3580, pp. 513\u2013525. Springer, Berlin (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9064_CR10","volume-title":"Automata, Languages and Machines","author":"S. Eilenberg","year":"1974","unstructured":"Eilenberg, S.: Automata, Languages and Machines, vol. A. Academic, New York (1974)"},{"key":"9064_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/BFb0023465","volume-title":"Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201997)","author":"S. Gaubert","year":"1997","unstructured":"Gaubert, S., Plus, M.: Methods and applications of (max\u2009,+) linear algebra. In: Reischuk, R., Morvan,\u00a0M. (eds.) Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201997). Lecture Notes in Computer Science, vol. 1200, pp. 261\u2013282. Springer, Berlin (1997)"},{"key":"9064_CR12","unstructured":"Guaiana, G.: Parties reconnaissables et morphismes sur les mono\u00efdes trace. PhD thesis, LITP, Universit\u00e9 Paris 7, France (1994)"},{"key":"9064_CR13","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/0304-3975(92)90080-Y","volume":"97","author":"G. Guaiana","year":"1992","unstructured":"Guaiana, G., Restivo, A., Salemi, S.: Star-free trace languages. Theor. Comput. Sci. 97, 301\u2013311 (1992)","journal-title":"Theor. Comput. Sci."},{"key":"9064_CR14","unstructured":"Kamp, J.A.W.: Tense logic and the theory of linear order. PhD Thesis, University of California (1968)"},{"key":"9064_CR15","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1007\/978-3-642-59136-5_9","volume-title":"Handbook on Formal Languages","author":"W. Kuich","year":"1997","unstructured":"Kuich, W.: Semirings and formal power series: their relevance to formal languages and automata. In: Rozenberg, G., Salomaa, A. (eds.) Handbook on Formal Languages, vol. 1, pp. 609\u2013677. Springer, Berlin (1997)"},{"key":"9064_CR16","series-title":"EATCS Monographs in Theoretical Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-69959-7","volume-title":"Semirings, Automata, Languages","author":"W. Kuich","year":"1986","unstructured":"Kuich, W., Salomaa, A.: Semirings, Automata, Languages. EATCS Monographs in Theoretical Computer Science, vol. 6. Springer, Berlin (1986)"},{"key":"9064_CR17","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/0304-3975(77)90001-9","volume":"5","author":"A. Mandel","year":"1977","unstructured":"Mandel, A., Simon, I.: On finite semigroups of matrices. Theor. Comput. Sci. 5, 101\u2013112 (1977)","journal-title":"Theor. Comput. Sci."},{"key":"9064_CR18","unstructured":"Mascle, J.P.: Quelques r\u00e9sultats de d\u00e9cidabilit\u00e9 sur la finitude des semigroupes de matrices. Tech. Rep. LITP 85.50, Universit\u00e9 Paris 7, France (1985)"},{"key":"9064_CR19","doi-asserted-by":"crossref","unstructured":"Mazurkiewicz, A.: Concurrent program schemes and their interpretations. Tech. rep. DAIMI PB 78, Aarhus University (1977)","DOI":"10.7146\/dpb.v6i78.7691"},{"key":"9064_CR20","series-title":"Lecture Notes in Computer Science","first-page":"279","volume-title":"Advances in Petri Nets\u201986","author":"A. Mazurkiewicz","year":"1987","unstructured":"Mazurkiewicz, A.: Trace theory. In: Brauer, W., et al. (eds.) Advances in Petri Nets\u201986. Lecture Notes in Computer Science, vol. 255, pp. 279\u2013324. Springer, Berlin (1987)"},{"key":"9064_CR21","volume-title":"Counter-Free Automata","author":"R. McNaughton","year":"1971","unstructured":"McNaughton, R., Papert, S.: Counter-Free Automata. MIT Press, Cambridge (1971)"},{"key":"9064_CR22","doi-asserted-by":"crossref","DOI":"10.1201\/9781420035643","volume-title":"Fuzzy Automata and Languages: Theory and Application","author":"J.N. Mordeson","year":"2002","unstructured":"Mordeson, J.N., Malik, D.S.: Fuzzy Automata and Languages: Theory and Application. Chapman & Hall\/CRC, New York\/Boca Raton (2002)"},{"key":"9064_CR23","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1017\/CBO9780511662508.004","volume-title":"Idempotency","author":"J.-E. Pin","year":"1998","unstructured":"Pin, J.-E.: Tropical semirings. In: Gunawardena, J. (ed.) Idempotency, pp. 50\u201369. Cambridge University Press, Cambridge (1998)"},{"key":"9064_CR24","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1016\/0021-8693(80)90097-6","volume":"66","author":"Ch. Reutenauer","year":"1980","unstructured":"Reutenauer, Ch.: S\u00e9ries formelles et alg\u00e8bres syntactiques. J. Algebra 66, 448\u2013483 (1980)","journal-title":"J. Algebra"},{"key":"9064_CR25","series-title":"Texts and Monographs in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-6264-0","volume-title":"Automata-Theoretic Aspects of Formal Power Series","author":"A. Salomaa","year":"1978","unstructured":"Salomaa, A., Soittola, M.: Automata-Theoretic Aspects of Formal Power Series. Texts and Monographs in Computer Science. Springer, Berlin (1978)"},{"key":"9064_CR26","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/S0019-9958(61)80020-X","volume":"4","author":"M.P. Sch\u00fctzenberger","year":"1961","unstructured":"Sch\u00fctzenberger, M.P.: On the definition of a family of automata. Inf. Control 4, 245\u2013270 (1961)","journal-title":"Inf. Control"},{"key":"9064_CR27","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1016\/S0019-9958(65)90108-7","volume":"8","author":"M.P. Sch\u00fctzenberger","year":"1965","unstructured":"Sch\u00fctzenberger, M.P.: On finite monoids having only trivial subgroups. Inf. Control 8, 190\u2013194 (1965)","journal-title":"Inf. Control"},{"key":"9064_CR28","doi-asserted-by":"crossref","unstructured":"Simon, I.: Limited subsets of a free monoid. In: 19th Annual Symposium on Foundation of Computer Science, pp. 143\u2013150. Institute of Electrical and Electronics Engineers (1978)","DOI":"10.1109\/SFCS.1978.21"},{"key":"9064_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1007\/BFb0017135","volume-title":"Proceeding of the International Symposium on Mathematical Foundations of Computer Science (MFCS\u201988)","author":"I. Simon","year":"1988","unstructured":"Simon, I.: Recognizable sets with multiplicities in the tropical semiring. In: Chytil, M., Janiga, L., Koubek, V. (eds.) Proceeding of the International Symposium on Mathematical Foundations of Computer Science (MFCS\u201988). Lecture Notes in Computer Science, vol. 324, pp. 107\u2013120. Springer, Berlin (1988)"},{"key":"9064_CR30","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/B978-0-12-198820-3.50020-6","volume-title":"Combinatorics on Words, Progress and Perspectives","author":"H. Straubing","year":"1983","unstructured":"Straubing, H.: The Burnside problem for semigroups of matrices. In: Cummings, L.J. (ed.) Combinatorics on Words, Progress and Perspectives, pp. 279\u2013295. Academic, San Diego (1983)"},{"key":"9064_CR31","first-page":"391","volume":"23","author":"H. Wang","year":"1997","unstructured":"Wang, H.: On characters of semirings. Houst. J. Math. 23, 391\u2013405 (1997)","journal-title":"Houst. J. Math."},{"key":"9064_CR32","series-title":"Annals of Discrete Mathematics","volume-title":"Linear and Combinatorial Optimization in Ordered Algebraic Structures","author":"U. Zimmermann","year":"1981","unstructured":"Zimmermann, U.: Linear and Combinatorial Optimization in Ordered Algebraic Structures. Annals of Discrete Mathematics, vol. 10. North-Holland, Amsterdam (1981)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9064-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-007-9064-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9064-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:51:34Z","timestamp":1558684294000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-007-9064-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,27]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,5]]}},"alternative-id":["9064"],"URL":"https:\/\/doi.org\/10.1007\/s00224-007-9064-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,27]]}}}