Independence Results About Context-Free Languages and Lower Bounds.
Juris HartmanisPublished in: Inf. Process. Lett. (1985)
Keyphrases
- context free languages
- lower bound
- grammatical inference
- upper bound
- context free grammars
- regular languages
- context free
- objective function
- inductive inference
- np hard
- worst case
- finite automata
- context dependent
- sample complexity
- vc dimension
- statistical queries
- optimal solution
- regular expressions
- learning theory
- pac learning
- equivalence queries
- machine learning