Abstract:
Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input $f$, one wants to decide whether $f$ satisfies the property or is `far' from satisfying the property. It has been shown that regular languages are testable, and that there exist context free language which are not testable. We show that there exists a language that is accepted by a deterministic counter automaton for which any $1/25$-test requires $\Omega(poly(\log{n}))$ queries. Thus, proving that even if we restrict ourselves to, perhaps the simplest possible stack automaton model, we do not ensure testability.