Content deleted Content added
Deltahedron (talk | contribs) →Related concepts: cite Berthé & Rigo (2010) |
Deltahedron (talk | contribs) →Complexity function of a language: polynomial language, cite Berthe & Rigo (2010) |
||
Line 23:
:<math>L \subseteq \{ x y^k z : x,y,z \in F,\ k \in \mathbb{N} \} \ . </math>
A '''polynomial''' or '''sparse''' 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==
| |||