Name
Abstract | ||
|---|---|---|
It is known that the class of deterministic finite automata is polynomial time learnable by using membership and equivalence
queries. We investigate the query complexity of learning deterministic finite automata, i.e., the number of membership and
equivalence queries made during the process of learning. We extend a known lower bound on membership queries to the case of
randomized learning algorithms, and prove lower bounds on the number of alternations between membership and equivalence queries.
We also show that a trade-off exists, allowing us to reduce the number of equivalence queries at the price of increasing the
number of membership queries. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1007/BF03037351 | New Generation Comput. |
Keywords | Field | DocType |
query learning,trade-off,equivalence query,membership query,deterministic finite automata,lower bound,polynomial time | Query learning,Deterministic automaton,Computer science,Upper and lower bounds,Deterministic finite automaton,Theoretical computer science,Finite-state machine,Equivalence (measure theory),Time complexity | Journal |
Volume | Issue | ISSN |
12 | 4 | 1882-7055 |
Citations | PageRank | References |
6 | 0.58 | 9 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| José L. Balcázar | 1 | 701 | 62.06 |
| Josep Díaz | 2 | 20 | 1.80 |
| Ricard Gavaldà | 3 | 1265 | 81.30 |
| Osamu Watanabe | 4 | 960 | 104.55 |