{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T13:36:19Z","timestamp":1725888979216},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319602516"},{"type":"electronic","value":"9783319602523"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-60252-3_12","type":"book-chapter","created":{"date-parts":[[2017,6,2]],"date-time":"2017-06-02T14:59:13Z","timestamp":1496415553000},"page":"152-163","source":"Crossref","is-referenced-by-count":0,"title":["Recognizing Union-Find Trees Built Up Using Union-By-Rank Strategy is NP-Complete"],"prefix":"10.1007","author":[{"given":"Kitti","family":"Gelle","sequence":"first","affiliation":[]},{"given":"Szabolcs","family":"Iv\u00e1n","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,6,3]]},"reference":[{"key":"12_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/978-3-540-45138-9_15","volume-title":"Mathematical Foundations of Computer Science 2003","author":"H Bannai","year":"2003","unstructured":"Bannai, H., Inenaga, S., Shinohara, A., Takeda, M.: Inferring strings from graphs and arrays. In: Rovan, B., Vojt\u00e1\u0161, P. (eds.) MFCS 2003. LNCS, vol. 2747, pp. 208\u2013217. Springer, Heidelberg (2003). doi:\n10.1007\/978-3-540-45138-9_15"},{"issue":"6","key":"12_CR2","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/0020-0190(93)90037-A","volume":"45","author":"L Cai","year":"1993","unstructured":"Cai, L.: The recognition of Union trees. Inf. Process. Lett. 45(6), 279\u2013283 (1993)","journal-title":"Inf. Process. Lett."},{"key":"12_CR3","series-title":"STACS 2009, vol. 3 of LIPIcs","first-page":"289","volume-title":"26th International Symposium on Theoretical Aspects of Computer Science","author":"J Cl\u00e9ment","year":"2009","unstructured":"Cl\u00e9ment, J., Crochemore, M., Rindone, G.: Reverse engineering prefix tables. In: Albers, S., Marion, J.-Y. (eds.) 26th International Symposium on Theoretical Aspects of Computer Science. STACS 2009, vol. 3 of LIPIcs, pp. 289\u2013300. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany (2009)"},{"key":"12_CR4","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2001","unstructured":"Cormen, T.H., Stein, C., Rivest, R.L., Leiserson, C.E.: Introduction to Algorithms, 2nd edn. McGraw-Hill Higher Education, New York (2001)","edition":"2"},{"key":"12_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/978-3-642-13509-5_23","volume-title":"Combinatorial Pattern Matching","author":"M Crochemore","year":"2010","unstructured":"Crochemore, M., Iliopoulos, C.S., Pissis, S.P., Tischler, G.: Cover array string reconstruction. In: Amir, A., Parida, L. (eds.) CPM 2010. LNCS, vol. 6129, pp. 251\u2013259. Springer, Heidelberg (2010). doi:\n10.1007\/978-3-642-13509-5_23"},{"issue":"2","key":"12_CR6","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1051\/ita:2008030","volume":"43","author":"J-P Duval","year":"2009","unstructured":"Duval, J.-P., Lecroq, T., Lefebvre, A.: Efficient validation and construction of border arrays and validation of string matching automata. RAIRO - Theor. Inf. Appl. 43(2), 281\u2013297 (2009)","journal-title":"RAIRO - Theor. Inf. Appl."},{"issue":"3","key":"12_CR7","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1051\/ita:2002012","volume":"36","author":"J-P Duval","year":"2002","unstructured":"Duval, J.-P., Lefebvre, A.: Words over an ordered alphabet and suffix permutations. Theor. Inf. Appl. 36(3), 249\u2013259 (2002)","journal-title":"Theor. Inf. Appl."},{"issue":"1","key":"12_CR8","first-page":"51","volume":"10","author":"J-P Duval","year":"2005","unstructured":"Duval, J.-P., Lecroq, T., Lefebvre, A.: Border array on bounded alphabet. J. Autom. Lang. Comb. 10(1), 51\u201360 (2005)","journal-title":"J. Autom. Lang. Comb."},{"key":"12_CR9","doi-asserted-by":"crossref","unstructured":"Fredman, M., Saks, M.: The cell probe complexity of dynamic data structures. In: Proceedings of the Twenty-first Annual ACM Symposium on Theory of Computing, STOC 1989, pp. 345\u2013354. ACM, New York (1989)","DOI":"10.1145\/73007.73040"},{"issue":"5","key":"12_CR10","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1145\/364099.364331","volume":"7","author":"BA Galler","year":"1964","unstructured":"Galler, B.A., Fisher, M.J.: An improved equivalence algorithm. Commun. ACM 7(5), 301\u2013303 (1964)","journal-title":"Commun. ACM"},{"key":"12_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)"},{"issue":"2","key":"12_CR12","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/s00224-013-9522-8","volume":"54","author":"P Gawrychowski","year":"2014","unstructured":"Gawrychowski, P., Jez, A., Jez, \u0141.: Validating the Knuth-Morris-Pratt failure function, fast and online. Theory Comput. Syst. 54(2), 337\u2013372 (2014)","journal-title":"Theory Comput. Syst."},{"key":"12_CR13","unstructured":"Gelle, K., Iv\u00e1n, S.: Recognizing Union-Find trees is NP-complete. CoRR, abs\/1510.07462 (2015)"},{"key":"12_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1007\/978-3-642-00982-2_36","volume-title":"Language and Automata Theory and Applications","author":"T I","year":"2009","unstructured":"I, T., Inenaga, S., Bannai, H., Takeda, M.: Counting parameterized border arrays for a binary alphabet. In: Dediu, A.H., Ionescu, A.M., Mart\u00edn-Vide, C. (eds.) LATA 2009. LNCS, vol. 5457, pp. 422\u2013433. Springer, Heidelberg (2009). doi:\n10.1007\/978-3-642-00982-2_36"},{"issue":"50","key":"12_CR15","doi-asserted-by":"crossref","first-page":"6959","DOI":"10.1016\/j.tcs.2011.09.008","volume":"412","author":"I Tomohiro","year":"2011","unstructured":"Tomohiro, I., Inenaga, S., Bannai, H., Takeda, M.: Verifying and enumerating parameterized border arrays. Theoret. Comput. Sci. 412(50), 6959\u20136981 (2011)","journal-title":"Theoret. Comput. Sci."},{"issue":"Part 3","key":"12_CR16","first-page":"316","volume":"163","author":"I Tomohiro","year":"2014","unstructured":"Tomohiro, I., Inenaga, S., Bannai, H., Takeda, M.: Inferring strings from suffix trees and links on a binary alphabet. Discr. Appl. Math. 163(Part 3), 316\u2013325 (2014)","journal-title":"Discr. Appl. Math."},{"issue":"1","key":"12_CR17","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1145\/62029.62030","volume":"21","author":"K Knight","year":"1989","unstructured":"Knight, K.: Unification: a multidisciplinary survey. ACM Comput. Surv. 21(1), 93\u2013124 (1989)","journal-title":"ACM Comput. Surv."},{"issue":"22\u201324","key":"12_CR18","doi-asserted-by":"crossref","first-page":"915","DOI":"10.1016\/j.ipl.2013.09.009","volume":"113","author":"G Kucherov","year":"2013","unstructured":"Kucherov, G., T\u00f3thm\u00e9r\u00e9sz, L., Vialette, S.: On the combinatorics of suffix arrays. Inf. Process. Lett. 113(22\u201324), 915\u2013920 (2013)","journal-title":"Inf. Process. Lett."},{"key":"12_CR19","first-page":"223","volume":"42","author":"L Weilin","year":"2000","unstructured":"Weilin, L., Ryan, P.J., Smyth, W.F., Sun, Y., Yang, L.: Verifying a border array in linear time. J. Comb. Math. Comb. Comput. 42, 223\u2013236 (2000)","journal-title":"J. Comb. Math. Comb. Comput."},{"issue":"2","key":"12_CR20","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/j.cosrev.2010.09.009","volume":"5","author":"RM McConnell","year":"2011","unstructured":"McConnell, R.M., Mehlhorn, K., N\u00e4her, S., Schweitzer, P.: Certifying algorithms. Comput. Sci. Rev. 5(2), 119\u2013161 (2011)","journal-title":"Comput. Sci. Rev."},{"key":"12_CR21","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/j.jda.2015.01.005","volume":"32","author":"T Starikovskaya","year":"2015","unstructured":"Starikovskaya, T., Vildh\u00f8j, H.W.: A suffix tree or not a suffix tree? J. Discr. Algorithms 32, 14\u201323 (2015)","journal-title":"J. Discr. Algorithms"},{"issue":"2","key":"12_CR22","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"RE Tarjan","year":"1975","unstructured":"Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. J. ACM 22(2), 215\u2013225 (1975)","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-60252-3_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,2]],"date-time":"2017-06-02T15:02:03Z","timestamp":1496415723000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-60252-3_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319602516","9783319602523"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-60252-3_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}