Regular Languages are Testable with a Constant Number of Queries

From MaRDI portal
Publication:2706138

DOI10.1137/S0097539700366528zbMath0992.68064MaRDI QIDQ2706138

Michael Krivelevich, Mario Szegedy, Noga Alon, Ilan Newman

Publication date: 19 March 2001

Published in: SIAM Journal on Computing (Search for Journal in Brave)




Related Items (27)

On the strength of comparisons in property testingProofs of Proximity for Context-Free Languages and Read-Once Branching ProgramsProofs of proximity for context-free languages and read-once branching programsEfficient Removal Lemmas for MatricesProperty Testing for Bounded Degree DatabasesApproximate membership for regular languages modulo the edit distanceEfficient removal lemmas for matricesIndistinguishability and First-Order LogicTesting membership for timed automataFully dynamic \(k\)-center clustering with outliersTestable and untestable classes of first-order formulaeDistribution-free connectivity testing for sparse graphsZero-Knowledge Proofs of ProximityTesting of matrix-poset propertiesNon-interactive proofs of proximityTesting convexity properties of tree coloringsTesting permutation properties through subpermutationsProperty Testing of Massively Parametrized Problems – A SurveyTesting low-degree polynomials over prime fieldsUnnamed ItemTesting subgraphs in directed graphsSublinear DTD ValidityFunctions that have read-once branching programs of quadratic size are not necessarily testableA combinatorial characterization of smooth LTCs and applicationsRelational Properties Expressible with One Universal Quantifier Are TestableA large lower bound on the query complexity of a simple Boolean functionLower bounds for testing triangle-freeness in Boolean functions




This page was built for publication: Regular Languages are Testable with a Constant Number of Queries