Results 21 to 30 of about 8,270 (198)
Arithmetical subword complexity of automatic sequences [PDF]
, 2023 We fully classify automatic sequences $a$ over a finite alphabet $Ω$ with the property that each word over $Ω$ appears is $a$ along an arithmetic progression. Using the terminology introduced by Avgustinovich, Fon-Der-Flaass and Frid, these are the automatic sequences with the maximal possible arithmetical subword complexity.
Jakub Konieczny, Clemens Müllner
openalex +3 more sources
Subword complexity and power avoidance [PDF]
Theoretical Computer Science, 2018 We begin a systematic study of the relations between subword complexity of infinite words and their power avoidance. Among other things, we show that -- the Thue-Morse word has the minimum possible subword complexity over all overlap-free binary words and all $(\frac 73)$-power-free binary words, but not over all $(\frac 73)^+$-power-free binary words;
Jeffrey Shallit, Arseny M. Shur
openalex +6 more sources
On Minimal Words With Given Subword Complexity [PDF]
The Electronic Journal of Combinatorics, 1998 We prove that the minimal length of a word $S_n$ having the property that it contains exactly $F_{m+2}$ distinct subwords of length $m$ for $1 \leq m \leq n$ is $F_n + F_{n+2}$. Here $F_n$ is the $n$th Fibonacci number defined by $F_1 = F_2 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n > 2$.
Ming‐Wei Wang, Jeffrey Shallit
openalex +3 more sources
Subword Complexity and (non)-automaticity of certain completely multiplicative functions [PDF]
Advances in Applied Mathematics, 2016 In this article, we prove that for a completely multiplicative function $f$ from $\mathbb{N}^*$ to a field $K$ such that the set $$\{p \;|\; f(p)\neq 1_K \;\mbox{and }p \mbox{ is prime}\}$$ is finite, the asymptotic subword complexity of $f$ is $ (n^t)$, where $t$ is the number of primes $p$ that $f(p)\neq 0_K, 1_K$.
Yining Hu
openalex +3 more sources
Subword complexity and decomposition of the set of factors [PDF]
, 2014 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.
Julien Cassaigne +3 more
openalex +6 more sources
Scattered Subword Complexity of Non-Primitive Words
, 2008 In this paper we analyze primitive words from the point of view of their scattered subwords. The language of primitive words has been the subject of numerous studies. It is the language of the words that are not proper powers of another word. First we take a look at the Parikh-vectors of these words, that is, we consider the commutative closure of ...
Szilárd Zsolt Fazekas, Benedek Nagy
openalex +2 more sources
On state complexity for subword-closed languages [PDF]
This paper investigates the state complexities of subword-closed and superword-closed languages, comparing them to regular languages. We focus on the square root operator and the substitution operator. We establish an exponential lower bound for superword-closed languages for the k-th root.
Jérôme Guyot
openalex +3 more sources
Slide complexes and subword complexes [PDF]
Russian Mathematical Surveys, 2020 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Smirnov, Evgeny Yu., Tutubalina, Anna A.
openaire +4 more sources
Quasiperiods, Subword Complexity and the Smallest Pisot Number
, 2016 Journal of Automata, Languages and Combinatorics, Volume 21, Numbers 1-2, 2016, 93 ...
Ronney Polley, Ludwig Staiger
openalex +2 more sources
Applying a uniform marked morphism to a word [PDF]
Discrete Mathematics & Theoretical Computer Science, 1999 We describe the relationship between different parameters of the initial word and its image obtained by application of a uniform marked morphism. The functions described include the subword complexity, frequency of factors, and the recurrence function ...
Anna Frid
doaj +3 more sources