wiki_research

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

property_testing_formal_language (824B)

      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   - uses [hamming_distance]
      6 - [ndione2013approximate] for [edit_distance]:
      7   - but the result is wrong according to [bathie2021property]
      8 - [bathie2021property] on [regular_languages]
      9   - uses the [levenshtein_distance], which is weaker
     10 - [bathie2025trichotomy] on [regular_languages]
     11   - uses the [hamming_distance]
     12   - gives a precise description of the complexity as a function of ε
     13 - [francois2015streaming] on [visibly_pushdown_languages]
     14 - [fischer2010approximate] for [edit_distance_with_moves]
     15   - called "approximate satisfiability"
     16 
     17 Up: [property_testing], [formal_language]