wiki_research

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

nfa_unary_lengths (439B)

      1 # NFA unary lengths
      2 
      3 An [NFA] which is [automata_unary], i.e., on a [unary_alphabet]
      4 
      5 - testing acceptance: [potechin2020lengths]
      6   - [lower_bound] from [triangle_detection]
      7     - already for [automata_acyclic]
      8   - also [lower_bound] from [orthogonal_vectors]
      9 - listing accepted lengths: [potechin2020lengths]
     10 - generalizes [subset_sum] with inputs coded in unary
     11 
     12 Up: [automata_unary], [nfa_acceptance]
     13 
     14 See also: [nfa_smallest_rejected]