×

Learning regular languages from counterexamples. (English) Zbl 0769.68108

Summary: We study the problem of learning an unknown language given a teacher which can only answer equivalence queries. The teacher presenting a language \(L\) can test (in unit time) whether a conjectured language \(L'\) is equal to \(L\) and, if \(L'\neq L\), provide a counterexample (i.e., a string in the symmetric difference of \(L\) and \(L'\)). It has recently been shown that the family of regular languages and the family of pattern languages are not learnable in polynomial time under this protocol. We consider the learnability of subfamilies of regular languages. It is shown that the problem of learning a subfamily of regular languages can be reduced to the problem of learning its finite members. Using this reduction, we show that the family of \(k\)-bounded regular languages is learnable in polynomial time. We investigate how a partial ordering on counterexamples affects the learnability of the family of regular languages and the family of pattern languages. Two partial orderings are considered: ordering by length and lexicographical ordering. We show that the first ordering on counterexamples does not reduce the complexity of learning the family of regular languages. In contrast, the family of pattern languages is learnable in polynomial time if the teacher always provides counterexamples of minimal length and the family of regular languages is learnable in polynomial time if the teacher always provides the lexicographically first counterexamples.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Angluin, D., Finding patterns common to a set of strings, J. Comput. System Sci., 21, 46-62 (1980) · Zbl 0454.68108
[2] Angluin, D., A note on the number of queries needed to identify regular languages, Inform. and Control, 51, 76-87 (1981) · Zbl 0504.68050
[3] Angluin, D., Types of Queries for Concept Learning, (Technical Report (1986), Yale University, Department of Computer Science), YALEU/DCS/TR-479
[4] Angluin, D., Learning regular sets from queries and counterexamples, Inform. and Comput., 75, 87-106 (1987) · Zbl 0636.68112
[5] Angluin, D., Negative Results for Equivalence Queries, (Technical Report (1988), Yale University, Department of Computer Science), YALEU/DCS/RR-647
[6] Berman, P.; Roos, R., Learning one-counter languages in polynomial time, (Proceedings of the 28th IEEE Annual Symposium on Foundations of Computer Science (1987)), 61-67
[7] Hopcroft, J.; Ullman, J., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0426.68001
[8] Marron, A.; Ko, K., Identification of pattern languages from examples and queries, Inform. and Comput., 74, 91-112 (1987) · Zbl 0635.68096
[9] Marron, A., Learning pattern languages from a single example and from queries, (Proceedings of the 1st Workshop on Computational Learning Theory (1988)), 345-358
[10] Porat, S.; Feldman, J., Learning Automata from Ordered Examples, (Proceedings of the 1st Workshop on Computational Learning Theory. Proceedings of the 1st Workshop on Computational Learning Theory, Technical Report (1988), Rochester University, Computer Science Department), extended abstract · Zbl 0741.68086
[11] Valiant, L., A theory of the learnable, Comm. ACM, 27, 1134-1142 (1984) · Zbl 0587.68077
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.