BispecialFactorsAndComplexity < Substitutions

Substitutions

Substitutions.BispecialFactorsAndComplexityr1.1 - 15 Jun 2007 - 23:05 - ThierryMonteiltopic end

Start of topic | Skip to actions

Bispecial factors and complexity

If p(n) is the complexity of a langage L. Its first derivate is given by :

$s(n) = p(n+1)-p(n) = \sum_{w \mbox{ \small right special of length } n} m_r(w)$

where

$m_r(w) = card \{ a\in A | wa \in L\} -1$

is the right multiplicity of w (it works also for the left special factors).

Its second derivative is given by :

$b(n) = s(n+1)-s(n) = \sum_{w \mbox{ \small bispecial of length } n} m(w)$

where

$m(w) = card \{ (a,b) \in A^2 | awb \in L\} -m_r(w) -m_l(w)-1$

is the multiplicity of w.

In the binary case A={0,1}, on has 3 types of multiplicities :

As a good reference, see the article of Julien Cassaigne in the links section.
to top

You are here: Substitutions > BispecialFactorsAndComplexity

to top