The Query complexity of learning context-free grammars
| Autor: | Domingo Soriano, Carlos, Lavín Puente, Víctor Angel |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 1994 |
| Předmět: | |
| Zdroj: | Recercat. Dipósit de la Recerca de Catalunya instname UPCommons. Portal del coneixement obert de la UPC Universitat Politècnica de Catalunya (UPC) |
| Popis: | In the COLT'94 Conference A. Burago showed that the class of structurally reversible grammars is learnable in polynomial time using membership and equivalence queries. The paper shows that this class of grammars is not learnable using either membership alone or equivalence alone. However, it turns out that structurally reversible grammars are a superclass of very simple grammars which are learnable using only equivalence queries. Furthermore, we prove that the number of alternations between equivalence and membership queries cannot be constant. We also prove a lower bound in the number of alternations between membership and equivalence queries which is an improvement with respect to the same lower bound for deterministic finite automata. Finally, we discuss a possible trade-off between membership and equivalence queries in Burago's algorithm that might allow us to reduce the number of equivalence queries. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|