{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T14:47:08Z","timestamp":1770475628078,"version":"3.49.0"},"reference-count":67,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2002,10,1]],"date-time":"2002-10-01T00:00:00Z","timestamp":1033430400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":3942,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2002,10]]},"DOI":"10.1016\/s0304-3975(01)00313-9","type":"journal-article","created":{"date-parts":[[2002,10,7]],"date-time":"2002-10-07T20:25:18Z","timestamp":1034022318000},"page":"425-456","source":"Crossref","is-referenced-by-count":13,"title":["Even linear simple matrix languages: formal language properties and grammatical inference"],"prefix":"10.1016","volume":"289","author":[{"given":"Henning","family":"Fernau","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(01)00313-9_BIB1","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/S0019-9958(64)90294-3","article-title":"On a family of linear grammars","volume":"7","author":"Amar","year":"1964","journal-title":"Inform. and Control"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB2","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/S0019-9958(65)90275-5","article-title":"Generalizations of regular events","volume":"8","author":"Amar","year":"1965","journal-title":"Inform. and Control"},{"issue":"3","key":"10.1016\/S0304-3975(01)00313-9_BIB3","doi-asserted-by":"crossref","first-page":"741","DOI":"10.1145\/322326.322334","article-title":"Inference of reversible languages","volume":"29","author":"Angluin","year":"1982","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB4","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0890-5401(87)90052-6","article-title":"Learning regular sets from queries and counterexamples","volume":"75","author":"Angluin","year":"1987","journal-title":"Inform. and Comput."},{"key":"10.1016\/S0304-3975(01)00313-9_BIB5","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BF00116034","article-title":"Negative results for equivalence queries","volume":"5","author":"Angluin","year":"1990","journal-title":"Mach. Learning"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB6","doi-asserted-by":"crossref","unstructured":"D. Angluin, M. Kharitonov, When won't membership queries help? in: Proc. 23rd ACM Symp. on Theory of Computing STOC, ACM Press, New York, 1991, pp. 444\u2013454.","DOI":"10.1145\/103418.103420"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB7","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/BF03037351","article-title":"The query complexity of learning DFA","volume":"12","author":"Balc\u00e1zar","year":"1994","journal-title":"New Generation Comput."},{"issue":"3","key":"10.1016\/S0304-3975(01)00313-9_BIB8","first-page":"97","article-title":"An optimal parallel algorithm for learning DFA","volume":"2","author":"Balc\u00e1zar","year":"1996","journal-title":"J. Universal Comput. Sci."},{"key":"10.1016\/S0304-3975(01)00313-9_BIB9","series-title":"Proc. 2nd European Conf. Computational Learning Theory EUROCOLT\u201995","first-page":"380","article-title":"Learning behaviors of automata from shortest counterexamples","volume":"vol. 904","author":"Bergadano","year":"1995"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB10","doi-asserted-by":"crossref","unstructured":"P. Berman, R. Roos, Learning one-counter languages in polynomial time. in: Proc. 28th Symp. on Foundations of Computer Science FOCS\u201987, IEEE Press, New York, 1987, pp. 61\u201367.","DOI":"10.1109\/SFCS.1987.36"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB11","series-title":"Transductions and Context-Free Languages","volume":"vol. 38","author":"Berstel","year":"1979"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB12","unstructured":"A. Birkendorf, A. B\u00f6ker, H.U. Simon, Learning deterministic finite automata from smallest counterexamples, in: Proc. 9th Annu. ACM\/SIAM Symp. on Discrete Algorithms SODA\u201998, ACM Press, New York, 1998, pp. 599\u2013608."},{"key":"10.1016\/S0304-3975(01)00313-9_BIB13","series-title":"Automata, Languages and Programming ICALP\u201978","first-page":"113","article-title":"Comparisons and reset machines","volume":"vol. 62","author":"Book","year":"1978"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB14","series-title":"Proc. 2nd Symp. on Theoretical Aspects of Computer Science STACS\u201985","first-page":"71","article-title":"Non-deterministic two-tape automata are more powerful than deterministic ones","volume":"vol. 182","author":"Brauer","year":"1985"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB15","doi-asserted-by":"crossref","unstructured":"J.A. Brzozowski, Regular-like expressions for some irregular languages, in: IEEE Conf. Record 9th Annu. Symp. on Switching and Automata Theory SWAT, IEEE Press, New York, 1968, pp. 278\u2013280.","DOI":"10.1109\/SWAT.1968.24"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB16","doi-asserted-by":"crossref","unstructured":"N.H. Bshouty, R. Cleve, On the exact learning of formulae in parallel. in: 33rd Symp. on Foundations of Computer Science FOCS\u201992, IEEE Press, New York, 1992, pp. 513\u2013522.","DOI":"10.1109\/SFCS.1992.267800"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB17","doi-asserted-by":"crossref","unstructured":"N.H. Bshouty, S.A. Goldman, T.R. Hancock, S. Matar, Asking queries to minimize errors, in: Proc. 6th Annu. ACM Conf. on Computational Learning Theory COLT\u201993, ACM Press, New York, 1993, pp. 41\u201350.","DOI":"10.1145\/168304.168310"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB18","series-title":"Regulated Rewriting in Formal Language Theory","volume":"vol. 18","author":"Dassow","year":"1989"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB19","series-title":"Comput. Combin. 5th Annu. Internat. Conf. COCOON\u201999","first-page":"221","article-title":"Efficient learning of some linear matrix languages","volume":"vol. 1627","author":"Fernau","year":"1999"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB20","series-title":"Discrete Mathematics and Theoretical Computer Science DMTCS 2001","first-page":"81","article-title":"Even linear simple matrix languages: formal language aspects","author":"Fernau","year":"2001"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB21","series-title":"Grammatical Inference: Algorithms Appl., 5th Internat. Colloq. (ICGI 2000)","first-page":"75","article-title":"Permutations and control sets for learning non-regular language families","volume":"Vol. 1891","author":"Fernau","year":"2000"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB22","doi-asserted-by":"crossref","first-page":"920","DOI":"10.1109\/34.57687","article-title":"Inference of k-testable languages in the strict sense and applications to syntactic pattern recognition","volume":"12","author":"Garc\u0131\u0301a","year":"1990","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"3","key":"10.1016\/S0304-3975(01)00313-9_BIB23","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1137\/0304034","article-title":"Finite-turn pushdown automata","volume":"4","author":"Ginsburg","year":"1966","journal-title":"SIAM J. Control"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB24","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/BF01692513","article-title":"Control sets on grammars","volume":"2","author":"Ginsburg","year":"1968","journal-title":"Math. Systems Theory"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB25","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(01)00313-9_BIB26","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/S0019-9958(78)90799-4","article-title":"Comments on universal and left universal grammars, context-sensitive languages, and context-free grammar forms","volume":"39","author":"Greibach","year":"1978","journal-title":"Inform. and Control"},{"issue":"2","key":"10.1016\/S0304-3975(01)00313-9_BIB27","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0304-3975(78)90035-X","article-title":"One way finite visit automata","volume":"6","author":"Greibach","year":"1978","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(01)00313-9_BIB28","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1016\/S0019-9958(81)90170-4","article-title":"Left universal context-free grammars and homomorphic characterizations of languages","volume":"50","author":"Hirose","year":"1981","journal-title":"Inform. and Control"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB29","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/S0019-9958(70)80034-1","article-title":"Simple matrix languages","volume":"17","author":"Ibarra","year":"1970","journal-title":"Inform. and Control"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB30","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/0022-0000(91)90016-X","article-title":"Learning regular languages from counterexamples","volume":"43","author":"Ibarra","year":"1991","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(01)00313-9_BIB31","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1016\/S0019-9958(75)90216-8","article-title":"A universal context-free grammar","volume":"28","author":"Kasai","year":"1975","journal-title":"Inform. and Control"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB32","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1016\/S0022-0000(74)80052-8","article-title":"A geometric hierarchy of languages","volume":"8","author":"Khabbaz","year":"1974","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(01)00313-9_BIB33","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1016\/S0019-9958(74)90864-X","article-title":"Control sets on linear grammars","volume":"25","author":"Khabbaz","year":"1974","journal-title":"Inform. and Control"},{"issue":"1","key":"10.1016\/S0304-3975(01)00313-9_BIB34","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/S0304-3975(97)00016-9","article-title":"Learning deterministic even linear languages from positive examples","volume":"185","author":"Koshiba","year":"1997","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(01)00313-9_BIB35","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/S0019-9958(70)90105-1","article-title":"On the entropy of context-free languages","volume":"16","author":"Kuich","year":"1970","journal-title":"Inform. and Control"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB36","doi-asserted-by":"crossref","first-page":"175","DOI":"10.3233\/FI-1996-25203","article-title":"A note on the grammatical inference problem for even linear languages","volume":"25","author":"M\u00e4kinen","year":"1996","journal-title":"Fund. Inform."},{"key":"10.1016\/S0304-3975(01)00313-9_BIB37","first-page":"461","article-title":"Natural language understanding: a new challenge for grammar systems","volume":"12","author":"Mart\u0131\u0301n-Vide","year":"1996","journal-title":"Acta Cybernet."},{"key":"10.1016\/S0304-3975(01)00313-9_BIB38","first-page":"45","article-title":"Special families of matrix languages and decidable problems","volume":"10","author":"Mateescu","year":"1991","journal-title":"Acta Cybernet."},{"key":"10.1016\/S0304-3975(01)00313-9_BIB39","unstructured":"H. Maurer, W. Kuich, Tuple languages, Proc. ACM Internat. Computing Symposium, 1970, pp. 882\u2013891."},{"key":"10.1016\/S0304-3975(01)00313-9_BIB40","first-page":"333","article-title":"On simple matrix grammars","volume":"20","author":"Pascu","year":"1976","journal-title":"Bull. Math. Soc. Sci. Math. Roumanie"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB41","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/S0019-9958(77)90169-3","article-title":"A homomorphic representation of simple matrix languages","volume":"35","author":"Pascu","year":"1977","journal-title":"Inform. and Control"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB42","first-page":"377","article-title":"Linear simple matrix languages","volume":"14","author":"P\u0103un","year":"1978","journal-title":"Elektronische Informationsverarbeitung und Kybernetik (EIK)"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB43","first-page":"143","article-title":"On a family of linearly grammatizable languages","volume":"10","author":"P\u0103un","year":"1987","journal-title":"Fund. Inform."},{"key":"10.1016\/S0304-3975(01)00313-9_BIB44","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/0031-3203(88)90071-4","article-title":"Inference of even linear grammars and its application to picture description languages","volume":"21","author":"Radhakrishnan","year":"1988","journal-title":"Pattern Recognition"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB45","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1006\/inco.1993.1021","article-title":"Inference on finite automata using homing sequences","volume":"103","author":"Rivest","year":"1993","journal-title":"Inform. and Comput."},{"key":"10.1016\/S0304-3975(01)00313-9_BIB46","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1007\/BF01762185","article-title":"Image theorems for simple matrix languages and n-parallel languages","volume":"8","author":"Rosebrugh","year":"1974","journal-title":"Math. Systems Theory"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB47","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/S0019-9958(67)80006-8","article-title":"A machine realization of the linear context-free languages","volume":"10","author":"Rosenberg","year":"1967","journal-title":"Inform. and Control."},{"key":"10.1016\/S0304-3975(01)00313-9_BIB48","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1016\/S0019-9958(77)80014-4","article-title":"A note on universal grammars","volume":"34","author":"Rozenberg","year":"1977","journal-title":"Inform. and Control"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB49","series-title":"Handbook of Formal Languages, vol. I","author":"Rozenberg","year":"1997"},{"issue":"2","key":"10.1016\/S0304-3975(01)00313-9_BIB50","first-page":"492","article-title":"Regularity of languages k-linear for various k","volume":"15","author":"Semenov","year":"1974","journal-title":"Soviet Math. Dokl."},{"key":"10.1016\/S0304-3975(01)00313-9_BIB51","series-title":"Proc. 2nd Internat. Colloq. on Grammatical Inference (ICGI-94): Grammatical Inference and Applications","first-page":"38","article-title":"A characterization of even linear languages and its application to the learning problem","volume":"vol. 862","author":"Sempere","year":"1994"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB52","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/BF00630917","article-title":"Evidence against the context-freeness of natural languages","volume":"8","author":"Shieber","year":"1985","journal-title":"Linguist. Philos."},{"key":"10.1016\/S0304-3975(01)00313-9_BIB53","first-page":"133","article-title":"On equal matrix languages","volume":"14","author":"Siromoney","year":"1969","journal-title":"Informat. and Control"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB54","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0019-9958(72)90233-1","article-title":"Unambiguous equal matrix languages","volume":"20","author":"Siromoney","year":"1972","journal-title":"Inform. and Control"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB55","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0020-0190(88)90208-6","article-title":"Grammatical inference of even linear languages based on control sets","volume":"28","author":"Takada","year":"1988","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0304-3975(01)00313-9_BIB56","unstructured":"Y. Takada, Algorithmic learning theory of formal languages and its applications, Technical Report IIAS-RR-93-6E, IIAS-SIS: International Institute for Advanced Study of Social Information Sciences, Fujitsu Laboratories, 1992. (Also Ph.D. Thesis.)"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB57","series-title":"Parallel Image Analysis, ICPIA\u201992","first-page":"274","article-title":"Learning even equal matrix languages based on control sets","volume":"Vol. 652","author":"Takada","year":"1992"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB58","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0304-3975(92)90123-W","article-title":"Learning semilinear sets from examples and via queries","volume":"104","author":"Takada","year":"1992","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(01)00313-9_BIB59","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1006\/inco.1995.1163","article-title":"A hierarchy of language families learnable by regular language learning","volume":"123","author":"Takada","year":"1995","journal-title":"Inform. and Comput."},{"key":"10.1016\/S0304-3975(01)00313-9_BIB60","series-title":"Algorithmic Learning for Knowledge-Based Systems","first-page":"317","article-title":"Learning formal languages based on control sets","author":"Takada","year":"1995"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB61","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0020-0190(86)90114-6","article-title":"On the intersection of the class of linear context-free languages and the class of single-reset languages","volume":"23","author":"Wagner","year":"1986","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0304-3975(01)00313-9_BIB62","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0304-3975(92)90124-X","article-title":"A geometric hierarchy beyond context-free languages","volume":"104","author":"Weir","year":"1992","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(01)00313-9_BIB63","first-page":"403","article-title":"n-linear simple matrix languages and n-parallel linear languages","volume":"22","author":"Wood","year":"1977","journal-title":"Rev. Roumaine Math. Pures Appl."},{"key":"10.1016\/S0304-3975(01)00313-9_BIB64","first-page":"122","article-title":"The decidability of equivalence for a family of linear grammars","volume":"47","author":"Yehudai","year":"1980","journal-title":"Inform. and Comput."},{"key":"10.1016\/S0304-3975(01)00313-9_BIB65","series-title":"Proc. 3rd Workshop on Algorithmic Learning Theory, ALT \u201992","first-page":"41","article-title":"On learning systolic languages","volume":"vol. 743","author":"Yokomori","year":"1992"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB66","series-title":"Machine Intelligence 13: Machine Intelligence and Inductive Learning, vol. 13","article-title":"Learning non-deterministic finite automata from queries and counterexamples","author":"Yokomori","year":"1994"},{"key":"10.1016\/S0304-3975(01)00313-9_BIB67","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/BF01201279","article-title":"Learning two-tape automata from queries and counterexamples","volume":"29","author":"Yokomori","year":"1996","journal-title":"Math. Systems Theory"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397501003139?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397501003139?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T17:55:49Z","timestamp":1583776549000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397501003139"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,10]]},"references-count":67,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2002,10]]}},"alternative-id":["S0304397501003139"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(01)00313-9","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2002,10]]}}}