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)
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Randomized algorithms (68W20)
Related Items (27)
On the strength of comparisons in property testing ⋮ Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs ⋮ Proofs of proximity for context-free languages and read-once branching programs ⋮ Efficient Removal Lemmas for Matrices ⋮ Property Testing for Bounded Degree Databases ⋮ Approximate membership for regular languages modulo the edit distance ⋮ Efficient removal lemmas for matrices ⋮ Indistinguishability and First-Order Logic ⋮ Testing membership for timed automata ⋮ Fully dynamic \(k\)-center clustering with outliers ⋮ Testable and untestable classes of first-order formulae ⋮ Distribution-free connectivity testing for sparse graphs ⋮ Zero-Knowledge Proofs of Proximity ⋮ Testing of matrix-poset properties ⋮ Non-interactive proofs of proximity ⋮ Testing convexity properties of tree colorings ⋮ Testing permutation properties through subpermutations ⋮ Property Testing of Massively Parametrized Problems – A Survey ⋮ Testing low-degree polynomials over prime fields ⋮ Unnamed Item ⋮ Testing subgraphs in directed graphs ⋮ Sublinear DTD Validity ⋮ Functions that have read-once branching programs of quadratic size are not necessarily testable ⋮ A combinatorial characterization of smooth LTCs and applications ⋮ Relational Properties Expressible with One Universal Quantifier Are Testable ⋮ A large lower bound on the query complexity of a simple Boolean function ⋮ Lower bounds for testing triangle-freeness in Boolean functions
This page was built for publication: Regular Languages are Testable with a Constant Number of Queries
