wiki_research

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

subsequence_testing_gap_constraints (429B)

      1 # Subsequence testing gap constraints
      2 
      3 [subsequence_testing] with gap constraints
      4 
      5 - [day2022subsequences]
      6   - gap equalities make problem [NP_complete] (Section 5)
      7   - gaps are specified with length intervals and automata given as [DFA]s
      8   - with only length constraints, cf [iliopoulos2007algorithms]
      9 
     10 Up: [subsequence_testing], [gap_constraints]
     11 
     12 See also: [gapped_pattern_matching], [p_subsequence], [gapped_string_indexing]