Deciding regularity of hairpin completions of regular languages in polynomial time.
Volker DiekertSteffen KopeckiVictor MitranaPublished in: Inf. Comput. (2012)
Keyphrases
- regular languages
- finite automata
- positive data
- equivalence queries
- context free languages
- grammatical inference
- regular expressions
- statistical queries
- decision problems
- membership queries
- context free grammars
- pac learning
- computational complexity
- special case
- efficient learning
- positive and negative
- positive examples
- pattern languages
- database
- pac learnable
- boolean functions
- np hard
- lower bound
- training data
- machine learning