It Is NL-complete to Decide Whether a Hairpin Completion of Regular Languages Is Regular

Volker Diekert Steffen Kopecki

Published in: CoRR (2011)

Keyphrases

regular languages
regular expressions
grammatical inference
context free languages
finite automata

decision problems
context free
context free grammars
natural language

pac learning
positive data
finite state machines
pattern matching

equivalence queries
statistical queries
theoretical analysis
computational complexity