wiki_research

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

arenas2020fpras (324B)

      1 # arenas2020fpras
      2 
      3 FPRAS [fpras] to count the number of [tree] of a given size accepted by nondeterministic 
      4 [tree_automaton]
      5 
      6 Proof sketch in [arenas2022counting]
      7 
      8 Note: it is [sharpp]-hard to exactly count the number of distinct words of length n accepted by an NFA A, given n and A as input 
      9 
     10 
     11 
     12 Up: [academic_paper_list]