Questions tagged [word-combinatorics]

Questions about combinatorics on languages of words, that is how many sequences of symbols with certain properties there are.

Filter by
Sorted by
Tagged with
2
votes
1answer
136 views

Hex Word Search Generator Algorithm

I want to create an algorithm to build a hex matrix with given: - max n rows - max m collumns - min t rown - min q collumns containing the specific words from a list: "example", "test", "algorithm"....
5
votes
1answer
92 views

Primitive word and cyclic rotations

Definition. A word $w \in \Sigma^*$ is primitive if $w=u^n \rightarrow n=1$. Is it true that a word is primitive if and only if its all cyclic rotations are dstinct?
7
votes
3answers
125 views

What is language density used for?

If we have a langage $L$ over an alphabet $\Sigma$, then we can defined the density function of $L$ as : $$ p_L(n) = | L \cap \Sigma^n | $$ I am wondering why it’s useful to study this function ...
12
votes
2answers
293 views

Word factorization in $O(n^2 \log n)$ time

Given two strings $S_1, S_2$, we write $S_1S_2$ for their concatenation. Given a string $S$ and integer $k\geq 1$, we write $(S)^k = SS\cdots S$ for the concatenation of $k$ copies of $S$. Now given a ...
6
votes
0answers
77 views

Number of strings at given edit distance

I would like to know the number of strings at edit distance $n$ of a string $s$. I guess this is textbook knowledge... but I cannot find the textbook in question. More formally, I have an alphabet $\...
2
votes
1answer
65 views

Maximal size of a set of ordered words such that no pair of letters occurs twice

Consider an alphabet $\Sigma=\{1,\dots,n\}$. An ordered word is a word $w=w_1w_2\dots w_k\in\Sigma^*$ such that $w_1<w_2<\dots<w_k$. In other words, an ordered word is a strictly increasing ...
5
votes
1answer
73 views

Word Problem over Finite Groupoids

I'm struggling with an interesting problem from a chapter about Dynamic Programming in Skienas' famous "The Algorithm Design Manual". It's listed on the following web-page under number 8-22: http://...
1
vote
1answer
32 views

Get all factors of a word in linear time or constant time

I have the following problem : I have an algorithm which takes a word $w$ as entry. The problem is that my algorithm is doing a lot of things on the factors of $w$ and I am representing $w$ as an ...
2
votes
1answer
36 views

Why every rational langage is the image of a local automaton

I have seen this result but I don’t understand why it’s true : Every rational language is the image of a local language by a morphism : $\phi : \Sigma^{*’} \to \Sigma^*$ I know what a local ...
4
votes
1answer
16 views

Don’t understanding argument on words of a certain form

In my book they use the following argument which I don’t understand : Let $L$ be a langage such that there is $m_1, ..., m_k \in \Sigma^*$ such that $ L \subset m_1^*...m_k^*$. Now choose the ...
4
votes
2answers
73 views

Why are we interested in square-free words?

There is wikipedia page about square-free words, and there are a lot of theorems about these words, and examples of infinite square-free words. I am wondering: why are we interested in these words? ...
-3
votes
1answer
322 views

Is the set of all strings over a finite alphabet finite? [closed]

Suppose $Σ=\{0,1\}$; then $Σ^*$ is the set of all strings over $Σ$. Is $Σ^*$ over $Σ$ finte?
5
votes
1answer
142 views

Permutation of words that have matched parentheses

Let $L$ denote the (context-free) language of matched parentheses over the alphabet $\Sigma$. Consider the following problem: Input: words $x_1,\dots,x_n \in \Sigma^*$ Question: does there exist a ...
1
vote
1answer
59 views

Number of words in $\{pi,po\}^*$ of length at most 9

I have a language $L^*$ for $L = \{pi,po\}$ (I think pi counts as one letter and po also as one letter otherwise a max length of 9 is not possible). The question is how many words I can make with $L^*...
1
vote
2answers
136 views

Proving that $xy=yx$ iff $x^2y^2=z^2$

I was given the following problem as homework: Let $x$, $y$ be words over an alphabet $Σ$. Prove that $xy = yx$ iff there exists a word $z$ such that $x^2y^2 = z^2$. I was hinted that I am ...
0
votes
2answers
381 views

Ordered Cartesian Product

Say I have three sets: A = [banana, apple, grape] B = [1, 2, 3, 4] C = [Alice, Bob, Carol] I need to design an algorithm that gives me the Cartesian Product A ...
2
votes
1answer
113 views

Expressing the language of squares as a concatenation of two languages

Can the language $L = \{ vv : v \in \Sigma^* \}$ be expressed as the concatenation of two nontrivial languages? (A language is nontrivial if it differs from $\{\epsilon\}$.)
0
votes
2answers
602 views

Given the alphabet $\{a, b, c\}$, how many words can we form with 4 letters?

Question: Given the alphabet $\{a, b, c\}$, how many words can we form with 4 letters? And how many words can we form with up to 4 letters? I was thinking about the logic behind this and came up with ...
2
votes
0answers
91 views

Given a permutation of n integers, how fast can a corresponding Standard Young's Tableau be created?

The Schensted insertion algorithm has an $O(n^2)$ running time, for constructing such a standard Young's Tableaux. But, since every permutation has a unique Young's tableau, there seems no reason as ...
2
votes
1answer
62 views

