id: 06101068
dt: a
an: 06101068
au: Staiger, Ludwig
ti: Asymptotic subword complexity.
so: Bordihn, Henning (ed.) et al., Languages alive. Essays dedicated to Jürgen
    Dassow on the occasion of his 65th birthday. Berlin: Springer (ISBN
    978-3-642-31643-2/pbk). Lecture Notes in Computer Science 7300, 236-245
    (2012).
py: 2012
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/978-3-642-31644-9_16
ab: Summary: The subword complexity of an infinite word $ξ$ is a function
    $f(ξ,n)$ returning the number of finite subwords (factors, infixes) of
    length $n$ of $ξ$. In the present paper we investigate infinite words
    for which the set of subwords occurring infinitely often is a regular
    language. Among these infinite words we characterise those which are
    eventually recurrent. Furthermore, we derive some results comparing the
    asymptotics of $f(ξ,n)$ to the information content of sets of finite
    or infinite words related to $ξ$. Finally, we give a simplified proof
    of Theorem 6 of [18].
rv: