Lachish, Oded, Newman, Ilan and Shapira, Asaf (2008) Space complexity vs. query complexity. In: 10th RANDOM Conference, Barcelona, Spain, 28-30 Aug, 2006. Published in: Computational Complexity, Vol.17 (No.1). pp. 70-93.

Full text not available from this repository.

Abstract

Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x satisfies the property or is "far" from satisfying it. The main focus of property testing is in identifying large families of properties that can be tested with a certain number of queries to the input. In this paper we study the relation between the space complexity of a language and its query complexity. Our main result is that for any space complexity s(n) <= log n there is a language with space complexity O(s(n)) and query complexity 2(Omega(s(n))). Our result has implications with respect to testing languages accepted by certain restricted machines. Alon et al. [FOCS 1999] have shown that any regular language is testable with a constant number of queries. It is well known that any language in space o(log log n) is regular, thus implying that such languages can be so tested. It was previously known that there are languages in space 0(logn) that are not testable with a constant number of queries and Newman [FOCS 2000] raised the question of closing the exponential gap between these two results. A special case of our main result resolves this problem as it implies that there is a language in space 0(log log n) that is not testable with a constant number of queries. It was also previously known that the class of testable properties cannot be extended to all context-free languages. We further show that one cannot even extend the family of testable languages to the class of languages accepted by single counter machines.

Item Type:	Conference Item (UNSPECIFIED)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics
Divisions:	Faculty of Science > Computer Science
Journal or Publication Title:	Computational Complexity
Publisher:	Springer
ISSN:	1016-3328
Date:	2008
Volume:	Vol.17
Number:	No.1
Number of Pages:	24
Page Range:	pp. 70-93
Identification Number:	10.1007/s00037-008-0239-z
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Title of Event:	10th RANDOM Conference
Type of Event:	Conference
Location of Event:	Barcelona, Spain
Date(s) of Event:	28-30 Aug, 2006
URI:	http://wrap.warwick.ac.uk/id/eprint/30164

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item