All Questions
Tagged with formal-languages combinatorics-on-words
12 questions
6
votes
1
answer
388
views
What is the max number of self-segregating words of length n?
A set of words S is called self-segregating if you don't need whitespaces to read them. It means that for any two words from S no new words from S arise between them.
For example the set ab, bc, ac, ...
- 125
5
votes
1
answer
123
views
Algorithms to factorize words into product of powers
I came across this problem, which I guess is well known to combinatorialists of words, so I write here to see if someone can help me with some references.
Let $A$ be a finite set of symbols, are there ...
- 477
2
votes
1
answer
133
views
What is the cardinality of the set of Dyck natural numbers of semilength $k$?
In arXiv:2102.02777 ("Recursive Prime Factorizations: Dyck Words as Numbers"), I show that there is a 1:1 correspondence between $\mathbb{N} = \{0,1,2,3,4,\ldots\}$ and $\mathcal{D}_{r_{\...
- 129
-1
votes
1
answer
125
views
Prove using Dyck naturals: for $n \in \mathbb{N}_{+}$ and big enough $k \in \mathbb{N}_{+}$, $p_{k-1} < \cdots < np_{k-a_{n}}$ (a is A073093)
While conducting research in connection with arXiv:2102.02777 ("Recursive Prime Factorizations: Dyck Words as Numbers"), I noticed certain interesting patterns, one of which inspired the ...
- 129
1
vote
1
answer
171
views
Terminology for set of infinite strings with a certain prefix
Let $\mathcal{A}$ be a finite alphabet, and let $C$ be the Cantor space $\mathcal{A}^\omega$ under the product topology.
Given a finite string $s \in \mathcal{A}^*$, let $C(s)$ be the set of all ...
- 8,483
9
votes
1
answer
443
views
Is there a name for infinite words containing every finite words?
Apparently, the closest thing I've found would be normal number http://mathworld.wolfram.com/NormalNumber.html
But requiring that every finite words occurs is weaker than this property. So I'm ...
- 93
2
votes
1
answer
143
views
Representability of sets of infinite sequences sharing common prefixes and factors (i.e. infixes)
Here we are concerned with the space $X^{\omega}$ of infinite sequences. Denote by $F_n(\xi)$
the set of factors (consecutive finite subsequences) of length $n$ and consider the set
$$
K_n(\xi) = \xi[...
- 798
5
votes
1
answer
346
views
What prefix and factors determine a ultimately periodic word uniquely
Let $\xi$ be an ultimately periodic sequence, i.e. there exists finite sequences $p, q \in X^*$ such that $\xi = pq^{\omega}$. Does there exists a $n > 0$ such that the prefix of length $n$ and all ...
- 798
5
votes
2
answers
387
views
Concatenation of strings [closed]
We have two strings (i. e., finite tuples) $A$ and $B$.
We have to find if for some positive integers $n$ and $m$, the string $A$ concatenated $n$ times equals the string $B$ concatenated $m$ times or ...
- 59
5
votes
2
answers
245
views
Ordering on words
What are the known computation-friendly well-orderings on words from $A^*$, where $A$ is a finite alphabet, except the standard weightlex and syllable-order?
- 1,437
20
votes
2
answers
734
views
congruence on words: having the same (scattered) subwords of length at most n
For a fixed finite alphabet $A=\{a,b,...\}$, write $x \sim_n y$ if the two words $x$ and $y$ have the same (scattered) subwords of length at most $n$. The relation $\sim_n$ is a congruence of finite ...
- 371
2
votes
1
answer
568
views
Notation for ends of a string
I work now a lot with strings of characters and other finite sequences and found that I need many times a good notation for "cutting the end" a string. If $a$ is a finite sequence and $a'$ is its ...
user22882