{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T03:51:28Z","timestamp":1743047488371,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642044199"},{"type":"electronic","value":"9783642044205"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-04420-5_9","type":"book-chapter","created":{"date-parts":[[2009,8,27]],"date-time":"2009-08-27T02:17:25Z","timestamp":1251339445000},"page":"79-92","source":"Crossref","is-referenced-by-count":0,"title":["How to Tackle Integer Weighted Automata Positivity"],"prefix":"10.1007","author":[{"given":"Yohan","family":"Boichut","sequence":"first","affiliation":[]},{"given":"Pierre-Cyrille","family":"H\u00e9am","sequence":"additional","affiliation":[]},{"given":"Olga","family":"Kouchnarenko","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"unstructured":"Abdulla, P.A., Cerans, K., Jonsson, B., Yih-Kuen, T.: General decidability theorems for infinite-state systems. In: Proc. 11th IEEE Symp. Logic in Computer Science (1996)","key":"9_CR1"},{"key":"9_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1007\/978-3-642-00596-1_25","volume-title":"FOSSACS","author":"P.A. Abdulla","year":"2009","unstructured":"Abdulla, P.A., Mayr, R.: Minimal cost reachability\/coverability in priced timed petri nets. In: de Alfaro, L. (ed.) FOSSACS. LNCS, vol.\u00a05504, pp. 348\u2013363. Springer, Heidelberg (2009)"},{"key":"9_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/3-540-45351-2_8","volume-title":"Hybrid Systems: Computation and Control","author":"R. Alur","year":"2001","unstructured":"Alur, R., La Torre, S., Pappas, G.J.: Optimal paths in weighted timed automata. In: Di Benedetto, M.D., Sangiovanni-Vincentelli, A.L. (eds.) HSCC 2001. LNCS, vol.\u00a02034, pp. 49\u201362. Springer, Heidelberg (2001)"},{"key":"9_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1007\/3-540-44585-4_34","volume-title":"Computer Aided Verification","author":"A. Annichini","year":"2001","unstructured":"Annichini, A., Bouajjani, A., Sighireanu, M.: Trex: A tool for reachability analysis of complex systems. In: Berry, G., Comon, H., Finkel, A. (eds.) CAV 2001. LNCS, vol.\u00a02102, pp. 368\u2013372. Springer, Heidelberg (2001)"},{"key":"9_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/978-3-540-79980-1_6","volume-title":"Algebraic Methodology and Software Technology","author":"E. Balland","year":"2008","unstructured":"Balland, E., Boichut, Y., Genet, T., Moreau, P.-E.: Towards an efficient implementation of tree automata completion. In: Meseguer, J., Ro\u015fu, G. (eds.) AMAST 2008. LNCS, vol.\u00a05140, pp. 67\u201382. Springer, Heidelberg (2008)"},{"issue":"5","key":"9_CR6","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/s10009-008-0064-3","volume":"10","author":"S. Bardin","year":"2008","unstructured":"Bardin, S., Finkel, A., Leroux, J., Petrucci, L.: Fast: acceleration from theory to practice. STTT\u00a010(5), 401\u2013424 (2008)","journal-title":"STTT"},{"issue":"3","key":"9_CR7","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/j.entcs.2006.05.007","volume":"154","author":"N. Bertrand","year":"2006","unstructured":"Bertrand, N., Schnoebelen, P.: A short visit to the sts hierarchy. Electr. Notes Theor. Comput. Sci.\u00a0154(3), 59\u201369 (2006)","journal-title":"Electr. Notes Theor. Comput. Sci."},{"key":"9_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/978-3-540-70590-1_4","volume-title":"Rewriting Techniques and Applications","author":"Y. Boichut","year":"2008","unstructured":"Boichut, Y., Courbis, R., H\u00e9am, P.-C., Kouchnarenko, O.: Finer is better: Abstraction refinement for rewriting approximations. In: Voronkov, A. (ed.) RTA 2008. LNCS, vol.\u00a05117, pp. 48\u201362. Springer, Heidelberg (2008)"},{"key":"9_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/978-3-540-73449-9_6","volume-title":"Term Rewriting and Applications","author":"Y. Boichut","year":"2007","unstructured":"Boichut, Y., Genet, T., Jensen, T., Le Roux, L.: Rewriting Approximations for Fast Prototyping of Static Analyzers. In: Baader, F. (ed.) RTA 2007. LNCS, vol.\u00a04533, pp. 48\u201362. Springer, Heidelberg (2007)"},{"issue":"1","key":"9_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ipl.2008.03.012","volume":"108","author":"Y. Boichut","year":"2008","unstructured":"Boichut, Y., H\u00e9am, P.-C.: A theoretical limit for safety verification techniques with regular fix-point computations. Inf. Process. Lett.\u00a0108(1), 1\u20132 (2008)","journal-title":"Inf. Process. Lett."},{"key":"9_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-45619-8_1","volume-title":"Logic Programming","author":"B. Boigelot","year":"2002","unstructured":"Boigelot, B., Wolper, P.: Representing arithmetic constraints with finite automata: An overview. In: Stuckey, P.J. (ed.) ICLP 2002. LNCS, vol.\u00a02401, pp. 1\u201319. Springer, Heidelberg (2002)"},{"issue":"2","key":"9_CR12","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/s10703-007-0035-4","volume":"31","author":"P. Bouyer","year":"2007","unstructured":"Bouyer, P., Brihaye, T., Bruy\u00e8re, V., Raskin, J.-C.: On the optimal reachability problem of weighted timed automata. Formal Methods in System Design\u00a031(2), 135\u2013175 (2007)","journal-title":"Formal Methods in System Design"},{"issue":"4","key":"9_CR13","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1007\/s00453-001-0026-6","volume":"30","author":"A.L. Buchsbaum","year":"2001","unstructured":"Buchsbaum, A.L., Giancarlo, R., Westbrook, J.: An approximate determinization algorithm for weighted finite-state automata. Algorithmica\u00a030(4), 503\u2013526 (2001)","journal-title":"Algorithmica"},{"unstructured":"Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree automata techniques and applications (2002), http:\/\/www.grappa.univ-lille3.fr\/tata\/","key":"9_CR14"},{"issue":"1-2","key":"9_CR15","doi-asserted-by":"publisher","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.\u00a0380(1-2), 69\u201386 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/978-3-540-27813-9_46","volume-title":"Computer Aided Verification","author":"A. Farzan","year":"2004","unstructured":"Farzan, A., Chen, C., Meseguer, J., Rosu, G.: Formal analysis of java programs in javafan. In: Alur, R., Peled, D.A. (eds.) CAV 2004. LNCS, vol.\u00a03114, pp. 501\u2013505. Springer, Heidelberg (2004)"},{"issue":"2","key":"9_CR17","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1016\/0890-5401(90)90009-7","volume":"89","author":"A. Finkel","year":"1990","unstructured":"Finkel, A.: Reduction and covering of infinite reachability trees. Information and Computation\u00a089(2), 144\u2013179 (1990)","journal-title":"Information and Computation"},{"issue":"1-2","key":"9_CR18","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/S0304-3975(00)00102-X","volume":"256","author":"A. Finkel","year":"2001","unstructured":"Finkel, A., Schnoebelen, P.: Well-structured transition systems everywhere! TCS\u00a0256(1-2), 63\u201392 (2001)","journal-title":"TCS"},{"doi-asserted-by":"crossref","unstructured":"Gaubert, S.: Performance Evaluation of (max,+) Automata. IEEE Trans. on Automatic Control\u00a040(12) (1995)","key":"9_CR19","DOI":"10.1109\/9.478227"},{"key":"9_CR20","series-title":"LNAI","doi-asserted-by":"publisher","DOI":"10.1007\/10721959_21","volume-title":"Automated Deduction - CADE-17","author":"T. Genet","year":"2000","unstructured":"Genet, T., Klay, F.: Rewriting for Cryptographic Protocol Verification. In: McAllester, D. (ed.) CADE 2000. LNCS (LNAI), vol.\u00a01831, Springer, Heidelberg (2000)"},{"unstructured":"Genet, T.: Timbuk 3.0 : Equationnal approximations, http:\/\/www.irisa.fr\/lande\/genet\/timbuk\/","key":"9_CR21"},{"key":"9_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/BFb0052368","volume-title":"Rewriting Techniques and Applications","author":"T. Genet","year":"1998","unstructured":"Genet, T.: Decidable approximations of sets of descendants and sets of normal forms. In: Nipkow, T. (ed.) RTA 1998. LNCS, vol.\u00a01379, p. 151. Springer, Heidelberg (1998)"},{"key":"9_CR23","doi-asserted-by":"crossref","first-page":"157","DOI":"10.3233\/FI-1995-24127","volume":"24","author":"R. Gilleron","year":"1995","unstructured":"Gilleron, R., Tison, S.: Regular tree languages and rewrite systems. Fundamenta Informaticae\u00a024, 157\u2013175 (1995)","journal-title":"Fundamenta Informaticae"},{"key":"9_CR24","doi-asserted-by":"publisher","first-page":"1043","DOI":"10.1090\/S0002-9939-1966-0201310-3","volume":"7","author":"S. Ginsburg","year":"1966","unstructured":"Ginsburg, S., Spanier, E.H.: Bounded regular sets. Proceedings of the American Mathematical Society\u00a07, 1043\u20131049 (1966)","journal-title":"Proceedings of the American Mathematical Society"},{"doi-asserted-by":"crossref","unstructured":"Hashiguchi, K., Ishiguro, K., Jimbo, S.: Decidability of the Equivalence Problem for Finitely Ambiguous Finance Automata. IJAC\u00a012(3) (2002)","key":"9_CR25","DOI":"10.1142\/S0218196702000845"},{"issue":"1","key":"9_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1042038.1042039","volume":"6","author":"T.A. Henzinger","year":"2005","unstructured":"Henzinger, T.A., Majumdar, R., Raskin, J.F.: A classification of symbolic transition systems. ACM Trans. Comput. Log.\u00a06(1), 1\u201332 (2005)","journal-title":"ACM Trans. Comput. Log."},{"issue":"4","key":"9_CR27","first-page":"227","volume":"5","author":"K. Culik II","year":"1999","unstructured":"Culik II, K., von Rosenberg, P.C.: Generalized weighted finite automata based image compression. J. UCS\u00a05(4), 227\u2013242 (1999)","journal-title":"J. UCS"},{"issue":"1","key":"9_CR28","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/j.tcs.2003.10.011","volume":"313","author":"F. Katritzke","year":"2004","unstructured":"Katritzke, F., Merzenich, W., Thomas, M.: Enhancements of partitioning techniques for image compression using weighted finite automata. TCS\u00a0313(1), 133\u2013144 (2004)","journal-title":"TCS"},{"unstructured":"Kirsten, D., Lombardy, S.: Deciding unambiguity and sequentiality of polynomially ambiguous min-plus automata. In: STACS, pp. 589\u2013600 (2009)","key":"9_CR29"},{"issue":"3","key":"9_CR30","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1016\/j.tcs.2004.02.049","volume":"327","author":"I. Klimann","year":"2004","unstructured":"Klimann, I., Lombardy, S., Mairesse, J., Prieur, C.: Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton. TCS\u00a0327(3), 349\u2013373 (2004)","journal-title":"TCS"},{"doi-asserted-by":"crossref","unstructured":"Krob, D.: The Equality Problem for Rational Series with Multiplicities in the Tropical Semiring is Undecidable. IJAC\u00a04(3) (1994)","key":"9_CR31","DOI":"10.1142\/S0218196794000063"},{"issue":"2-3","key":"9_CR32","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/j.tcs.2007.09.021","volume":"390","author":"K.G. Larsen","year":"2008","unstructured":"Larsen, K.G., Rasmussen, J.I.: Optimal reachability for multi-priced timed automata. Theor. Comput. Sci.\u00a0390(2-3), 197\u2013213 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9_CR33","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1016\/j.tcs.2008.09.037","volume":"409","author":"J. Leroux","year":"2008","unstructured":"Leroux, J.: Structural presburger digit vector automata. TCS\u00a0409(3), 549\u2013556 (2008)","journal-title":"TCS"},{"doi-asserted-by":"crossref","unstructured":"Lombardy, S.: Sequentialization and unambiguity of (max,+) rational series over one letter. In: Gaubert, S., Loiseau, J.-J. (eds.) Workshop on max-plus Algebras and Their Applications to Discrete-event Systems, TCS, and Optimization, Prague. IFAC, Elsevier Sciences (2001)","key":"9_CR34","DOI":"10.1016\/S1474-6670(17)39086-9"},{"key":"9_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-25984-8_1","volume-title":"Automated Reasoning","author":"J. Meseguer","year":"2004","unstructured":"Meseguer, J., Rosu, G.: Rewriting logic semantics: From language specifications to formal analysis tools. In: Basin, D., Rusinowitch, M. (eds.) IJCAR 2004. LNCS, vol.\u00a03097, pp. 1\u201344. Springer, Heidelberg (2004)"},{"issue":"1","key":"9_CR36","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1006\/csla.2001.0184","volume":"16","author":"M. Mohri","year":"2002","unstructured":"Mohri, M., Pereira, F., Riley, M.: Weighted finite-state transducers in speech recognition. Computer Speech & Language\u00a016(1), 69\u201388 (2002)","journal-title":"Computer Speech & Language"},{"key":"9_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/11591191_28","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"D. Tabakov","year":"2005","unstructured":"Tabakov, D., Vardi, M.Y.: Experimental evaluation of classical automata constructions. In: Sutcliffe, G., Voronkov, A. (eds.) LPAR 2005. LNCS, vol.\u00a03835, pp. 396\u2013411. Springer, Heidelberg (2005)"},{"doi-asserted-by":"crossref","unstructured":"Weber, A.: Finite-valued Distance Automata. In: TCS, p. 134 (1994)","key":"9_CR38","DOI":"10.1016\/0304-3975(94)90287-9"}],"container-title":["Lecture Notes in Computer Science","Reachability Problems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04420-5_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,21]],"date-time":"2020-05-21T19:49:29Z","timestamp":1590090569000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04420-5_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642044199","9783642044205"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04420-5_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}