{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T15:53:23Z","timestamp":1742918003574,"version":"3.40.3"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319135236"},{"type":"electronic","value":"9783319135243"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-13524-3_23","type":"book-chapter","created":{"date-parts":[[2014,12,2]],"date-time":"2014-12-02T17:51:38Z","timestamp":1417542698000},"page":"270-281","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Parameterized Study of Maximum Generalized Pattern Matching Problems"],"prefix":"10.1007","author":[{"given":"Sebastian","family":"Ordyniak","sequence":"first","affiliation":[]},{"given":"Alexandru","family":"Popa","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,12,3]]},"reference":[{"issue":"3","key":"23_CR1","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.jda.2006.10.001","volume":"5","author":"A Amir","year":"2007","unstructured":"Amir, A., Nor, I.: Generalized function matching. J. Discrete Algorithms 5(3), 514\u2013523 (2007)","journal-title":"J. Discrete Algorithms"},{"key":"23_CR2","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Finding patterns common to a set of strings (extended abstract). In: Proceedings of the 11h Annual ACM Symposium on Theory of Computing, 30 April\u20132 May, Atlanta, Georgia, USA, pp. 130\u2013141 (1979)","DOI":"10.1145\/800135.804406"},{"issue":"1","key":"23_CR3","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/0022-0000(80)90041-0","volume":"21","author":"D Angluin","year":"1980","unstructured":"Angluin, D.: Finding patterns common to a set of strings. J. Comput. Syst. Sci. 21(1), 46\u201362 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"23_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/978-3-642-03784-9_29","volume-title":"String Processing and Information Retrieval","author":"R Clifford","year":"2009","unstructured":"Clifford, R., Harrow, A.W., Popa, A., Sach, B.: Generalised matching. In: Karlgren, J., Tarhio, J., Hyyr\u00f6, H. (eds.) SPIRE 2009. LNCS, vol. 5721, pp. 295\u2013301. Springer, Heidelberg (2009)"},{"key":"23_CR5","unstructured":"Clifford, R., Popa, A.: (In)approximability results for pattern matching problems. In: Holub, J., Zd\u00e1rek, J. (eds.) Proceedings of the Prague Stringology Conference 2010, Prague, Czech Republic, 30 August\u20131 September, pp. 52\u201362. Prague Stringology Club, Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague (2010)"},{"key":"23_CR6","series-title":"Monographs in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)"},{"issue":"2","key":"23_CR7","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0020-0190(79)90135-2","volume":"9","author":"A Ehrenfreucht","year":"1979","unstructured":"Ehrenfreucht, A., Rozenberg, G.: Finding a homomorphism between two words in np-complete. Inf. Process. Lett. 9(2), 86\u201388 (1979)","journal-title":"Inf. Process. Lett."},{"key":"23_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/978-3-642-38905-4_10","volume-title":"Combinatorial Pattern Matching","author":"H Fernau","year":"2013","unstructured":"Fernau, H., Schmid, M.L.: Pattern matching with variables: a multivariate complexity analysis. In: Fischer, J., Sanders, P. (eds.) CPM 2013. LNCS, vol. 7922, pp. 83\u201394. Springer, Heidelberg (2013)"},{"key":"23_CR9","unstructured":"Fernau, H., Schmid, M.L., Villanger, Y.: On the parameterised complexity of string morphism problems. In: Seth, A., Vishnoi, N.K. (eds). IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2013. LIPIcs, 12\u201314 December 2013, Guwahati, India, vol. 24, pp. 55\u201366. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2013)"},{"key":"23_CR10","series-title":"Texts in Theoretical Computer Science. An EATCS Series","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, vol. XIV. Springer, Berlin (2006)"},{"key":"23_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1007\/11505877_22","volume-title":"Developments in Language Theory","author":"DD Freydenberger","year":"2005","unstructured":"Freydenberger, D.D., Reidenbach, D., Schneider, J.C.: Unambiguous morphic images of strings. In: De Felice, C., Restivo, A. (eds.) DLT 2005. LNCS, vol. 3572, pp. 248\u2013259. Springer, Heidelberg (2005)"},{"issue":"3\u20134","key":"23_CR12","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1080\/00207169408804252","volume":"50","author":"T Jiang","year":"1994","unstructured":"Jiang, T., Kinber, E., Salomaa, A., Salomaa, K., Yu, S.: Pattern languages with and without erasing. Int. J. Comput. Math. 50(3\u20134), 147\u2013163 (1994)","journal-title":"Int. J. Comput. Math."},{"issue":"3\u20134","key":"23_CR13","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1051\/ita\/1994283-402331","volume":"28","author":"A Mateescu","year":"1994","unstructured":"Mateescu, A., Salomaa, A.: Finite degrees of ambiguity in pattern languages. Inform. Th\u00e9orique et Appl. 28(3\u20134), 233\u2013253 (1994)","journal-title":"Inform. Th\u00e9orique et Appl."},{"issue":"13","key":"23_CR14","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/j.tcs.2008.02.028","volume":"397","author":"YK Ng","year":"2008","unstructured":"Ng, Y.K., Shinohara, T.: Developments from enquiries into the learnability of the pattern languages from positive data. Theor. Comput. Sci. 397(13), 150\u2013165 (2008). Forty Years of Inductive Inference: Dedicated to the 60th Birthday of Rolf Wiehagen","journal-title":"Theor. Comput. Sci."},{"key":"23_CR15","doi-asserted-by":"crossref","unstructured":"Ordyniak, S., Popa, A.: A parameterized study of maximum generalized pattern matching problems. CoRR, abs\/1402.6109 (2014)","DOI":"10.1007\/978-3-319-13524-3_23"},{"issue":"4","key":"23_CR16","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1016\/S0022-0000(03)00078-3","volume":"67","author":"K Pietrzak","year":"2003","unstructured":"Pietrzak, K.: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. Comput. Syst. Sci. 67(4), 757\u2013771 (2003)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"23_CR17","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.tcs.2005.10.017","volume":"350","author":"D Reidenbach","year":"2006","unstructured":"Reidenbach, D.: A non-learnable class of e-pattern languages. Theor. Comput. Sci. 350(1), 91\u2013102 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"13","key":"23_CR18","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/j.tcs.2008.02.029","volume":"397","author":"D Reidenbach","year":"2008","unstructured":"Reidenbach, D.: Discontinuities in pattern inference. Theor. Comput. Sci. 397(13), 166\u2013193 (2008). Forty Years of Inductive Inference: Dedicated to the 60th Birthday of Rolf Wiehagen","journal-title":"Theor. Comput. Sci."},{"issue":"19\u201321","key":"23_CR19","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1016\/j.ipl.2013.06.011","volume":"113","author":"ML Schmid","year":"2013","unstructured":"Schmid, M.L.: A note on the complexity of matching patterns with variables. Inf. Process. Lett. 113(19\u201321), 729\u2013733 (2013)","journal-title":"Inf. Process. Lett."},{"key":"23_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/3-540-11980-9_19","volume-title":"RIMS Symposium on Software Science and Engineering","author":"S Takeshi","year":"1983","unstructured":"Takeshi, S.: Polynomial time inference of extended regular pattern languages. In: Goto, E., Furukawa, K., Nakajima, R., Nakata, I., Yonezawa, A. (eds.) RIMS 1982. LNCS, vol. 147, pp. 115\u2013127. Springer, Heidelberg (1983)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-13524-3_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,15]],"date-time":"2023-02-15T02:25:32Z","timestamp":1676427932000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-13524-3_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319135236","9783319135243"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-13524-3_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"3 December 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}