Up: Formal Languages
Previous: Formal Languages
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.
An order j, i.e., a positive integer j witnessing the local testability of
The value of the order, i.e., j.
- Good News:
Admits a PTAS .