Definitions
Definitions
A locally testable language L is a language with
the property that
for some nonnegative integer k, called the order of local testability,
whether or not a word u in the language depends on
(1) the prefix and suffix of the word u of length k-1 and
(2) the set of intermediate substrings of length k of the word u.
For given k the language is called k-testable
A language L [a semigroup, an automaton] is
locally testable if it is
k-testable for
some k.
In the case of strictly k-testable language three sets of
intermediate substrings, prefixes and suffixes of length k must exist.
The local threshold testability generalizes the concept of
local testability. The number of occurences of the factor is
taken in account, but only till the threshold.
For right [left] locally testable language
the order of the first appearance of these segments in prefixes
[suffixes] is essential.
.
A locally threshold testable language L is a language
with the property that
for some nonnegative integer k, called the order of local testability,
and for some threshold m whether or not a word u in the language depends on
(1) the prefix and suffix of the word u of length k-1,
(2) the set of factors of length k of the word u and
(3) number of occurrences of factor up to threshold.
For given k and m the language is called m-threshold k-testable.
A language L [a semigroup, an automaton] is
locally threshold testable if it is
m-threshold k-testable for
some k and m.
It is best understood in terms of a kind of computational procedure used
to classify a two-dimensional image: a window of relatively small size
is moved around on the image and a record is made of the various
attributes of the image that are detected by what is observed through the
window. No record is kept of the order in which the attributes are observed,
where each attribute occurs, or (for local testability) how many times it occurs.
For local threshold testability we count every attribute up to threshold.
We say that a class
of images is locally testable if a decision about whether a given image
belongs to the class can be made simply on the basis of the set of attributes
that occur.
| | | | | | | | | | | | | | | | | |
a b | | e c d
| | | | | e c d
| f g
a b | e c d
| | | | | e c d
e c d | f g
a b | | | e c d
| | | | | f g
Here k=3. All three words have the same begin, end and at least one common factor,
but for this factor number of occurences differs.
Local testability implies local threshold testability and
is a kind of local threshold testability with threshold 1
next