@inproceedings{10.1007/3-540-57811-0_6,
    Abstract = {We consider the problem of identifying the behavior of an unknown automaton with multiplicity in the field Q of rational numbers (Q-automaton) from multiplicity and equivalence queries. We provide an algorithm which is polynomial in the size of the Q-automaton and of the maximum length of the given counterexamples. As a consequence, we have that Q-automata are PAC-learnable in polynomial time when multiplicity queries are allowed. A corollary of this result is that regular languages are polynomially predictable using membership queries w.r.t. the representation of unambiguous non-deterministic automata. This is important, as there are unambiguous automata such that the equivalent deterministic automaton has an exponentially larger number of states.},
    Address = {Berlin, Heidelberg},
    Author = {Bergadano, F. and Varricchio, S.},
    BookTitle = {Algorithms and Complexity},
    Editor = {Bonuccelli, M. and Crescenzi, P. and Petreschi, R.},
    File = {Learning behaviors of automata from multiplicity and equivalence queries - Bergadano-Varricchio1994\_Chapter\_LearningBehaviorsOfAutomataFro.pdf},
    ISBN = {978-3-540-48337-3},
    Pages = {54--62},
    Publisher = {Springer Berlin Heidelberg},
    Title = {Learning behaviors of automata from multiplicity and equivalence queries},
    Year = {1994},
    date-added = {2022-05-20 10:22:00 +0200},
    date-modified = {2022-05-20 10:22:00 +0200},
    doi = {10.1007/3-540-57811-0_6}
}

@inproceedings{10.1007/3-540-57811-0_6, Abstract = {We consider the problem of identifying the behavior of an unknown automaton with multiplicity in the field Q of rational numbers (Q-automaton) from multiplicity and equivalence queries. We provide an algorithm which is polynomial in the size of the Q-automaton and of the maximum length of the given counterexamples. As a consequence, we have that Q-automata are PAC-learnable in polynomial time when multiplicity queries are allowed. A corollary of this result is that regular languages are polynomially predictable using membership queries w.r.t. the representation of unambiguous non-deterministic automata. This is important, as there are unambiguous automata such that the equivalent deterministic automaton has an exponentially larger number of states.}, Address = {Berlin, Heidelberg}, Author = {Bergadano, F. and Varricchio, S.}, BookTitle = {Algorithms and Complexity}, Editor = {Bonuccelli, M. and Crescenzi, P. and Petreschi, R.}, File = {Learning behaviors of automata from multiplicity and equivalence queries - Bergadano-Varricchio1994_Chapter_LearningBehaviorsOfAutomataFro.pdf}, ISBN = {978-3-540-48337-3}, Pages = {54--62}, Publisher = {Springer Berlin Heidelberg}, Title = {Learning behaviors of automata from multiplicity and equivalence queries}, Year = {1994}, date-added = {2022-05-20 10:22:00 +0200}, date-modified = {2022-05-20 10:22:00 +0200}, doi = {10.1007/3-540-57811-0_6} }