{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T06:40:22Z","timestamp":1725691222730},"reference-count":36,"publisher":"EDP Sciences","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"published-print":{"date-parts":[[2008,7]]},"DOI":"10.1051\/ita:2008017","type":"journal-article","created":{"date-parts":[[2008,6,2]],"date-time":"2008-06-02T11:45:58Z","timestamp":1212407158000},"page":"553-581","source":"Crossref","is-referenced-by-count":19,"title":["A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata"],"prefix":"10.1051","volume":"42","author":[{"given":"Daniel","family":"Kirsten","sequence":"first","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2008,6,3]]},"reference":[{"key":"R1","unstructured":"C. Allauzen and M. Mohri, Efficient algorithms for testing the twins property.Journal of Automata, Languages and Combinatorics8(2003) 117\u2013144."},{"key":"R2","unstructured":"J. Berstel and C. Reutenauer,Rational Series and Their Languages, volume 12 ofEATCS Monographs on Theoretical Computer Science. Springer-Verlag, Berlin Heidelberg New York (1984)."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"A.L. Buchsbaum, R. Giancarlo and J.R. Westbrook, On the determinization of weighted finite automata.SIAM Journal of Computing(2000) 1502\u20131531.","DOI":"10.1137\/S0097539798346676"},{"key":"R4","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1016\/S0304-3975(03)00344-X","volume":"310","author":"Chalopin","year":"2004","journal-title":"Theoretical Computer Science"},{"key":"R5","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0304-3975(77)90049-4","volume":"5","author":"Choffrut","year":"1977","journal-title":"Theoretical Computer Science"},{"key":"R6","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0097-8493(93)90079-O","volume":"17","author":"Culik II","year":"1993","journal-title":"Computer and Graphics"},{"key":"R7","unstructured":"G. Grahne and A. Thomo, Approximate reasoning in semi-structured databases. In8th International Workshop on Knowledge Representation meets Databases (KRDB2001), M. Lenzerini et al., Eds. volume 45 ofCEUR Workshop Proceedings(2001)."},{"key":"R8","unstructured":"U. Hafner,Low Bit-Rate Image and Video Coding with Weighted Finite Automata. PhD thesis, Universit\u00e4t W\u00fcrzburg (1999)."},{"key":"R9","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1016\/0890-5401(88)90033-8","volume":"78","author":"Hashiguchi","year":"1988","journal-title":"Information and Computation"},{"key":"R10","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0304-3975(90)90044-I","volume":"72","author":"Hashiguchi","year":"1990","journal-title":"Theoretical Computer Science"},{"key":"R11","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/S0304-3975(97)00260-0","volume":"233","author":"Hashiguchi","year":"2000","journal-title":"Theoretical Computer Science"},{"key":"R12","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1142\/S0218196702000845","volume":"12","author":"Hashiguchi","year":"2002","journal-title":"International Journal of Algebra and Computation"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"J. Hromkovi\u010d, J. Karhum\u00e4ki, H. Klauck, G. Schnitger and S. Seibert, Measures of nondeterminism in finite automata. InICALP'00 Proceedings, volume 1853 ofLecture Notes in Computer Science, U. Montanari et al., Eds. pages 199\u2013210. Springer-Verlag, Berlin (2000).","DOI":"10.1007\/3-540-45022-X_17"},{"key":"R14","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1006\/inco.2001.3069","volume":"172","author":"Hromkovi\u010d","year":"2002","journal-title":"Information and Computation"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"O. Ibarra and B. Ravikumar, On sparseness, ambiguity and other decision problems for acceptors and transducers. InSTACS'86 Proceedings, volume 210 ofLecture Notes in Computer Science, B. Monien and G. Vidal-Naquet, Eds. pages 171\u2013179. Springer-Verlag, Berlin (1986).","DOI":"10.1007\/3-540-16078-7_74"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"Z. Jiang, B. Litov and O. de Vel, Similarity enrichments in image compression through weighted finite automata. InCOCOON'00 Proceedings, volume 1858 ofLecture Notes in Computer Science, pages 447\u2013456. Springer-Verlag, Berlin (2000).","DOI":"10.1007\/3-540-44968-X_44"},{"key":"R17","unstructured":"F. Katritzke,Refinements of Data Compression using Weighted Finite Automata. PhD thesis, Universit\u00e4t Siegen (2001)."},{"key":"R18","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1051\/ita:2005027","volume":"39","author":"Kirsten","year":"2005","journal-title":"RAIRO-Theor. Inf. Appl."},{"key":"R19","unstructured":"D. Kirsten and I. M\u00e4urer, On the determinization of weighted automata.Journal of Automata, Languages and Combinatorics10(2005) 287\u2013312."},{"key":"R20","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/j.tcs.2004.02.049","volume":"327","author":"Klimann","year":"2004","journal-title":"Theoretical Computer Science"},{"key":"R21","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1142\/S0218196794000063","volume":"4","author":"Krob","year":"1994","journal-title":"International Journal of Algebra and Computation"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"W. Kuich, Semirings and formal power series. In G. Rozenberg and A. Salomaa, editors,Handbook of Formal Languages, Vol.\u00a01, Word, Language, Grammar, pages 609\u2013677. Springer-Verlag, Berlin (1997).","DOI":"10.1007\/978-3-642-59136-5_9"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"W. Kuich and A. Salomaa, editors.Semirings, Automata, Languages, volume 5 ofMonographs in Theoretical Computer Science.\u2000An EATCS Series. Springer-Verlag, Berlin (1986).","DOI":"10.1007\/978-3-642-69959-7_2"},{"key":"R24","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/0304-3975(91)90321-R","volume":"81","author":"Leung","year":"1991","journal-title":"Theoretical Computer Science"},{"key":"R25","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1137\/S0097539793252092","volume":"27","author":"Leung","year":"1998","journal-title":"SIAM Journal of Computing"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"H. Leung, The topological approach to the limitedness problem on distance automata. In J. Gunawardena, editor,Idempotency, pages 88\u2013111. Cambridge University Press (1998).","DOI":"10.1017\/CBO9780511662508.007"},{"key":"R27","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/S0304-3975(03)00377-3","volume":"310","author":"Leung","year":"2004","journal-title":"Theoretical Computer Science"},{"key":"R28","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1006\/inco.1995.1088","volume":"119","author":"M\u00e9tivier","year":"1995","journal-title":"Information and Computation"},{"key":"R29","first-page":"269","volume":"23","author":"Mohri","year":"1997","journal-title":"Computational Linguistics"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"A. Salomaa and M. Soittola,Automata-Theoretic Aspects of Formal Power Series. Texts and Monographs on Computer Science. Springer-Verlag, Berlin Heidelberg New York (1978).","DOI":"10.1007\/978-1-4612-6264-0"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"I. Simon, Recognizable sets with multiplicities in the tropical semiring. In M. P. Chytil et al., editors,MFCS'88 Proceedings, volume 324 ofLecture Notes in Computer Science, pages 107\u2013120. Springer-Verlag, Berlin (1988).","DOI":"10.1007\/BFb0017135"},{"key":"R32","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/0304-3975(90)90047-L","volume":"72","author":"Simon","year":"1990","journal-title":"Theoretical Computer Science"},{"key":"R33","unstructured":"I. Simon, A short proof of the factorization forest theorem. In M. Nivat and A. Podelski, Eds.Tree Automata and Languages, pages 433\u2013438. Elsevier Science Publishers B.V. (1992)."},{"key":"R34","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1051\/ita\/1994283-402771","volume":"28","author":"Simon","year":"1994","journal-title":"RAIRO-Theor. Inf. Appl."},{"key":"R35","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF01202281","volume":"26","author":"Weber","year":"1993","journal-title":"Mathematical Systems Theory"},{"key":"R36","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0304-3975(94)90287-9","volume":"134","author":"Weber","year":"1994","journal-title":"Theoretical Computer Science"}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita:2008017\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,11]],"date-time":"2019-05-11T20:51:42Z","timestamp":1557607902000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita:2008017"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6,3]]},"references-count":36,"journal-issue":{"issue":"3"},"alternative-id":["ita08014"],"URL":"https:\/\/doi.org\/10.1051\/ita:2008017","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"1290-385X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,6,3]]}}}