sharp_ufa (399B)
1 # Sharp-UFA 2 3 given [word_automaton_unambiguous] A and length n in [unary], count the number of words of length n accepted by A 4 5 in [ptime], by counting [run]s 6 7 even if n is given in binary, by [fast_exponentiation] and [matrix_multiplication] 8 - cf https://cstheory.stackexchange.com/a/8202 9 10 Up: [sharp_automaton], [word_automaton_unambiguous] 11 12 See also: [sharp_nfa], [sharp_dfa], [density_function]