Polynomial inference of universal automata from membership and equivalence queries.

Johanna Björklund Henning Fernau Anna Kasprzik

Published in: Inf. Comput. (2016)

Keyphrases

membership and equivalence queries
membership queries
learning algorithm
exact learning
query complexity
efficient learning
turing machine
fixpoint
equivalence queries
dnf formulas
target concept
finite state machines
uniform distribution
concept classes
regular expressions
logic programs
lower bound
pac learning