.png){kind=icon}
Return
Learning DFA from simple examples
.png){kind=icon}
OA
AI
DOI：10.1023/A:1010822518073.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Efficient learning of DFA is a challenging research problem in grammatical inference. It is known that both exact and approximate (in the PAC sense) identifiability of DFA is hard. Pitt has posed the following open research problem: Are DFA PAC-identifiable if examples are drawn from the uniform distribution, or some other known simple distribution ? (Pitt, in Lecture Notes in Artificial Intelligence, 397, pp. 18-44, Springer-Verlag, 1989). We demonstrate that the class of DFA whose canonical representations have logarithmic Kolmogorov complexity is efficiently PAC learnable under the Solomonoff Levin universal distribution (m). We prove that the class of DFA is efficiently learnable under the PACS (PAC learning with simple examples) model (Denis, D'Halluin & Gilleron, STACS'96-Proceedings of the 13th Annual Symposium on the Theoretical Aspects of Computer Science, pp. 231-242, 1996) wherein positive and negative examples are sampled according to the universal distribution conditional on a description of the target concept. Further, we show that any concept that is learnable under Gold's model of learning from characteristic samples, Goldman and Mathias' polynomial teachability model, and the model of learning from example based queries is also learnable under the PACS model.
Keywords:
DFA inference
exact identification
characteristic sets
PAC learning
collusion
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
2.9
Papers:
2.7K
Citations:
3.4W
Organization
No organization information available
Cited Papers
No cited papers available