How many restricted length strings are there without significant repetitions

Let us fix an alphabet $\Sigma$ of size $c$, then we have the finite language $\Sigma^n$ which is the set of all $n$ length words. For each $N,M$ how many words are there in $\Sigma^n$ such that no ...
0
votes
1answer
61 views

Finding alternative way of combinatorial counting

The question is related to databases: There is a relation $R(A_1,A_2,...,A_n)$. Every $(n-2)$ attributes of $R$ forms candidate key. Number of superkeys of $R$ are? I thought if any one of the $(n-...
6
votes
0answers
80 views

What is longest string with no equidistant pairs of equal characters for a given alphabet?

Given a finite alphabet $A$ with $|A|=n$, what is the largest $l$ so that a string $s=a_1...a_l$ of length $l$ exists with $a_i\in A$ so that there is no $i,j,d$ with $i\neq j, d > 0$ so that $a_i =...
2
votes
1answer
44 views

What is the closest result relating perfect shuffle closure of primitive words?

A perfect shuffle of two words $u=a_{1}a_{2} \cdots a_{n}$ and $v=b_{1}b_{2} \cdots b_{n}$ where $a_{i}$'s and $b_{j}$'s are letters from the alphabet $\Sigma$ is defined as $u \diamond v=a_{1}b_{1} \...
2
votes
2answers
70 views

How should i guide a program to perform correct things? [closed]

I want to make a small model of A.I. which can learn itself. I am inspired by 1000+ monkey theorem which states that if 1000+ monkey bangs a keyboard for enough long, then they will eventually produce ...
3
votes
1answer
170 views

Number of words within Hamming distance $\delta$

This is a problem I'm having reading Arora & Barak's book, page 378-379. They define: For two words $x, y \in \{0, 1\}^m$, the fractional Hamming distance of $x$ and $y$ is equal to the ...
4
votes
1answer
109 views

How many words are in this sets?

I have problems to determine the size of the following sets in dependancy of the parameters $m, n>0$: $$M_{m,n}=\{a^iwa^{m-i}\mid 0\le i \le m,\;w\in\{a,b\}^n\}$$ It is easy to see that $|M_{m,n}|\...
-1
votes
0answers
246 views

Prove $y'w'v'u'x' = xuvwy$ [duplicate]

This question repeats one that was closed. Let $x, u, v, w, y, x', u', v', w', y'$ be words satisfying $y'x' = xy$. $y'u'x' = xuy$. $y'v'x' = xvy$. $y'w'x' = xwy$. $y'v'u'x' = xuvy$. $y'w'v'x' = ...
3
votes
1answer
40 views

Lexicographical position of a string in its type class

I have the following problem: Given a string $x\in\{1,...,M\}^+$ of length $n$. Let $S$ be the set of all words with exactly the same numbers of occurences of smybols as in $x$. In fact, $S$ consists ...
2
votes
2answers
1k views

How Dynamic programming can be used for Coin Change problem?

As far as I can unserstand Dynamic programming stands simply for memoization (which is a fancy name for lazy evaluation or plain "caching"). Now, I read that there is we can reduce complexity of coin-...
15
votes
2answers
2k views

Number of words of a given length in a regular language

Is there an algebraic characterization of the number of words of a given length in a regular language? Wikipedia states a result somewhat imprecisely: For any regular language $L$ there exist ...
1
vote
1answer
124 views

The language of all borderless words

Could anyone help me please to find who was the first person who has proved that the language of all borderless words is not regular and when was that? Could you mention the reference, please? A word ...
17
votes
3answers
838 views

Number of words in the regular language $(00)^*$

According to Wikipedia, for any regular language $L$ there exist constants $\lambda_1,\ldots,\lambda_k$ and polynomials $p_1(x),\ldots,p_k(x)$ such that for every $n$ the number $s_L(n)$ of words of ...
6
votes
4answers
791 views

What is the number of expressions containing n pairs of matching brackets with nesting limit?

I know the answer without nesting limit is the Catalan number. My question is, specifically, is there a recurrence relation that gives the number of expression containing $n$ pairs of matching ...
4
votes
2answers
17k views

Finding the number of distinct permutations of length N with n different symbols

I have one puzzle whose answer I have boiled down to finding the total number and which type of permutation they are. For example if the string is of length ten as $w = aabbbaabba$, the total number ...
7
votes
2answers
599 views

How many strings are close to a given set of strings?

This question has been prompted by Efficient data structures for building a fast spell checker. Given two strings $u,v$, we say they are $k$-close if their Damerau–Levenshtein distance¹ is small, i.e. ...
8
votes
1answer
250 views

What is a formula for the number of strings with no repeats?

I want to count the number of strings $s$ over a finite alphabet $A$, that contain no repeats, and by that I mean for any substring $t$ of $s$, $1< |t| < |s|$, there is no disjoint copy of $t$ ...
21
votes
1answer
490 views

Does every large enough string have repeats?

Let $\Sigma$ be some finite set of characters of fixed size. Let $\alpha$ be some string over $\Sigma$. We say that a nonempty substring $\beta$ of $\alpha$ is a repeat if $\beta = \gamma \gamma$ for ...