Some of my references are below. These are mostly online, but the first one from Pitt is behind a paywall and I couldn't find a free version of it, unfortunately. Email me if you need clarifications.

Dana Angluin, Inductive inference of formal languages from positive data. [http://www-personal.umich.edu/~yinw/papers/Angluin80.pdf]

Dana Angluin, Learning regular sets from queries and counterexamples. [https://people.eecs.berkeley.edu/~dawnsong/teaching/s10/pape...]

Mark E. Gold, Complexity of automaton identification from given data. [http://sebastian.doc.gold.ac.uk/papers/Language_Learning/gol...]

Mark E. Gold, Language Identification in the Limit.[http://web.mit.edu/6.863/www/spring2010/readings/gold67limit...]

Pitt, L., & Pitt, L. (1989). Inductive Inference, DFAs and Computational Complexity. 2ND INT. WORKSHOP ON ANALOGICAL AND INDUCTIVE INFERENCE (AII, 18--44. Retrieved from http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.187....

Leonard Pitt & Manfred K. Warmuth. The minimum consistent DFA problem cannot be approximated within any polynomial. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86....]

Also see below for a gentle introduction to PAC-Learning, which actually allows for learning several concepts in restricted (but non-trivial) settings:

http://web.cs.iastate.edu/~honavar/pac.pdf

There is a lot more bibliography on both Inductive Inference tractability and PAC-Learnability. You'll have to follow the trail of references :)