wiki_research

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

density_function (672B)

      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_polyslender]
      9 - [language_polynomially_bounded]
     10 
     11 [counting_problem] of evaluating it: [sharp_automaton]
     12 
     13 testing which lengths can be achieved, on [NFAs]: [potechin2020lengths]
     14 
     15 computing its regime on [context_free_languages]: [gawrychowski2010finding]
     16 
     17 Up: [automata]
     18 
     19 See also: [universality_automata], [sharp_automaton], [slice], [degree_of_ambiguity], [growth_rate_analysis]
     20 
     21 Aliases: density functions