The query complexity of learning DFA |
| |
Authors: | José L Balcázar Josep Díaz Ricard Gavaldà Osamu Watanabe |
| |
Affiliation: | 1. Dept. Llenguatges i Sistemes Informàtics, Universitat Politècnica Catalunya, Pau Gargallo 5, 08028, Barcelona, Spain 2. Department of Computer Science, Tokyo Institute of Technology, Meguro-ku, 152, Tokyo, Japan
|
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|