1. Subword complexity and decomposition of the set of factors
- Author
-
Cassaigne, J., Frid, A. E., Puzynina, S., and Zamboni, L. Q.
- Subjects
Computer Science - Formal Languages and Automata Theory ,Computer Science - Discrete Mathematics ,68R15 ,G.2.1 ,F.4.3 - Abstract
In this paper we explore a new hierarchy of classes of languages and infinite words and its connection with complexity classes. Namely, we say that a language belongs to the class $L_k$ if it is a subset of the catenation of $k$ languages $S_1\cdots S_k$, where the number of words of length $n$ in each of $S_i$ is bounded by a constant. The class of infinite words whose set of factors is in $L_k$ is denoted by $W_k$. In this paper we focus on the relations between the classes $W_k$ and the subword complexity of infinite words, which is as usual defined as the number of factors of the word of length $n$. In particular, we prove that the class $W_{2}$ coincides with the class of infinite words of linear complexity. On the other hand, although the class $W_{k}$ is included in the class of words of complexity $O(n^{k-1})$, this inclusion is strict for $k> 2$., Comment: The final publication will be available in the Springer proceedings of MFCS 2014
- Published
- 2014