{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,26]],"date-time":"2025-06-26T04:11:21Z","timestamp":1750911081800,"version":"3.41.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2017,9,27]],"date-time":"2017-09-27T00:00:00Z","timestamp":1506470400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,7]]},"DOI":"10.1007\/s00224-017-9815-4","type":"journal-article","created":{"date-parts":[[2017,9,27]],"date-time":"2017-09-27T05:49:38Z","timestamp":1506491378000},"page":"1203-1222","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["From Tree Automata to String Automata Minimization"],"prefix":"10.1007","volume":"62","author":[{"given":"Younes","family":"Guellouma","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hadda","family":"Cherroun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Djelloul","family":"Ziadi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bruce W.","family":"Watson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,9,27]]},"reference":[{"key":"9815_CR1","unstructured":"Zilio, S., Lugiez, D.: XML schema, tree logic and sheaves automata. In: Rewriting Techniques and Applications (R. Nieuwenhuis, ed.), vol. 2706 of Lecture Notes in Computer Science, Springer Berlin Heidelberg (2003)"},{"key":"9815_CR2","doi-asserted-by":"crossref","unstructured":"Chidlovskii, B.: Using regular tree automata as XML schemas. In: Proceedings IEEE advances on digital libraries conference 2000, pp 89\u201398 (1999)","DOI":"10.1109\/ADL.2000.848373"},{"key":"9815_CR3","first-page":"3","volume-title":"Structures arborescentes et apprentissage automatique","author":"M Tommasi","year":"2006","unstructured":"Tommasi, M.: Structures arborescentes et apprentissage automatique, p 3. PhD thesis, Universit\u00e9 Charles de Gaulle - Lille (2006)"},{"issue":"5","key":"9815_CR4","doi-asserted-by":"crossref","first-page":"484","DOI":"10.1016\/S0019-9958(68)90917-0","volume":"13","author":"WS Brainerd","year":"1968","unstructured":"Brainerd, W.S.: The minimalization of tree automata. Inf. Control. 13(5), 484\u2013491 (1968)","journal-title":"Inf. Control."},{"issue":"4","key":"9815_CR5","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1016\/S0019-9958(68)90374-4","volume":"12","author":"MA Arbib","year":"1968","unstructured":"Arbib, M.A., Give\u2019on, Y.: Algebra automata I: Parallel programming as a prolegomena to the categorical approach. Inf. Control. 12(4), 331\u2013345 (1968)","journal-title":"Inf. Control."},{"key":"9815_CR6","doi-asserted-by":"crossref","unstructured":"Moore, E.F.: Gedanken Experiments on Sequential Machines. In: Automata Studies, pp. 129\u2013153, Princeton U. (1956)","DOI":"10.1515\/9781400882618-006"},{"key":"9815_CR7","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"JE Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Boston (1979)"},{"key":"9815_CR8","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/j.ipl.2011.12.004","volume":"112","author":"A Valmari","year":"2012","unstructured":"Valmari, A.: Fast brief practical DFA minimization. Inf. Process. Lett. 112, 213\u2013217 (2012)","journal-title":"Inf. Process. Lett."},{"key":"9815_CR9","first-page":"37","volume":"4","author":"F G\u00e9cseg","year":"1980","unstructured":"G\u00e9cseg, F., Steinby, M.: Minimal ascending tree automata. Acta Cybern. 4, 37\u201344 (1980)","journal-title":"Acta Cybern."},{"key":"9815_CR10","unstructured":"Comon, H., Dauchet, M., Gilleron, R., L\u00f6ding, C., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree automata techniques and applications, 2007. release October 12th (2007)"},{"key":"9815_CR11","unstructured":"Watson, B.W.: Taxonomies and Toolkits of Regular Language Algorithms. PhD thesis, Faculty of Mathematics and Computer Science, Eindhoven University of Technology (1995)"},{"issue":"1","key":"9815_CR12","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1017\/S1351324903003127","volume":"9","author":"BW Watson","year":"2003","unstructured":"Watson, B.W., Daciuk, J.: An efficient incremental DFA minimization algorithm. Nat. Lang. Eng. 9(1), 49\u201364 (2003)","journal-title":"Nat. Lang. Eng."},{"key":"9815_CR13","unstructured":"Cleophas, L.G., Kourie, D.G., Strauss, T., Watson, B.W.: On minimizing deterministic tree automata. In: Stringology (J. Holub and J. Zdrek, eds.), pp. 173\u2013182, Prague Stringology Club, Department of Computer Science and Engineering, Faculty of Electrical Engineering, Czech Technical University in Prague (2009)"},{"key":"9815_CR14","doi-asserted-by":"crossref","unstructured":"Almeida, M., Moreira, N., Reis, R.: Incremental DFA minimisation. In: CIAA (M. Domaratzki and K. Salomaa, eds.), vol. 6482 of Lecture Notes in Computer Science, pp. 39\u201348, Springer (2010)","DOI":"10.1007\/978-3-642-18098-9_5"},{"issue":"2","key":"9815_CR15","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/s00224-014-9588-y","volume":"57","author":"P Garc\u00eda","year":"2015","unstructured":"Garc\u00eda, P., V\u00e1zquez de Parga, M., Velasco, J.A., Lo\u0307pez, D.: A split-based incremental deterministic automata minimization algorithm. Theory Comput. Syst. 57(2), 319\u2013336 (2015)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"9815_CR16","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/s00453-008-9172-4","volume":"55","author":"RC Carrasco","year":"2009","unstructured":"Carrasco, R.C., Daciuk, J., Forcada, M.L.: Incremental construction of minimal tree automata. Algorithmica 55(1), 95\u2013110 (2009)","journal-title":"Algorithmica"},{"issue":"2","key":"9815_CR17","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1162\/089120102760173652","volume":"28","author":"RC Carrasco","year":"2002","unstructured":"Carrasco, R.C., Forcada, M.L.: Incremental construction and maintenance of minimal finite-state automata. Comput. Linguist. 28(2), 207\u2013216 (2002)","journal-title":"Comput. Linguist."},{"key":"9815_CR18","doi-asserted-by":"crossref","unstructured":"Carrasco, R.C., Daciuk, J., Forcada, M.L.: An implementation of deterministic tree automata minimization. In: CIAA (J. Holub and J. Zdarek, eds.), vol. 4783 of Lecture Notes in Computer Science, pp. 122\u2013129, Springer (2007)","DOI":"10.1007\/978-3-540-76336-9_13"},{"issue":"4","key":"9815_CR19","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1142\/S0129054109006814","volume":"20","author":"PA Abdulla","year":"2009","unstructured":"Abdulla, P.A., Bouajjani, A., Hol\u00edk, L., Kaati, L., Kaati, T.X.: Composed bisimulation for tree automata. Int. J. Found. Comput. Sci. 20(4), 685\u2013700 (2009)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"37","key":"9815_CR20","doi-asserted-by":"crossref","first-page":"3539","DOI":"10.1016\/j.tcs.2009.03.022","volume":"410","author":"J H\u00f6gberg","year":"2009","unstructured":"H\u00f6gberg, J., Maletti, A., May, J.: Backward and forward bisimulation minimization of tree automata. Theor. Comput. Sci. 410(37), 3539\u20133552 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"9815_CR21","doi-asserted-by":"crossref","unstructured":"Riley, M., Allauzen, C., Jansche, M.: OpenFst: An open-source, weighted finite-state transducer library and its applications to speech and language. In: Human Language Technologies: Conference of the North American Chapter of the Association of Computational Linguistics, Proceedings, May 31 - June 5, 2009, Boulder, Colorado, USA, Tutorial Abstracts, pp 9\u201310 (2009)","DOI":"10.3115\/1620950.1620955"},{"key":"9815_CR22","doi-asserted-by":"crossref","unstructured":"Kanthak, S., Ney, H.: FSA: An Efficient and Flexible C++ Toolkit for Finite State Automata Using On-Demand Computation. In: Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics, Barcelona, Spain, pp. 510\u2013517 (2004)","DOI":"10.3115\/1218955.1219020"},{"key":"9815_CR23","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1017\/S135132499700154X","volume":"2","author":"BW Watson","year":"1996","unstructured":"Watson, B.W.: Implementing and using finite automata toolkits. Nat. Lang. Eng. 2, 295\u2013302 (1996)","journal-title":"Nat. Lang. Eng."},{"issue":"6","key":"9815_CR24","doi-asserted-by":"crossref","first-page":"973","DOI":"10.1137\/0216062","volume":"16","author":"R Paige","year":"1987","unstructured":"Paige, R., Tarjan, R.E.: Three partition refinement algorithms. SIAM J. Comput. 16(6), 973\u2013989 (1987)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9815_CR25","doi-asserted-by":"crossref","first-page":"1322","DOI":"10.1007\/s00224-014-9544-x","volume":"57","author":"M Bousquet-M\u0117lou","year":"2015","unstructured":"Bousquet-M\u0117lou, M., Lohrey, M., Maneth, S., No\u0307th, E.: XML compression via directed acyclic graphs. Theory Comput. Syst. 57(4), 1322\u20131371 (2015)","journal-title":"Theory Comput. Syst."},{"issue":"2-3","key":"9815_CR26","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/S0167-6423(03)00012-1","volume":"48","author":"BW Watson","year":"2003","unstructured":"Watson, B.W.: A new algorithm for the construction of minimal acyclic DFAs. Sci. Comput. Program. 48(2-3), 81\u201397 (2003)","journal-title":"Sci. Comput. Program."},{"issue":"1","key":"9815_CR27","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0304-3975(92)90142-3","volume":"92","author":"D Revuz","year":"1992","unstructured":"Revuz, D.: Minimisation of acyclic deterministic automata in linear time. Theor. Comput. Sci. 92(1), 181\u2013189 (1992)","journal-title":"Theor. Comput. Sci."},{"key":"9815_CR28","unstructured":"Watson, B.W.: An incremental DFA minimization algorithm. In: Finite State Methods in Natural Language Processing (2001)"},{"key":"9815_CR29","doi-asserted-by":"crossref","unstructured":"Daciuk, J., Mihov, S., Watson, B.W., Watson, R.E.: Incremental construction of minimal acyclic finite-state automata, CoRR, vol. cs.CL\/0007009 (2000)","DOI":"10.1162\/089120100561601"},{"key":"9815_CR30","doi-asserted-by":"crossref","unstructured":"Hanneforth, T., Maletti, A., Quernheim, D.: Random generation of nondeterministic finite-state tree automata. In: Proceedings Second International Workshop on Trends in Tree Automata and Tree Transducers, TTATT 2013, Hanoi, Vietnam, 19\/10\/2013, pp 11\u201316 (2013)","DOI":"10.4204\/EPTCS.134.2"},{"key":"9815_CR31","unstructured":"Bubenzer, J.: Minimization of Acyclic DFAs. In: Proceedings of the Prague Stringology Conference 2011, Prague, Czech Republic, August 29-31 (2011)"},{"issue":"2","key":"9815_CR32","first-page":"180","volume":"22","author":"J Bj\u00f6rklund","year":"2016","unstructured":"Bj\u00f6rklund, J., Cleophas, L.: A Taxonomy of Minimisation Algorithms for Deterministic Tree Automata. J. Universal Comput. Sci. 22(2), 180\u2013196 (2016)","journal-title":"J. Universal Comput. Sci."},{"issue":"38-39","key":"9815_CR33","doi-asserted-by":"crossref","first-page":"3469","DOI":"10.1016\/j.tcs.2010.05.036","volume":"411","author":"P-C H\u0117am","year":"2010","unstructured":"H\u0117am, P.-C., Nicaud, C., Schmitz, S.: Parametric random generation of deterministic tree automata. Theor. Comput. Sci. 411(38-39), 3469\u20133480 (2010)","journal-title":"Theor. Comput. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9815-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9815-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9815-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,25]],"date-time":"2025-06-25T22:23:40Z","timestamp":1750890220000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9815-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,27]]},"references-count":33,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["9815"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9815-4","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2017,9,27]]}}}