{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T23:23:43Z","timestamp":1791069823730,"version":"4.1.0"},"reference-count":14,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2001,1]]},"abstract":"<jats:p>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\\in \\{0,1\\}^*$ and an integer n there exists a randomized algorithm which always accepts a word w of length n if $w\\in L$ and rejects it with high probability if w has to be modified in at least $\\epsilon n$ positions to create a word in L. The algorithm queries $\\tilde{O}(1\/\\epsilon)$ bits of w. This query complexity is shown to be optimal up to a factor polylogarithmic in $1\/\\epsilon$. 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 $\\epsilon$. 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.<\/jats:p>","DOI":"10.1137\/s0097539700366528","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1842-1862","source":"Crossref","is-referenced-by-count":73,"title":["Regular Languages are Testable with a Constant Number of Queries"],"prefix":"10.1137","volume":"30","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Krivelevich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ilan","family":"Newman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mario","family":"Szegedy","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070001"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"R3","unstructured":"Manuel Blum, Michael Luby, Ronitt Rubinfeld, Self\u2010testing\/correcting with applications to numerical problems, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (Baltimore, MD, 1990), Vol. 47, 1993, 549\u201359594m:65020"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"M. D. Davis, R. Sigal, and E. Weyuker,\n                      Computability, Complexity and Languages: Fundamentals of Theoretical Computer Science\n                      , Academic Press, New York, 1994.","DOI":"10.1016\/B978-0-08-050246-5.50020-9"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0022-314X(90)90150-P"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"P. Gemmell, R. Lipton, R. Rubinfeld, M. Sudan, and A. Wigderson,\n                      Self\u2010testing\/correcting for polynomials and for approximate functions\n                      , in Proceedings of the 23rd ACM Symposium on Theory of Computer Science, ACM, New York, 1991, pp. 33\u201342.","DOI":"10.1145\/103418.103429"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Oded Goldreich, Shafi Goldwasser, Dana Ron, Property testing and its connection to learning and approximation, IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, 339\u20133481450632","DOI":"10.1109\/SFCS.1996.548493"},{"key":"R8","unstructured":"John Hopcroft, Jeffrey Ullman, Wprowadzenie do teorii automat\u00f3w, j\u0119zyk\u00f3w i oblicze\u0144, Wydawnictwo Naukowe PWN, Warsaw, 1994, 480\u20130, Translated from the 1979 English original by Beata Konikowska99a:68001"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-6.1.61"},{"key":"R10","unstructured":"Richard Lipton, New directions in testing, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Vol. 2, Amer. Math. Soc., Providence, RI, 1991, 191\u201320292c:68127"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"N. Nisan and M. Szegedy,\n                      On the degree of Boolean functions as real polynomials\n                      , Proceedings of the 24th ACM Symposium on Theory of Computer Science, ACM, New York, 1992, pp. 462\u2013467.","DOI":"10.1145\/129712.129757"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"N. Nisan,\n                      CREW PRAMs and decision trees\n                      , in Proceedings of the 21st ACM Symposium on Theory of Computer Science, ACM, New York, 1989, pp. 327\u2013335.","DOI":"10.1145\/73007.73038"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"A. C. Yao,\n                      Probabilistic computation, towards a unified measure of complexity\n                      , in Proceedings of the 18th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 1977, pp. 222\u2013227.","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539700366528","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:20:10Z","timestamp":1787336410000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539700366528"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,1]]},"references-count":14,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2001,1]]}},"alternative-id":["10.1137\/S0097539700366528"],"URL":"https:\/\/doi.org\/10.1137\/s0097539700366528","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,1]]}}}