Next: Miscellaneous Up: Formal Languages Previous: Formal Languages Index

### MINIMUM LOCALLY TESTABLE AUTOMATON ORDER

- 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 [304].