-regular languages are testable with a constant number of queries
From MaRDI portal
Publication:706616
DOI10.1016/J.TCS.2004.08.004zbMATH Open1086.68071OpenAlexW2068161577MaRDI QIDQ706616FDOQ706616
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
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Property testing and its connection to learning and approximation
- 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
- Decision problems forω-automata
- Defining liveness
- Testing \(k\)-colorability
- 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 (6)
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)
