-regular languages are testable with a constant number of queries

DOI10.1016/J.TCS.2004.08.004MaRDI QIDQ706616zbMATH OpenOpenAlexFDO

Authors 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

algorithmscomplexity\(\omega\)-regular languagesProperty testing

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2019622
• Regular languages are testable with a constant number of queries
• Learning regular omega languages
• Testing membership in counter automaton languages
• Testing Membership in Languages that Have Small Width Branching Programs

Cites work

• scientific article; zbMATH DE number 1670872 (Why is no real title available?)
• scientific article; zbMATH DE number 438994 (Why is no real title available?)
• scientific article; zbMATH DE number 1559556 (Why is no real title available?)
• scientific article; zbMATH DE number 4119616 (Why is no real title available?)
• scientific article; zbMATH DE number 1833419 (Why is no real title available?)
• scientific article; zbMATH DE number 1833420 (Why is no real title available?)
• scientific article; zbMATH DE number 2102704 (Why is no real title available?)
• scientific article; zbMATH DE number 1418268 (Why is no real title available?)
• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• A Bound for a Solution of a Linear Diophantine Problem
• A sublinear bipartiteness tester for bounded degree graphs
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Decision problems forω-automata
• Defining liveness
• Proof of a conjecture by Erdős and Graham concerning the problem of Frobenius
• Property testing and its connection to learning and approximation
• Reasoning about infinite computations
• Robust Characterizations of Polynomials with Applications to Program Testing
• Safety, liveness and fairness in temporal logic
• Testing \(k\)-colorability
• Testing and generating infinite sequences by a finite automaton
• Three theorems regarding testing graph properties

Cited in

(11)

• Regular languages are testable with a constant number of queries
• Testable and untestable classes of first-order formulae
• Typical paths of a graph
• Indistinguishability and First-Order Logic
• scientific article; zbMATH DE number 2019622 (Why is no real title available?)
• Relational Properties Expressible with One Universal Quantifier Are Testable
• Sublinear DTD validity
• Property testing of regular tree languages
• Space complexity vs. query complexity
• Space Complexity vs. Query Complexity
• Property testing for bounded degree databases

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q706616)