wiki_research

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

locally_threshold_testable_language (478B)


      1 # Locally_threshold_testable_language
      2 
      3 Discussed in [bojanczyk2007new]
      4 
      5 A [formal_language] is *locally threshold testable* if it is a [Boolean_combination] of [formal_languages] of the form:
      6 - words having a given [word] w as a [prefix]
      7 - words having a given [word] w as a [suffix]
      8 - words having a given [word] w as a [factor] at least n times
      9 
     10 Generalizes [locally_testable_languages]
     11 
     12 Up: [locally_testable_language]
     13 
     14 See also: [local_language]
     15 
     16 Aliases: LTT language, LTT