Space Complexity vs. Query Complexity

DOI10.1007/11830924_39MaRDI QIDQ3595382zbMATH OpenOpenAlexFDO

Authors Oded Lachish, Ilan Newman, Asaf Shapira

Publication date 28 August 2007

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11830924_39

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Space complexity vs. query complexity
• Regular languages are testable with a constant number of queries
• scientific article; zbMATH DE number 2079374
• Testing membership in counter automaton languages
• \(\omega\)-regular languages are testable with a constant number of queries

Cited in

(4)

• Space complexity vs. query complexity
• Approximate Query Complexity
• Regular languages are testable with a constant number of queries
• Testing membership in counter automaton languages

This page was built for publication: Space Complexity vs. Query Complexity

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