Regular languages are testable with a constant number of queries

Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szeged

Research output: Contribution to journalArticle

87 Scopus citations

Abstract

We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser, and Ron in [J. ACM, 45 (1998), pp. 653-750]. The subject of this paper is testing regular languages. Our main result is as follows. For a regular language L £{0,1} and an integer n there exists a randomized algorithm which always accepts a word w of length n if tu £L and rejects it \vith high probability if w has to be modified in at least en positions to create a word in L. The algorithm queries O(l/e) bits of w. This query complexity is shown to be optimal up to a factor polylogarithmic in 1/e. We also discuss the testability of more complex languages and show, in particular, that the query complexity required for testing context-free languages cannot be bounded by any function of (.. The problem of testing regular languages can be viewed as a part of a very general approach, seeking to probe testability of properties defined by logical means.

Original languageEnglish (US)
Pages (from-to)1842-1862
Number of pages21
JournalSIAM Journal on Computing
Volume30
Issue number6
DOIs
StatePublished - 2000
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

  • Context-free languages
  • Property testing
  • Regular languages

Fingerprint Dive into the research topics of 'Regular languages are testable with a constant number of queries'. Together they form a unique fingerprint.

  • Cite this