Questions tagged [word-combinatorics]
Questions about combinatorics on languages of words, that is how many sequences of symbols with certain properties there are.
53 questions
2
votes
1
answer
126
views
How to find a bijection $\Phi$ that maximizes the number of iterative replacements in a local rewriting system on $\left\{ 0, 1, 2, 3 \right\}$?
Problem. We study a local rewriting map defined on $5$-letter words over the alphabet $\{0,1,2,3\}$. A fixed forbidden-block set $\mathcal{F}$ of $16$ length-$3$ patterns is given by
$$\mathcal{F}= \{...
- 111
3
votes
0
answers
69
views
Statement on regular language density
On this forum, I've found following statement on densities of regular languages:
The density of a regular language is of the form $\Theta \left( n^k \lambda ^ n \right)$ for some integer $k \geq 0$ ...
- 41
4
votes
0
answers
75
views
Remove contiguous 5th powers (5-fold repetitions) from list of 'a's and 'b's?
Given a list of characters in $\{a,b\}$, for example $abababababa$, what is the most efficient way to remove all 5th powers in a way that makes the string as short as possible?
(This example would ...
- 141
0
votes
1
answer
91
views
Prefix-disjoint code
A set $C$ of words is a prefix code if no word in $C$ is a proper prefix of any other. Consider the following stronger property $P$: no two distinct words in $C$ have any proper non-empty prefix in ...
- 101
4
votes
1
answer
213
views
Finding Shift-Invariant "Interesting" Elements In Words
I want to find "interesting" elements in a sequence of symbols that are independent of their absolute position in that sequence.
Formally, I have a window size $s \in \mathbb{N}$ and a ...
- 61
3
votes
1
answer
151
views
The smallest periods of the prefixes of the Fibonacci word
I'll start with some definitions to simplify the rest of the message.
Let's denote $f_0 = b, \ f_1 = a, \ f_n = f_{n-1} \cdot f_{n-2}$, where $\cdot$ stands for concatenation of two words. We call $...
- 65
2
votes
1
answer
503
views
What is the maximal length of a CNF formula?
The question is quite short. Let $k$ be a given number. What is the maximal length of $k$-CNF formulae can we compute, over the set of binary variables $\left\{ x_1 ,\ldots, x_n \right\}$?
The way I ...
- 535
0
votes
1
answer
249
views
Find the total no. of strings ( len n ) possible given a set of sets of letters such that no two letter from a single set should be in that string
This was an algorithm problem but I am having problems in formulating it.
I have a certain approach but I do not know how to fully execute:
Given
26 letters in total
All possible strings of length n
...
1
vote
1
answer
51
views
Inductive sequence of words in a biprefix code
Let $X = X_1 \cup X_2$ a code on an alphabet $A$, with $X_1$ a biprefix code and $X_2$ a uniform code, with $m(X_1) < m(X_2)$, i.e. the maximal length of the first is strictly lower than the second....
- 125
1
vote
1
answer
201
views
Maximal prefix codes and maximal length
Let $X$ a maximal prefix code on an alphabet $A$, $m(X)$ its maximal length, $F = X \cap A^{m(X)}$ and $F’ \subseteq A^{m(X)}$. Let $X’ = X \setminus F \cup F’$ a maximal prefix code. Why is it true ...
- 125
1
vote
1
answer
109
views
Must a word be binary (and never unary)?
I understand that a computer memory sequential word must always include at least two bits so it must be binary and therefore cannot be unary.
Must a word be binary (and never unary)?
That is to ask; ...
- 25
1
vote
1
answer
1k
views
Must a Turing machine tape be binary?
I once asked why does computer data bits are usually organized on binary (base 2) sets, rather than on unary (base 1) sets, aiming to also understand why its not also ternary (base 3), heptary (base 7)...
- 25
0
votes
1
answer
85
views
Computing morphic word produced by uniform morphism
Let $\Sigma = \{a,b,c\}$, and consider the function $f\colon \Sigma \to \Sigma^*$ given by $f(a) = abc$, $f(b) = bac$, and $f(c) = cba$. We can extend $f$ to $\Sigma^*$ in the obvious way. Since $f(a)$...
user119506
1
vote
0
answers
95
views
Number of words of length n for special language
Let $\Sigma$ be an alphabet and let $L$ be a language over it with the following properties:
if $w\in L$ then there exists $v\in \Sigma^*$ such that $wv \in L$ and for every $s\in \Sigma$ the word $...
- 61
0
votes
1
answer
116
views
Is my recursive algorithm for Equivalent Words correct?
Here is my problem.
Problem
Given two words and a dictionary, find out whether the words are equivalent.
Input: The dictionary, D (a set of words), and two words v and w from the dictionary.
Output: A ...