density_function (542B)
1 # Density function 2 3 function defined on an [automata] and giving the number of words of a given length accepted by that automaton (= cardinality of [slice] of its [formal_language]) 4 5 possible regimes: exponential, polynomial, etc. 6 7 - [language_slender] 8 - [language_polynomially_bounded] 9 10 [counting_problem] of evaluating it: [sharp_automaton] 11 12 testing which lengths can be achieved, on [NFAs]: [potechin2020lengths] 13 14 Up: [automata] 15 16 See also: [universality_automata], [sharp_automaton], [slice], [degree_of_ambiguity], [growth_rate_analysis]