Next: Miscellaneous
Up: Formal Languages
Previous: Formal Languages
Index
- INSTANCE:
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.
- SOLUTION:
An order j, i.e., a positive integer j witnessing the local testability of
L.
- MEASURE:
The value of the order, i.e., j.
- Good News:
Admits a PTAS [321].
Viggo Kann
2000-03-20