Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-152 | 9th December 2005 00:00

Languages that are Recognized by Simple Counter Automata are not necessarily Testable

RSS-Feed




TR05-152
Authors: Oded Lachish, Ilan Newman
Publication: 12th December 2005 10:07
Downloads: 2111
Keywords: 


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.



ISSN 1433-8092 | Imprint