wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

locally_testable_language (897B)

      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 infixes 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 Membership is decidable in [ptime] with 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 dans place2013separating, where you can further count [modulo] a certain value
     17 
     18 See also: [piecewise_testable_language], [local_language], [suffix_testable_language], [prefix_testable_language]
     19 
     20 Up: [formal_language]