{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T04:26:56Z","timestamp":1778732816491,"version":"3.51.4"},"reference-count":39,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2001,6,1]],"date-time":"2001-06-01T00:00:00Z","timestamp":991353600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2001,6,1]],"date-time":"2001-06-01T00:00:00Z","timestamp":991353600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4429,"URL":"http:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2001,6]]},"DOI":"10.1016\/s0304-3975(00)00136-5","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T14:37:27Z","timestamp":1027607847000},"page":"119-156","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":21,"title":["Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries"],"prefix":"10.1016","volume":"261","author":[{"given":"Thomas","family":"Erlebach","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Rossmanith","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hans","family":"Stadtherr","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Angelika","family":"Steger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Zeugmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"issue":"5","key":"10.1016\/S0304-3975(00)00136-5_BIB1","doi-asserted-by":"crossref","first-page":"808","DOI":"10.1137\/0216053","article-title":"Deterministic simulation of idealized parallel computers on more realistic ones","volume":"16","author":"Alt","year":"1987","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10.1016\/S0304-3975(00)00136-5_BIB2","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1016\/0022-0000(80)90041-0","article-title":"Finding patterns common to a set of strings","volume":"21","author":"Angluin","year":"1980","journal-title":"J. Comput. Systems Sci."},{"key":"10.1016\/S0304-3975(00)00136-5_BIB3","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/S0019-9958(80)90285-5","article-title":"Inductive inference of formal languages from positive data","volume":"45","author":"Angluin","year":"1980","journal-title":"Inform. and Control"},{"key":"10.1016\/S0304-3975(00)00136-5_BIB4","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1023\/A:1022821128753","article-title":"Queries and concept learning","volume":"2","author":"Angluin","year":"1988","journal-title":"Mach. Learning"},{"issue":"2","key":"10.1016\/S0304-3975(00)00136-5_BIB5","doi-asserted-by":"crossref","first-page":"261","DOI":"10.2140\/pjm.1979.85.261","article-title":"Avoidable patterns in strings of symbols","volume":"85","author":"Bean","year":"1979","journal-title":"Pacific J. Math."},{"key":"10.1016\/S0304-3975(00)00136-5_BIB6","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/S0019-9958(86)80042-0","article-title":"On the complexity of inductive inference","volume":"69","author":"Daley","year":"1986","journal-title":"Inform. and Control"},{"key":"10.1016\/S0304-3975(00)00136-5_BIB7","first-page":"184","article-title":"The relation of two patterns with comparable languages","volume":"vol. 294","author":"Fil\u00e9","year":"1988"},{"key":"10.1016\/S0304-3975(00)00136-5_BIB8","series-title":"Parallelism in random access machines, Proc. 10th Ann. ACM Symp. on Theory of Computing","first-page":"114","author":"Fortune","year":"1978"},{"key":"10.1016\/S0304-3975(00)00136-5_BIB9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0890-5401(90)90042-G","article-title":"Prudence and other restrictions in formal language learning","volume":"85","author":"Fulk","year":"1990","journal-title":"Inform. and Comput."},{"key":"10.1016\/S0304-3975(00)00136-5_BIB10","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1016\/S0019-9958(67)91165-5","article-title":"Language identification in the limit","volume":"10","author":"Gold","year":"1967","journal-title":"Inform. and Control"},{"key":"10.1016\/S0304-3975(00)00136-5_BIB11","series-title":"Formal Languages and their Relation to Automata","author":"Hopcroft","year":"1969"},{"key":"10.1016\/S0304-3975(00)00136-5_BIB12","series-title":"An Introduction to Parallel Algorithms","author":"J\u00e1J\u00e1","year":"1992"},{"key":"10.1016\/S0304-3975(00)00136-5_BIB13","first-page":"314","article-title":"Polynomial time inference of general pattern languages","volume":"Vol 166","author":"Jantke","year":"1984"},{"key":"10.1016\/S0304-3975(00)00136-5_BIB14","first-page":"161","article-title":"Monotonic and nonmonotonic inductive inference of functions and patterns","volume":"vol. 543","author":"Jantke","year":"1991"},{"key":"10.1016\/S0304-3975(00)00136-5_BIB15","first-page":"301","article-title":"Inclusion is undecidable for pattern languages","volume":"vol. 700","author":"Jiang","year":"1993"},{"key":"10.1016\/S0304-3975(00)00136-5_BIB16","series-title":"Efficient PRAM simulation on a distributed memory machine, Proc. 24th Ann. ACM Symp. on Theory of Computing","first-page":"318","author":"Karp","year":"1992"},{"key":"10.1016\/S0304-3975(00)00136-5_BIB17","series-title":"A polynomial-time algorithm for learning k-variable pattern languages from examples, Proc. 2nd Ann. Workshop on Computational Learning Theory","first-page":"57","author":"Kearns","year":"1989"},{"issue":"1","key":"10.1016\/S0304-3975(00)00136-5_BIB18","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0022-0000(87)90006-7","article-title":"A note on the two-variable pattern-finding problem","volume":"34","author":"Ko","year":"1987","journal-title":"J. Comput. Systems Sci."},{"key":"10.1016\/S0304-3975(00)00136-5_BIB19","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/BF03037093","article-title":"Polynomial-time inference of arbitrary pattern languages","volume":"8","author":"Lange","year":"1991","journal-title":"New Generation Comput."},{"issue":"6","key":"10.1016\/S0304-3975(00)00136-5_BIB20","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1007\/BF01301967","article-title":"Set-driven and rearrangement-independent learning of recursive languages","volume":"29","author":"Lange","year":"1996","journal-title":"Math. Systems Theory"},{"key":"10.1016\/S0304-3975(00)00136-5_BIB21","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0890-5401(87)90026-5","article-title":"Identification of pattern languages from examples and queries","volume":"74","author":"Marron","year":"1987","journal-title":"Inform. and Comput."},{"key":"10.1016\/S0304-3975(00)00136-5_BIB22","unstructured":"A. Mitchell, A. Sharma, T. Scheffer, Language identification for tourists on polynomially bounded holidays, unpublished manuscript."},{"key":"10.1016\/S0304-3975(00)00136-5_BIB23","series-title":"Editing by examples, Tech. Rep. 280, Department of Computer Science","author":"Nix","year":"1983"},{"key":"10.1016\/S0304-3975(00)00136-5_BIB24","series-title":"Systems that Learn: An Introduction to Learning Theory for Cognitive and Computer Scientists","author":"Osherson","year":"1986"},{"key":"10.1016\/S0304-3975(00)00136-5_BIB25","first-page":"18","article-title":"Inductive inference, DFAs and computational complexity","volume":"vol. 397","author":"Pitt","year":"1989"},{"key":"10.1016\/S0304-3975(00)00136-5_BIB26","first-page":"46","article-title":"Patterns (The Formal Language Theory Column)","volume":"54","author":"Salomaa","year":"1994","journal-title":"EATCS Bull."},{"key":"10.1016\/S0304-3975(00)00136-5_BIB27","first-page":"144","article-title":"Return to patterns (The Formal Language Theory Column)","volume":"55","author":"Salomaa","year":"1994","journal-title":"EATCS Bull."},{"key":"10.1016\/S0304-3975(00)00136-5_BIB28","unstructured":"G. Sch\u00e4fer-Richter, \u00dcber Eingabeabh\u00e4ngigkeit und Komplexit\u00e4t von Inferenzstrategien, Rheinisch Westf\u00e4lische Technische Hochschule Aachen, Dissertation, 1984."},{"key":"10.1016\/S0304-3975(00)00136-5_BIB29","unstructured":"T. Shinohara, Polynomial time inference of pattern languages and its applications, Proc. 7th IBM Symp. on Mathematical Foundations of Computer Science (1982) 191\u2013209."},{"key":"10.1016\/S0304-3975(00)00136-5_BIB30","first-page":"115","article-title":"Polynomial time inference of extended regular pattern languages","volume":"vol. 147","author":"Shinohara","year":"1983"},{"key":"10.1016\/S0304-3975(00)00136-5_BIB31","first-page":"259","article-title":"Pattern inference","volume":"vol. 961","author":"Shinohara","year":"1995"},{"key":"10.1016\/S0304-3975(00)00136-5_BIB32","first-page":"256","article-title":"Inductive inference of unbounded unions of pattern languages from positive data","volume":"vol. 1160","author":"Shinohara","year":"1996"},{"key":"10.1016\/S0304-3975(00)00136-5_BIB33","first-page":"1","article-title":"\u00dcber unendliche Zeichenreihen","volume":"7","author":"Thue","year":"1906","journal-title":"Norske Vid. Selsk. Skr. I. Mat. Nat. Kl., Christiana"},{"issue":"11","key":"10.1016\/S0304-3975(00)00136-5_BIB34","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","article-title":"A theory of the learnable","volume":"27","author":"Valiant","year":"1984","journal-title":"Comm. ACM"},{"key":"10.1016\/S0304-3975(00)00136-5_BIB35","series-title":"Formal Principles of Language Acquisition","author":"Wexler","year":"1980"},{"issue":"1","key":"10.1016\/S0304-3975(00)00136-5_BIB36","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1080\/09528139408953785","article-title":"Ignoring data may be the only way to learn efficiently","volume":"6","author":"Wiehagen","year":"1994","journal-title":"J. Experimental Theoret. Artificial Intelligence"},{"key":"10.1016\/S0304-3975(00)00136-5_BIB37","unstructured":"T. Zeugmann, Parallel algorithms, in: A. Kent, J.G. Williams (Eds.), Encyclopedia of Computer Science and Technology, vol. 21, Suppl. 6, Marcel Dekker, New York, 1990, 223\u2013244."},{"issue":"1, 2","key":"10.1016\/S0304-3975(00)00136-5_BIB38","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1023\/A:1018964207937","article-title":"Lange and Wiehagen's pattern language learning algorithm","volume":"23","author":"Zeugmann","year":"1998","journal-title":"Ann. Math. Artificial Intelligence"},{"key":"10.1016\/S0304-3975(00)00136-5_BIB39","first-page":"190","article-title":"A guided tour across the boundaries of learning recursive languages","volume":"vol. 961","author":"Zeugmann","year":"1995"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397500001365?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397500001365?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T00:52:09Z","timestamp":1759625529000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397500001365"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,6]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2001,6]]}},"alternative-id":["S0304397500001365"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(00)00136-5","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2001,6]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries","name":"articletitle","label":"Article Title"},{"value":"Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/S0304-3975(00)00136-5","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"converted-article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 2001 Elsevier Science B.V. All rights reserved.","name":"copyright","label":"Copyright"}]}}