wiki_research

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

sharp_nfa (452B)

      1 # Sharp NFA
      2 
      3 [counting_problem] of [density_function] of [automata_nondeterministic]:
      4 - input:
      5   - [automata_nondeterministic]
      6   - a length n written in [unary]
      7 - output: cardinality of [slice] of accepted language
      8 
      9 [computational_complexity]:
     10 - [sharpp]-hard
     11   - by reduction from [sharp_satisfiability_dnf]
     12 - [spanl]-complete
     13 - admits a [fpras]: [arenas2021nfa]
     14 
     15 Up: [sharp_automaton], [automata_nondeterministic]
     16 
     17 See also: [sharp_dfa], [sharp_cfg]