\(\omega\)-regular languages are testable with a constant number of queries

DOI10.1016/j.tcs.2004.08.004zbMath1086.68071OpenAlexW2068161577MaRDI QIDQ706616

Hana Chockler, Orna Kupferman

Publication date: 9 February 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.08.004

zbMATH Keywords

complexityalgorithms\(\omega\)-regular languagesProperty testing

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Related Items (6)

Property Testing for Bounded Degree Databases ⋮ Indistinguishability and First-Order Logic ⋮ Testable and untestable classes of first-order formulae ⋮ Property testing of regular tree languages ⋮ Sublinear DTD Validity ⋮ Relational Properties Expressible with One Universal Quantifier Are Testable

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Proof of a conjecture by Erdős and Graham concerning the problem of Frobenius
• Defining liveness
• Reasoning about infinite computations
• Safety, liveness and fairness in temporal logic
• A sublinear bipartiteness tester for bounded degree graphs
• Testing k-colorability
• Property testing and its connection to learning and approximation
• Three theorems regarding testing graph properties
• Robust Characterizations of Polynomials with Applications to Program Testing
• Decision problems forω-automata
• Testing and generating infinite sequences by a finite automaton
• Decidability of Second-Order Theories and Automata on Infinite Trees
• A Bound for a Solution of a Linear Diophantine Problem
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

This page was built for publication: \(\omega\)-regular languages are testable with a constant number of queries