-regular languages are testable with a constant number of queries

DOI10.1016/J.TCS.2004.08.004zbMATH Open1086.68071OpenAlexW2068161577MaRDI QIDQ706616FDOQ706616

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

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

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)

Cites Work

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

Cited In (11)

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

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)