wiki_research

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

blocking_factor (436B)

      1 # Blocking factor
      2 
      3 A blocking factor of a [language] is a [word] which never occurs as a [factor] of a [word] of the language
      4 
      5 - [minimal_blocking_factor]
      6 - [blocking_sequence]
      7   - [blocking_sequence_minimal]
      8 
      9 ## Meta-dichotomy
     10 
     11 even for [strongly_connected] [NFA], it's [PSPACE_complete]
     12   - reduction from [NFA_universality]
     13 
     14 See also: [links_seminar_gabriel], [property_testing], [Mortal_word]
     15 
     16 Aliases: blocking factors
     17 
     18 Up: [word]