Revision as of 20:29, 23 February 2014 edit Deltahedron (talk \| contribs) Pending changes reviewers 7,714 edits →Complexity function of a language: polynomial language, cite Berthe & Rigo (2010) ← Previous edit		Revision as of 20:55, 23 February 2014 edit undo Deltahedron (talk \| contribs) Pending changes reviewers 7,714 edits m →Complexity function of a language: link Next edit →
Line 24: :<math>L \subseteq \{ x y^k z : x,y,z \in F,\ k \in \mathbb{N} \} \ . </math> A '''polynomial''' or '''[[sparse language]]''' ~~language~~ is one for which the complexity function ''p''(''n'') is bounded by a fixed power of ''n''. A [[regular language]] which is not polynomial is ''exponential'': there are infinitely many ''n'' for which ''p''(''n'') is greater than ''k''<sup>''n''</sup> for some fixed ''k'' > 1.<ref name=BR136>Berthé & Rigo (2010) p.136</ref> ==Related concepts==

Complexity function: Difference between revisions