Name
Abstract | ||
|---|---|---|
In the last COLT 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 disccus a possible trade-off between membership and equivalence queries in Burago's algorithm that might allow us to reduce the number of equivalence queries. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1007/3-540-59119-2_195 | EuroCOLT |
Keywords | Field | DocType |
query complexity,context-free grammar,context free grammar,deterministic finite automata,lower bound,polynomial time | Deterministic context-free grammar,Tree-adjoining grammar,Rule-based machine translation,Discrete mathematics,Combinatorics,Context-free grammar,Deterministic finite automaton,Computer science,Equivalence (measure theory),Regular language,Time complexity | Conference |
ISBN | Citations | PageRank |
3-540-59119-2 | 1 | 0.36 |
References | Authors | |
9 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Carlos Domingo | 1 | 262 | 21.88 |
| Víctor Lavín | 2 | 25 | 3.54 |