Languages that are Recognized by Simple Counter Automata are not necessarily Testable
Oded Lachish, Ilan Newman · Electronic colloquium on computational complexity · 2005
Combinatorial property testing deals with the following relaxation of decision problems: Given a xed property and an input f, one wants to decide whether f satises 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 ( 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.