Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [word-combinatorics]

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

5
votes
0answers
44 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
53 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
58 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
30 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 ...
6
votes
3answers
89 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 ...
2
votes
1answer
30 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 ...
3
votes
2answers
68 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? ...
12
votes
2answers
246 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 ...
1
vote
1answer
72 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
123 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
56 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
110 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
288 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
96 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
153 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
89 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 ...
0
votes
1answer
59 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-...
2
votes
1answer
42 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 ...
6
votes
0answers
76 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 =...
3
votes
1answer
127 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
105 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}|\...
-3
votes
1answer
139 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?
2
votes
1answer
58 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 ...
-1
votes
0answers
232 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
38 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
967 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-...
1
vote
1answer
110 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 ...
6
votes
4answers
719 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 ...
3
votes
2answers
16k 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
534 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
235 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$ ...
15
votes
2answers
1k 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 ...
16
votes
3answers
747 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 ...
20
votes
1answer
448 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 ...