Regular Languages are Testable with a Constant Number of Queries.

Noga Alon Michael Krivelevich Ilan Newman Mario Szegedy

Published in: SIAM J. Comput. (2000)

Keyphrases

data model
database
computational complexity
query language
small number
databases
query processing
pattern matching
context free languages
relational databases
regular expressions
grammatical inference
positive data
regular languages