wiki_research

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

permutation_pattern_matching (508B)

      1 # Permutation pattern matching
      2 
      3 [computational_complexity]
      4 - [np_hard]: [bose1998pattern]
      5 - [fixed_parameter_tractable]: [guillemot2013finding]
      6 
      7 [stanley_wilf_conjecture]
      8 - [conjecture] on the proportion of [permutations] which [permutation_avoid] a [permutation_pattern]
      9 
     10 Generalizations:
     11 - with [vincular] patterns: [W1_hard]
     12   - cf [bruner2014computational]
     13 - with [parity_constraints]
     14   - cf [ardevolmartinez2024parity]
     15 
     16 See also: [permutation], [vincular]
     17 
     18 Up: [pattern_matching], [permutation_pattern]