wiki_research

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

property_testing_formal_language (969B)

      1 # Property testing formal language
      2 
      3 - [alon2001regular] on [regular_languages]
      4   - [Otilde](1/ε) bits are enough to know [with_high_probability] whether you need to change at least εn positions to belong to the target [regular_language]
      5     - more precisely O(log^3(1/ε) / ε)
      6   - uses [hamming_distance]
      7 - [ndione2013approximate] for [levenshtein_distance]:
      8   - uses the [levenshtein_distance], which is weaker
      9   - but the result is wrong according to [bathie2021property]
     10 - [bathie2021property] on [regular_languages]
     11   - uses the [levenshtein_distance], which is weaker
     12 - [bathie2025trichotomy] on [regular_languages]
     13   - uses the [hamming_distance]
     14   - gives a precise description of the complexity as a function of ε
     15 - [francois2015streaming] on [visibly_pushdown_languages]
     16 - [fischer2010approximate] for [edit_distance_with_moves]
     17   - called "approximate satisfiability"
     18 
     19 Up: [property_testing], [formal_language]
     20 
     21 Aliases: property testing formal languages