THE QUERY COMPLEXITY OF LEARNING DFA

It is known that the class of deterministic finite automata is polynom ial time learnable by using membership and equivalence queries. We inv estigate the query complexity of learning deterministic finite automat a, i.e., the number of membership and equivalence queries made during the process of learning. We extend a known lower bound on membership q ueries to the case of randomized learning algorithms, and prove lower bounds on the number of alternations between membership and equivalenc e queries. We also show that a trade-off exists, allowing us to reduce the number of equivalence queries at the price of increasing the numb er of membership queries.