Strongly Unambiguous Büchi Automata Are Polynomially Predictable With Membership Queries.
Dana AngluinTimos AntonopoulosDana FismanPublished in: CSL (2020)
Keyphrases
- membership queries
- dnf formulas
- concept class
- pac learning
- uniform distribution
- target concept
- learning algorithm
- boolean functions
- exact learning
- regular languages
- equivalence queries
- truth table
- query complexity
- efficient learning
- monotone dnf
- polynomial size
- agnostic learning
- cellular automata
- concept classes
- dnf formulae
- computational learning theory
- term dnf
- monotone dnf formulas
- upper and lower bounds
- learning theory
- read once formulas
- remains np hard
- statistical queries
- finite state machines
- np complete
- upper bound
- randomly chosen
- membership and equivalence queries
- sample complexity
- regular expressions
- conjunctive queries
- special case