{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T16:27:30Z","timestamp":1725467250734},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642389047"},{"type":"electronic","value":"9783642389054"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38905-4_10","type":"book-chapter","created":{"date-parts":[[2013,5,16]],"date-time":"2013-05-16T03:28:54Z","timestamp":1368674934000},"page":"83-94","source":"Crossref","is-referenced-by-count":7,"title":["Pattern Matching with Variables: A Multivariate Complexity Analysis"],"prefix":"10.1007","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"}]}],"member":"297","reference":[{"key":"10_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1007\/3-540-45061-0_72","volume-title":"Automata, Languages and Programming","author":"A. Amir","year":"2003","unstructured":"Amir, A., Aumann, Y., Cole, R., Lewenstein, M., Porat, E.: Function matching: Algorithms, applications, and a lower bound. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 929\u2013942. Springer, Heidelberg (2003)"},{"key":"10_CR2","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. Journal of Discrete Algorithms\u00a05, 514\u2013523 (2007)","journal-title":"Journal of Discrete Algorithms"},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Finding patterns common to a set of strings. In: Proc. 11th Annual ACM Symposium on Theory of Computing, STOC 1979, pp. 130\u2013141 (1979)","DOI":"10.1145\/800135.804406"},{"key":"10_CR4","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. Journal of Computer and System Sciences\u00a021, 46\u201362 (1980)","journal-title":"Journal of Computer and System Sciences"},{"key":"10_CR5","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1006\/jcss.1996.0003","volume":"52","author":"B.S. Baker","year":"1996","unstructured":"Baker, B.S.: Parameterized pattern matching: Algorithms and applications. Journal of Computer and System Sciences\u00a052, 28\u201342 (1996)","journal-title":"Journal of Computer and System Sciences"},{"key":"10_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1007\/978-3-642-14455-4_11","volume-title":"Developments in Language Theory","author":"J. Bremer","year":"2010","unstructured":"Bremer, J., Freydenberger, D.D.: Inclusion problems for patterns with a bounded number of variables. In: Gao, Y., Lu, H., Seki, S., Yu, S. (eds.) DLT 2010. LNCS, vol.\u00a06224, pp. 100\u2013111. Springer, Heidelberg (2010)"},{"key":"10_CR7","doi-asserted-by":"publisher","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. International Journal of Foundations of Computer Science\u00a014, 1007\u20131018 (2003)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"10_CR8","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.\u00a05721, pp. 295\u2013301. Springer, Heidelberg (2009)"},{"key":"10_CR9","doi-asserted-by":"publisher","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. Information Processing Letters\u00a09, 86\u201388 (1979)","journal-title":"Information Processing Letters"},{"key":"10_CR10","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.ic.2009.04.002","volume":"208","author":"D.D. Freydenberger","year":"2010","unstructured":"Freydenberger, D.D., Reidenbach, D.: Bad news on decision problems for patterns. Information and Computation\u00a0208, 83\u201396 (2010)","journal-title":"Information and Computation"},{"key":"10_CR11","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1142\/S0129054106004017","volume":"17","author":"D.D. Freydenberger","year":"2006","unstructured":"Freydenberger, D.D., Reidenbach, D., Schneider, J.C.: Unambiguous morphic images of strings. International Journal of Foundations of Computer Science\u00a017, 601\u2013628 (2006)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"10_CR12","volume-title":"Mastering Regular Expressions","author":"J.E.F. Friedl","year":"2006","unstructured":"Friedl, J.E.F.: Mastering Regular Expressions, 3rd edn. O\u2019Reilly, Sebastopol (2006)","edition":"3"},{"key":"10_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/978-3-642-24412-4_10","volume-title":"Algorithmic Learning Theory","author":"M. Geilke","year":"2011","unstructured":"Geilke, M., Zilles, S.: Learning relational patterns. In: Kivinen, J., Szepesv\u00e1ri, C., Ukkonen, E., Zeugmann, T. (eds.) ALT 2011. LNCS, vol.\u00a06925, pp. 84\u201398. Springer, Heidelberg (2011)"},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"Harju, T., Karhum\u00e4ki, J.: Morphisms. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol.\u00a01, ch. 7, pp. 439\u2013510. Springer (1997)","DOI":"10.1007\/978-3-642-59136-5_7"},{"key":"10_CR15","doi-asserted-by":"publisher","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 Recognition Letters\u00a016, 179\u2013182 (1995)","journal-title":"Pattern Recognition Letters"},{"key":"10_CR16","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. International Journal of Computer Mathematics\u00a050, 147\u2013163 (1994)","journal-title":"International Journal of Computer Mathematics"},{"key":"10_CR17","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1006\/jcss.1995.1006","volume":"50","author":"T. Jiang","year":"1995","unstructured":"Jiang, T., Salomaa, A., Salomaa, K., Yu, S.: Decision problems for patterns. Journal of Computer and System Sciences\u00a050, 53\u201363 (1995)","journal-title":"Journal of Computer and System Sciences"},{"key":"10_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/BFb0017162","volume-title":"Mathematical Foundations of Computer Science 1988","author":"J. Kratochv\u00edl","year":"1988","unstructured":"Kratochv\u00edl, J., K\u0159iv\u00e1nek, M.: On the computational complexity of codes in graphs. In: Koubek, V., Janiga, L., Chytil, M.P. (eds.) MFCS 1988. LNCS, vol.\u00a0324, pp. 396\u2013404. Springer, Heidelberg (1988)"},{"key":"10_CR19","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 Informatique Th\u00e9oretique et Applications\u00a028, 233\u2013253 (1994)","journal-title":"RAIRO Informatique Th\u00e9oretique et Applications"},{"key":"10_CR20","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/j.tcs.2008.02.028","volume":"397","author":"Y.K. Ng","year":"2008","unstructured":"Ng, Y.K., Shinohara, T.: Developments from enquiries into the learnability of the pattern languages from positive data. Theoretical Computer Science\u00a0397, 150\u2013165 (2008)","journal-title":"Theoretical Computer Science"},{"key":"10_CR21","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/S0304-3975(96)00289-7","volume":"186","author":"E. Ohlebusch","year":"1997","unstructured":"Ohlebusch, E., Ukkonen, E.: On the equivalence problem for E-pattern languages. Theoretical Computer Science\u00a0186, 231\u2013248 (1997)","journal-title":"Theoretical Computer Science"},{"key":"10_CR22","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. Theoretical Computer Science\u00a0350, 91\u2013102 (2006)","journal-title":"Theoretical Computer Science"},{"key":"10_CR23","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. Theoretical Computer Science\u00a0397, 166\u2013193 (2008)","journal-title":"Theoretical Computer Science"},{"key":"10_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/978-3-642-18098-9_26","volume-title":"Implementation and Application of Automata","author":"D. Reidenbach","year":"2011","unstructured":"Reidenbach, D., Schmid, M.L.: A polynomial time match test for large classes of extended regular expressions. In: Domaratzki, M., Salomaa, K. (eds.) CIAA 2010. LNCS, vol.\u00a06482, pp. 241\u2013250. Springer, Heidelberg (2011)"},{"key":"10_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"468","DOI":"10.1007\/978-3-642-28332-1_40","volume-title":"Language and Automata Theory and Applications","author":"D. Reidenbach","year":"2012","unstructured":"Reidenbach, D., Schmid, M.L.: Patterns with bounded treewidth. In: Dediu, A.-H., Mart\u00edn-Vide, C. (eds.) LATA 2012. LNCS, vol.\u00a07183, pp. 468\u2013479. Springer, Heidelberg (2012)"},{"key":"10_CR26","unstructured":"Schmid, M.L.: A note on the complexity of matching patterns with variables. Information Processing Letters (Submitted)"},{"key":"10_CR27","unstructured":"Schmid, M.L.: On the Membership Problem for Pattern Languages and Related Topics. PhD thesis, Department of Computer Science, Loughborough University (2012)"},{"key":"10_CR28","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":"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 1982. LNCS, vol.\u00a0147, pp. 115\u2013127. Springer, Heidelberg (1983)"},{"key":"10_CR29","unstructured":"Shinohara, T.: Polynomial time inference of pattern languages and its application. In: Proc. 7th IBM Symposium on Mathematical Foundations of Computer Science, pp. 191\u2013209 (1982)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38905-4_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T15:15:36Z","timestamp":1578496536000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38905-4_10"}},"subtitle":["(Extended Abstract)"],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642389047","9783642389054"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38905-4_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}