Subword complexity and decomposition of the set of factors

DOI10.1007/978-3-662-44522-8_13zbMATH Open1425.68187arXiv1406.3974OpenAlexW165929378MaRDI QIDQ2922010FDOQ2922010

Authors: Julien Cassaigne, Svetlana Puzynina, Luca Q. Zamboni, Anna Frid 

Publication date: 14 October 2014

Published in: Mathematical Foundations of Computer Science 2014 (Search for Journal in Brave)

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$.

Full work available at URL: https://arxiv.org/abs/1406.3974

Recommendations

• On the character of words of sublinear complexity
• On the minimal complexity of infinite words
• A characterization of words of linear complexity
• Asymptotic subword complexity
• Factor complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Combinatorics on words (68R15)

Cites Work

• Title not available (Why is that?)
• Some improvements of the \(S\)-adic conjecture
• Subword complexities of various classes of deterministic developmental languages without interactions
• Complexité des facteurs des mots infinis engendrés par morphismes itérés
• On palindromic factorization of words
• Title not available (Why is that?)
• Factor complexity
• Prime Decompositions of Regular Languages
• A UNIQUE DECOMPOSITION THEOREM FOR FACTORIAL LANGUAGES

Cited In (4)

• Cost and dimension of words of zero topological entropy
• On subword decomposition and balanced polynomials
• Subword complexity and Laurent series
• A characterization of words of linear complexity

This page was built for publication: Subword complexity and decomposition of the set of factors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2922010)