Next:
Miscellaneous
Up:
Formal Languages
Previous:
Formal Languages
-
I
NSTANCE
:
A locally testable language
L
, i.e., a language
L
such that, for some
positive integer
j
, whether or not a string
x
is in the language depends on
(a) the prefix and suffix of
x
of length
j-1
, and (b) the set of substrings
of
x
of length
j
.
-
S
OLUTION
:
An order
j
, i.e., a positive integer
j
witnessing the local testability of
L
.
-
M
EASURE
:
The value of the order, i.e.,
j
.
-
Good News:
Admits a PTAS [
231
].
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997