{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T22:29:11Z","timestamp":1791412151107,"version":"4.3.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,6,17]],"date-time":"2015-06-17T00:00:00Z","timestamp":1434499200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,5]]},"DOI":"10.1007\/s00453-015-0008-8","type":"journal-article","created":{"date-parts":[[2015,6,16]],"date-time":"2015-06-16T14:57:39Z","timestamp":1434466659000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["A Parameterized Study of Maximum Generalized Pattern Matching Problems"],"prefix":"10.1007","volume":"75","author":[{"given":"Sebastian","family":"Ordyniak","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexandru","family":"Popa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,6,17]]},"reference":[{"issue":"3","key":"8_CR1","doi-asserted-by":"crossref","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":"8_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, April 30-May 2, 1979, Atlanta, GA, USA, pp. 130\u2013141 (1979)","DOI":"10.1145\/800135.804406"},{"issue":"1","key":"8_CR3","doi-asserted-by":"crossref","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":"8_CR4","doi-asserted-by":"crossref","unstructured":"Clifford, R., Harrow, A.W., Popa, A., Sach, B.: Generalised matching. In: Karlgren, J., Tarhio, J., Hyyr\u00f6, H. (eds.) Proceedings od the 16th International Symposium String Processing and Information Retrieval (SPIRE 2009), Saariselk\u00e4, Finland, August 25\u201327, 2009, Volume 5721 of Lecture Notes in Computer Science, pp. 295\u2013301. Springer, Berlin (2009)","DOI":"10.1007\/978-3-642-03784-9_29"},{"key":"8_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, August 30\u2013September 1, 2010, pp. 52\u201362. Prague Stringology Club, Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague (2010)"},{"key":"8_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity. Monographs in Computer Science","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":"8_CR7","doi-asserted-by":"crossref","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":"8_CR8","doi-asserted-by":"crossref","unstructured":"Fernau, H., Schmid, M.L.: Pattern matching with variables: a multivariate complexity analysis. In: Fischer, J., Sanders, P. (eds.) Combinatorial pattern matching, Proceedings of 24th Annual Symposium, CPM 2013, Bad Herrenalb, Germany, June 17\u201319, 2013, Lecture Notes in Computer Science, vol. 7922, pp. 83\u201394. Springer, Berlin, Heidelberg (2013)","DOI":"10.1007\/978-3-642-38905-4_10"},{"key":"8_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), December 12\u201314, 2013, Guwahati, India, Volume 24 of LIPIcs, pp. 55\u201366. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik (2013)"},{"key":"8_CR10","volume-title":"Parameterized Complexity Theory, volume XIV of Texts in Theoretical Computer Science. An EATCS Series","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory, volume XIV of Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2006)"},{"issue":"3","key":"8_CR11","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1142\/S0129054106004017","volume":"17","author":"DD Freydenberger","year":"2006","unstructured":"Freydenberger, D.D., Reidenbach, D., Schneider, J.C.: Unambiguous morphic images of strings. Int. J. Found. Comput. Sci. 17(3), 601\u2013628 (2006)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"3\u20134","key":"8_CR12","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1080\/00207169408804252","volume":"50","author":"T Jiang","year":"1994","unstructured":"Jiang, T., Kinber, E., Salomaa, A., Salomaa, K., Sheng, Y.: 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":"8_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. Informatique Th\u00e9orique et Applications 28(3\u20134), 233\u2013253 (1994)","journal-title":"Informatique Th\u00e9orique et Applications"},{"key":"8_CR14","doi-asserted-by":"crossref","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","DOI":"10.1016\/j.tcs.2008.02.028"},{"issue":"4","key":"8_CR15","doi-asserted-by":"crossref","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":"8_CR16","doi-asserted-by":"crossref","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."},{"key":"8_CR17","doi-asserted-by":"crossref","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","DOI":"10.1016\/j.tcs.2008.02.029"},{"key":"8_CR18","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.ic.2014.08.010","volume":"239","author":"D Reidenbach","year":"2014","unstructured":"Reidenbach, D., Schmid, M.L.: Patterns with bounded treewidth. Inf. Comput. 239, 87\u201399 (2014)","journal-title":"Inf. Comput."},{"issue":"19\u201321","key":"8_CR19","doi-asserted-by":"crossref","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":"8_CR20","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/3-540-11980-9_19","volume-title":"RIMS Symposia on Software Science and Engineering, Volume 147 of Lecture Notes in Computer Science","author":"T Shinohara","year":"1983","unstructured":"Shinohara, T.: Polynomial Time Inference Of Extended Regular Pattern Languages. In: Goto, E., Furukawa, K., Nakajima, R., Nakata, I., Yonezawa, A. (eds.) RIMS Symposia on Software Science and Engineering, Volume 147 of Lecture Notes in Computer Science, pp. 115\u2013127. Springer, Berlin (1983)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0008-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0008-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0008-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T17:41:41Z","timestamp":1748454101000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0008-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,17]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,5]]}},"alternative-id":["8"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0008-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6,17]]}}}