ω-Regular Languages Are Testable with a Constant Number of Queries (English)
- New search for: Chockler, Hana
- New search for: Kupferman, Orna
- New search for: Chockler, Hana
- New search for: Kupferman, Orna
In:
Randomization and Approximation Techniques in Computer Science
;
26-38
;
2002
-
ISSN:
- Article/Chapter (Book) / Electronic Resource
-
Title:ω-Regular Languages Are Testable with a Constant Number of Queries
-
Contributors:Chockler, Hana ( author ) / Kupferman, Orna ( author )
-
Published in:Lecture Notes in Computer Science ; 2483 ; 26-38
-
Publisher:
- New search for: Springer Berlin Heidelberg
-
Place of publication:Berlin, Heidelberg
-
Publication date:2002-01-01
-
Size:13 pages
-
ISBN:
-
ISSN:
-
DOI:
-
Type of media:Article/Chapter (Book)
-
Type of material:Electronic Resource
-
Language:English
-
Keywords:
-
Source:
Table of contents eBook
The tables of contents are generated automatically and are based on the data records of the individual contributions available in the index of the TIB portal. The display of the Tables of Contents may therefore be incomplete.
- 1
-
Counting Distinct Elements in a Data StreamBar-Yossef, Ziv / Jayram, T. S. / Kumar, Ravi / Sivakumar, D. / Trevisan, Luca et al. | 2002
- 11
-
On Testing Convexity and SubmodularityParnas, Michal / Ron, Dana / Rubinfeld, Ronitt et al. | 2002
- 26
-
ω-Regular Languages Are Testable with a Constant Number of QueriesChockler, Hana / Kupferman, Orna et al. | 2002
- 39
-
Optimal Lower Bounds for 2-Query Locally Decodable Linear CodesObata, Kenji et al. | 2002
- 51
-
Counting and Sampling H-ColouringsDyer, Martin / Goldberg, Leslie A. / Jerrum, Mark et al. | 2002
- 68
-
Rapidly Mixing Markov Chains for Dismantleable Constraint GraphsDyer, Martin / Jerrum, Mark / Vigoda, Eric et al. | 2002
- 78
-
On the 2-Colorability of Random HypergraphsAchlioptas, Dimitris / Moore, Cristopher et al. | 2002
- 91
-
Percolation on Finite Cayley GraphsMalon, Christopher / Pak, Igor et al. | 2002
- 105
-
Computing Graph Properties by Randomized Subcube PartitionsFriedgut, Ehud / Kahn, Jeff / Wigderson, Avi et al. | 2002
- 114
-
Bisection of Random Cubic GraphsDíaz, J. / Do, N. / Sernal, M. J. / Wormald, N. C. et al. | 2002
- 126
-
Small k-Dominating Sets of Regular GraphsDuckworth, William / Mans, Bernard et al. | 2002
- 139
-
Finding Sparse Induced Subgraphs of Semirandom GraphsCoja-Oghlan, Amin et al. | 2002
- 149
-
Mixing in Time and Space for Lattice Spin Systems: A Combinatorial ViewDyer, Martin / Sinclair, Alistair / Vigoda, Eric / Weitz, Dror et al. | 2002
- 164
-
Quantum Walks on the HypercubeMoore, Cristopher / Russell, Alexander et al. | 2002
- 179
-
Randomness-Optimal Characterization of Two NP Proof SystemsSantis, Alfredo / Crescenzo, Giovanni / Persiano, Giuseppe et al. | 2002
- 194
-
A Probabilistic-Time Hierarchy Theorem for “Slightly Non-uniform” AlgorithmsBarak, Boaz et al. | 2002
- 209
-
Derandomization That Is Rarely Wrong from Short Advice That Is Typically GoodGoldreich, Oded / Wigderson, Avi et al. | 2002
- 224
-
Is Constraint Satisfaction Over Two Variables Always Easy?Engebretsen, Lars / Guruswami, Venkatesan et al. | 2002
- 239
-
Dimensionality Reductions That Preserve Volumes and Distance to Affine Spaces, and Their Algorithmic ApplicationsMagen, Avner et al. | 2002
- 254
-
On the Eigenvalue Power LawMihail, Milena / Papadimitriou, Christos et al. | 2002
- 263
-
Classifying Special Interest Groups in Web GraphsCooper, Colin et al. | 2002