locally_testable_language (1115B)
1 # Locally testable language 2 3 A [formal_language] is *locally testable* if it is k-testable for some k, where a k-testable language is one where membership depends only on the [prefix] and [suffix] of length k and the set of [factors] of size k 4 5 ## Subclass 6 7 - "strictly locally testable" in [caron2000families]: the locally testable languages are the [Boolean_combinations] of [strictly_locally_testable_languages] 8 9 ## Membership problem to the class 10 11 The [membership_problem] is decidable in [PTIME] with an [algebraic_characterization], cf [schutzenberger1965monoids], [caron2000families] 12 13 ## Generalizations 14 15 - [locally_threshold_testable_language] where you can count infixes up to some threshold 16 - mTT+MOD in [place2013separating], where you can further count [modulo] a certain value 17 - [garcia2000right]: [locally_testable_language_right] and [locally_testable_language_left], which strictly generalize the locally testable languages 18 19 See also: [piecewise_testable_language], [local_language], [suffix_testable_language], [prefix_testable_language] 20 21 Up: [formal_language] 22 23 Aliases: locally testable languages