{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:18:39Z","timestamp":1778807919750,"version":"3.51.4"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,6,26]],"date-time":"2015-06-26T00:00:00Z","timestamp":1435276800000},"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":["Theory Comput Syst"],"published-print":{"date-parts":[[2016,7]]},"DOI":"10.1007\/s00224-015-9635-3","type":"journal-article","created":{"date-parts":[[2015,6,25]],"date-time":"2015-06-25T03:37:01Z","timestamp":1435203421000},"page":"24-51","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["On the Parameterised Complexity of String Morphism Problems"],"prefix":"10.1007","volume":"59","author":[{"given":"Henning","family":"Fernau","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus L.","family":"Schmid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yngve","family":"Villanger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,26]]},"reference":[{"key":"9635_CR1","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.disopt.2010.10.003","volume":"8","author":"FN Abu-Khzam","year":"2011","unstructured":"Abu-Khzam, F.N., Fernau, H., Langston, M.A., Lee-Cultura, S., Stege, U.: A fixed-parameter algorithm for string-to-string correction. Discret. Optim. 8, 41\u201349 (2011)","journal-title":"Discret. Optim."},{"key":"9635_CR2","doi-asserted-by":"crossref","unstructured":"Amir, A., Aumann, Y., Cole, R., Lewenstein, M., Porat, E.: Function matching: Algorithms, applications, and a lower bound. In: Proceedings 30th International College on Automata, Languages and Programming, ICALP 2003, LNCS, vol. 2719, pp 929\u2013942 (2003)","DOI":"10.1007\/3-540-45061-0_72"},{"key":"9635_CR3","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. Discret. Algorithm. 5, 514\u2013523 (2007)","journal-title":"J. Discret. Algorithm."},{"key":"9635_CR4","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Finding patterns common to a set of strings. In: Proceedings 11th Annual ACM Symposium on Theory of Computing, STOC 1979, pp 130\u2013141 (1979)","DOI":"10.1145\/800135.804406"},{"key":"9635_CR5","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1006\/jcss.1996.0003","volume":"52","author":"BS Baker","year":"1996","unstructured":"Baker, B.S.: Parameterized pattern matching: Algorithms and applications. J. Comput. Syst. Sci. 52, 28\u201342 (1996)","journal-title":"J. Comput. Syst. Sci."},{"key":"9635_CR6","doi-asserted-by":"crossref","first-page":"1007","DOI":"10.1142\/S012905410300214X","volume":"14","author":"C C\u00e2mpeanu","year":"2003","unstructured":"C\u00e2mpeanu, C., Salomaa, K., Yu, S.: A formal study of practical regular expressions. Int. J. Found. Comput. Sci 14, 1007\u20131018 (2003)","journal-title":"Int. J. Found. Comput. Sci"},{"key":"9635_CR7","doi-asserted-by":"crossref","first-page":"654","DOI":"10.1016\/S0022-0000(03)00073-4","volume":"67","author":"M Cesati","year":"2003","unstructured":"Cesati, M.: The Turing way to parameterized complexity. J. Comput. Syst. Sci. 67, 654\u2013685 (2003)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9635_CR8","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1016\/j.tcs.2006.07.016","volume":"363","author":"J Chen","year":"2006","unstructured":"Chen, J., Zhang, F.: On product covering in 3-tier supply chain models: Natural complete problems for W[3] and W[4]. Theor. Comput. Sci. 363(3), 278\u2013288 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"9635_CR9","doi-asserted-by":"crossref","unstructured":"Clifford, R., Harrow, A.W., Popa, A., Sach, B.: Generalised matching. In: Proceedings 16th International Symposium on String Processing and Information Retrieval, SPIRE 2009, LNCS, vol. 5721, pp 295\u2013301 (2009)","DOI":"10.1007\/978-3-642-03784-9_29"},{"key":"9635_CR10","doi-asserted-by":"crossref","unstructured":"Downey, R., Fellows, M., Kapron, B., Hallett, M., Wareham, H.: Parameterized complexity of some problems in logic and linguistics (extended abstract). In: Proceedings 2nd Workshop on Structural Complexity and Recursion-theoretic Methods in Logic Programming, LNCS, vol. 813, pp 89\u2013101 (1994)","DOI":"10.1007\/3-540-58140-5_10"},{"key":"9635_CR11","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer (1999)","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"9635_CR12","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0020-0190(79)90135-2","volume":"9","author":"A Ehrenfeucht","year":"1979","unstructured":"Ehrenfeucht, A., Rozenberg, G.: Finding a homomorphism between two words is NP-complete. Inf. Process. Lett. 9, 86\u201388 (1979)","journal-title":"Inf. Process. Lett."},{"key":"9635_CR13","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"401","author":"MR Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 401, 53\u201361 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"9635_CR14","doi-asserted-by":"crossref","unstructured":"Fernau, H., Schmid, M.L.: Pattern matching with variables: A multivariate complexity analysis. In: Proceedings 24th Annual Symposium on Combinatorial Pattern Matching, CPM 2013, LNCS, vol. 7922, pp 83\u201394 (2013)","DOI":"10.1007\/978-3-642-38905-4_10"},{"key":"9635_CR15","unstructured":"Fernau, H., Schmid, M.L., Villanger, Y.: On the parameterised complexity of string morphism problems. In: Proceedings 33rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2013, Leibniz International Proceedings in Informatics (LIPIcs), vol. 24, pp 55\u201366 (2013)"},{"key":"9635_CR16","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer-Verlag New York, Inc., NJ, USA (2006)"},{"key":"9635_CR17","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Texts in Theoretical Computer Science. Springer (2010)","DOI":"10.1007\/978-3-642-16533-7"},{"key":"9635_CR18","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, 601\u2013628 (2006)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9635_CR19","unstructured":"Garey, M.R., Johnson, D.S.: Computers And Intractability. W. H. Freeman and Company (1979)"},{"key":"9635_CR20","doi-asserted-by":"crossref","unstructured":"Geilke, M., Zilles, S.: Learning relational patterns, vol. 6925, pp 84\u201398. Proceedings 22nd International Conference on Algorithmic Learning Theory, ALT 2011, LNCS (2011)","DOI":"10.1007\/978-3-642-24412-4_10"},{"key":"9635_CR21","doi-asserted-by":"crossref","unstructured":"Harju, T., Karhum\u00e4ki, J.: Morphisms. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 1, pp 439\u2013510. Springer (1997)","DOI":"10.1007\/978-3-642-59136-5_7"},{"key":"9635_CR22","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0167-8655(94)00091-G","volume":"16","author":"O Ibarra","year":"1995","unstructured":"Ibarra, O., Pong, T.C., Sohn, S.: A note on parsing pattern languages. Pattern Recog. Lett. 16, 179\u2013182 (1995)","journal-title":"Pattern Recog. Lett."},{"key":"9635_CR23","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity J. Comput. Syst. Sci. 63, 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"9635_CR24","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., Yu, S.: Pattern languages with and without erasing. Int. J. Comput. Math. 50, 147\u2013163 (1994)","journal-title":"Int. J. Comput. Math."},{"key":"9635_CR25","first-page":"41","volume":"105","author":"D Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the Exponential Time Hypothesis. EATCS Bullet. 105, 41\u201372 (2011)","journal-title":"EATCS Bullet."},{"key":"9635_CR26","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. RAIRO Inf. Th\u00e9or. Appl. 28, 233\u2013253 (1994)","journal-title":"RAIRO Inf. Th\u00e9or. Appl."},{"key":"9635_CR27","doi-asserted-by":"crossref","unstructured":"Pietrzak, K.: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. Comput. Syst. Sci. 67, 757\u2013771 (2003)","DOI":"10.1016\/S0022-0000(03)00078-3"},{"key":"9635_CR28","doi-asserted-by":"crossref","unstructured":"Reidenbach, D., Schmid, M.L.: A polynomial time match test for large classes of extended regular expressions. In: Proceedings 15th International Conference on Implementation and Application of Automata, CIAA 2010, LNCS, vol. 6482, pp 241\u2013250 (2011)","DOI":"10.1007\/978-3-642-18098-9_26"},{"key":"9635_CR29","doi-asserted-by":"crossref","unstructured":"Reidenbach, D., Schmid, M.L.: Patterns with bounded treewidth. In: Proceedings 6th International Conference on Language and Automata Theory and Applications, LATA 2012, LNCS, vol. 7183, pp 468\u2013479 (2012)","DOI":"10.1007\/978-3-642-28332-1_40"},{"key":"9635_CR30","doi-asserted-by":"crossref","unstructured":"Rinaudo, P., Ponty, Y., Barth, D., Denise, A.: Tree decomposition and parameterized algorithms for RNA structure-sequence alignment including tertiary interactions and pseudoknots \u2014 (extended abstract). In: Raphael, B.J., Tang, J. (eds.) Algorithms in Bioinformatics \u2014 12th International Workshop, WABI, LNCS, vol. 7534, pp 149\u2013164. Springer (2012)","DOI":"10.1007\/978-3-642-33122-0_12"},{"key":"9635_CR31","unstructured":"Schmid, M.L.: On the membership problem for pattern languages and related topics. Ph.D. thesis, Department of Computer Science, Loughborough Univer (2012)"},{"key":"9635_CR32","unstructured":"Shinohara, T.: Polynomial time inference of pattern languages and its application. In: Proceedings 7th IBM Symposium on Mathematical Foundations of Computer Science, pp 191\u2013209 (1982)"},{"key":"9635_CR33","doi-asserted-by":"crossref","unstructured":"Stephan, F., Yoshinaka, R., Zeugmann, T.: On the parameterised complexity of learning patterns. In: Proceedings 26th International Symposium on Computer and Information Sciences, ISCIS 2011, pp 277\u2013281","DOI":"10.1007\/978-1-4471-2155-8_35"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9635-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-015-9635-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9635-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,27]],"date-time":"2019-08-27T14:04:05Z","timestamp":1566914645000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-015-9635-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,26]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,7]]}},"alternative-id":["9635"],"URL":"https:\/\/doi.org\/10.1007\/s00224-015-9635-3","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6,26]]}}}