{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,11]],"date-time":"2024-09-11T06:57:17Z","timestamp":1726037837144},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030248857"},{"type":"electronic","value":"9783030248864"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"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":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-24886-4_11","type":"book-chapter","created":{"date-parts":[[2019,7,23]],"date-time":"2019-07-23T19:02:56Z","timestamp":1563908576000},"page":"154-167","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Teaching Complexity of Erasing Pattern Languages with Bounded Variable Frequency"],"prefix":"10.1007","author":[{"given":"Ziyuan","family":"Gao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,7,10]]},"reference":[{"key":"11_CR1","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/B978-0-444-88071-0.50010-2","volume-title":"Algorithms and Complexity","author":"Alfred V. AHO","year":"1990","unstructured":"Aho, A.V.: Algorithms for finding patterns in strings. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science. Algorithms and Complexity, vol. A, chap. 5, pp. 257\u2013300. MIT Press, Oxford (1990)"},{"issue":"3","key":"11_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. J. Disc. Algorithms 5(3), 514\u2013523 (2007)","journal-title":"J. Disc. Algorithms"},{"key":"11_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, 46\u201362 (1980)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"11_CR4","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/S0019-9958(80)90285-5","volume":"45","author":"D Angluin","year":"1980","unstructured":"Angluin, D.: Inductive inference of formal languages from positive data. Inf. Control 45(2), 117\u2013135 (1980)","journal-title":"Inf. Control"},{"key":"11_CR5","first-page":"1513","volume":"14","author":"D Angluin","year":"2013","unstructured":"Angluin, D., Aspnes, J., Eisenstat, S., Kontorovich, A.: On the learnability of shuffle ideals. J. Mach. Learn. Res. 14, 1513\u20131531 (2013)","journal-title":"J. Mach. Learn. Res."},{"issue":"1","key":"11_CR6","doi-asserted-by":"publisher","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(1), 28\u201342 (1996)","journal-title":"J. Comput. Syst. Sci."},{"key":"11_CR7","unstructured":"Bayeh, F., Gao, Z., Zilles, S.: Erasing pattern languages distinguishable by a finite number of strings. In: ALT, pp. 72\u2013108 (2017)"},{"issue":"6","key":"11_CR8","doi-asserted-by":"publisher","first-page":"1007","DOI":"10.1142\/S012905410300214X","volume":"14","author":"C Campeanu","year":"2003","unstructured":"Campeanu, C., Salomaa, K., Yu, S.: A formal study of practical regular expressions. Int. J. Found. Comput. Sci. 14(6), 1007\u20131018 (2003)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"11_CR9","unstructured":"Day, J.D., Fleischmann, P., Manea, F., Nowotka, D.: Local patterns. In: FSTTCS, pp. 24:1\u201324:14 (2017)"},{"key":"11_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/978-3-319-98654-8_22","volume-title":"Developments in Language Theory","author":"JD Day","year":"2018","unstructured":"Day, J.D., Fleischmann, P., Manea, F., Nowotka, D., Schmid, M.L.: On matching generalised repetitive patterns. In: Hoshi, M., Seki, S. (eds.) DLT 2018. LNCS, vol. 11088, pp. 269\u2013281. Springer, Cham (2018). \n                      https:\/\/doi.org\/10.1007\/978-3-319-98654-8_22"},{"key":"11_CR11","unstructured":"Fernau, H., Manea, F., Mercas, R., Schmid, M.L.: Pattern matching with variables: fast algorithms and new hardness results. In: STACS, pp. 302\u2013315 (2015)"},{"key":"11_CR12","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/j.ic.2015.03.006","volume":"242","author":"H Fernau","year":"2015","unstructured":"Fernau, H., Schmid, M.L.: Pattern matching with variables: a multivariate complexity analysis. Inf. Comput. 242, 287\u2013305 (2015)","journal-title":"Inf. Comput."},{"key":"11_CR13","unstructured":"Freydenberger, D.D., Schmid, M.L.: Deterministic regular expressions with back-references. In: STACS, pp. 33:1\u201333:14 (2017)"},{"key":"11_CR14","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1016\/S0019-9958(67)91165-5","volume":"10","author":"EM Gold","year":"1967","unstructured":"Gold, E.M.: Language identification in the limit. Inf. Control 10, 447\u2013474 (1967)","journal-title":"Inf. Control"},{"key":"11_CR15","first-page":"1","volume":"18","author":"Z Gao","year":"2017","unstructured":"Gao, Z., Ries, C., Simon, H.U., Zilles, S.: Preference-based teaching. J. Mach. Learn. Res. 18, 1\u201332 (2017)","journal-title":"J. Mach. Learn. Res."},{"key":"11_CR16","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1006\/jcss.1995.1003","volume":"50","author":"SA Goldman","year":"1995","unstructured":"Goldman, S.A., Kearns, M.J.: On the complexity of teaching. J. Comput. Syst. Sci 50, 20\u201331 (1995)","journal-title":"J. Comput. Syst. Sci"},{"issue":"24","key":"11_CR17","doi-asserted-by":"publisher","first-page":"1114","DOI":"10.1016\/j.ipl.2010.09.010","volume":"110","author":"S Jain","year":"2010","unstructured":"Jain, S., Ong, Y.S., Stephan, F.: Regular patterns, regular languages and context-free languages. Inf. Proc. Lett. 110(24), 1114\u20131119 (2010)","journal-title":"Inf. Proc. Lett."},{"key":"11_CR18","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, 147\u2013163 (1994)","journal-title":"Int. J. Comput. Math."},{"key":"11_CR19","doi-asserted-by":"crossref","unstructured":"Lothaire, M.: Combinatorics on Words, Cambridge Mathematical Library. Cambridge University Press, Cambridge (1997). Corrected reprint of the 1983 original","DOI":"10.1017\/CBO9780511566097"},{"key":"11_CR20","series-title":"Encyclopedia of Mathematics and its Applications","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107326019","volume-title":"Algebraic Combinatorics on Words","author":"M Lothaire","year":"2002","unstructured":"Lothaire, M.: Algebraic Combinatorics on Words. Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge (2002)"},{"key":"11_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/3-540-62685-9_16","volume-title":"Computational Learning Theory","author":"S Matsumoto","year":"1997","unstructured":"Matsumoto, S., Shinohara, A.: Learning pattern languages using queries. In: Ben-David, S. (ed.) EuroCOLT 1997. LNCS, vol. 1208, pp. 185\u2013197. Springer, Heidelberg (1997). \n                      https:\/\/doi.org\/10.1007\/3-540-62685-9_16"},{"key":"11_CR22","doi-asserted-by":"crossref","unstructured":"Mitchell, A.R.: Learnability of a subclass of extended pattern languages. In: COLT, pp. 64\u201371 (1998)","DOI":"10.1145\/279943.279955"},{"issue":"1\u20132","key":"11_CR23","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. Theor. Comput. Sci 186(1\u20132), 231\u2013248 (1997)","journal-title":"Theor. Comput. Sci"},{"issue":"1","key":"11_CR24","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"},{"key":"11_CR25","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, 166\u2013193 (2008)","journal-title":"Theor. Comput. Sci"},{"key":"11_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ic.2016.02.003","volume":"249","author":"ML Schmid","year":"2016","unstructured":"Schmid, M.L.: Characterising REGEX languages by regular languages equipped with factor-referencing. Inf. Comput. 249, 1\u201317 (2016)","journal-title":"Inf. Comput."},{"issue":"4","key":"11_CR27","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/BF03037091","volume":"8","author":"A Shinohara","year":"1991","unstructured":"Shinohara, A., Miyano, S.: Teachability in computational learning. New Gener. Comput. 8(4), 337\u2013347 (1991)","journal-title":"New Gener. Comput."},{"key":"11_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 Symposia 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 Symposia on Software Science and Engineering. LNCS, vol. 147, pp. 115\u2013127. Springer, Heidelberg (1983). \n                      https:\/\/doi.org\/10.1007\/3-540-11980-9_19"},{"key":"11_CR29","unstructured":"Zhu, X., Singla, A., Zilles, S., Rafferty, A.N.: An overview of machine teaching (2018, manuscript). \n                      http:\/\/arxiv.org\/abs\/1801.05927"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-24886-4_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,23]],"date-time":"2019-07-23T19:04:16Z","timestamp":1563908656000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-24886-4_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030248857","9783030248864"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-24886-4_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"10 July 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"DLT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Developments in Language Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Warsaw","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 August 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 August 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"dlt2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/dlt2019.mimuw.edu.pl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"20","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"67% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}