Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Algèbre, Algebra, Algèbre linéaire et multilinéaire, matrices, Linear and multilinear algebra, matrix theory, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Théorie des langages et analyse syntaxique, Language theory and syntactical analysis, Algorithmique, Algorithmics, Algorítmica, Analyse image, Image analysis, Análisis imagen, Application, Aplicación, Apprentissage, Learning, Aprendizaje, Caractérisation, Characterization, Caracterización, Classe langage, Language class, Clase lenguaje, Commande, Control, Connaissance, Knowledge, Conocimiento, Décidabilité, Decidability, Decidibilidad, Fermeture, Closure, Cerradura, Forme normale, Normal form, Forma normal, Grammaire linéaire, Linear grammar, Gramática lineal, Image, Imagen, Inclusion, Inclusión, Informatique, Computer science, Informática, Inférence grammaticale, Grammatical inference, Inferencia gramatical, Inférence, Inference, Inferencia, Intelligence artificielle, Artificial intelligence, Inteligencia artificial, Langage commande, Control language, Lenguaje control, Langage déterministe, Deterministic language, Lenguaje determinista, Langage formel, Formal language, Lenguaje formal, Langage rationnel, Regular language, Lenguaje racional, Modèle, Models, Modelo, Ordinateur, Computer, Computadora, Polynôme, Polynomial, Polinomio, Processus, Process, Proceso, Propriété, Properties, Propiedad, Question documentaire, Query, Pregunta documental, Reconnaissance forme, Pattern recognition, Reconocimiento patrón, Reconnaissance langage, Language recognition, Reconocimiento lenguaje, Relation, Relación, Système apprentissage, Learning systems, Système informatique, Computer system, Sistema informático, Temps polynomial, Polynomial time, Tiempo polinomial, Théorie langage, Language theory, Teoría lenguaje, Grammaire matricielle simple, Simple matrix grammar, Grammaire universelle, and Universal grammar

We show that so-called deterministic even linear simple matrix grammars can be inferred in polynomial time using the query-based learner-teacher model (minimally adequate teacher-learning model) proposed by Angluin (Inform. and Comput. 75 (1987) 87) for learning deterministic regular languages. In this way, we extend the class of efficiently learnable languages beyond both the even linear languages and the even equal matrix languages (Pattern Recognition 21 (1988) 55; Proc. 2nd Internat. Colloq. on Grammatical Inference (ICGI-94): Grammatical Inference and Applications, Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence, vol. 862, Springer, Berlin, 1994, p. 38; Inform. Process. Lett. 28 (1988) 193; Technical Report IIAS-RR-93-6E, Fujitsu Laboratories, 1992; Parallel Image Analysis, ICPIA'92, Lecture Notes in Computer Science, vol. 652, Springer, Berlin, 1992, p. 274; Inform. and Comput. 123 (1995) 138; Algorithmic Learning for Knowledge-Based Systems, Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence, Springer, Berlin, 1995, p. 317). Moreover, we investigate formal language properties of even linear simple matrix languages and related language classes. More precisely, we discuss characterizations, (proper) inclusion relations, closure properties and decidability questions. This way, we also show that, in a certain sense, the idea of iterating the control language approach for learning purposes, as undertook by Takada (1995), could be seen as a special case of using deterministic even linear simple matrix grammars as basic and uniform learning target.