# Questions tagged [word-combinatorics]

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

41 questions
Filter by
Sorted by
Tagged with
34 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)$...
54 views

66 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 ...
81 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://...
33 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 ...
127 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 ...
39 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 ...
17 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 ...
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? ...
299 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 ...
158 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"....
146 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 ...
59 views

46 views

185 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 ...
109 views

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 ...
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-...
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 ...
808 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 ...
18k 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 ...
616 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. ...
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$ ...
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 ...
### 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 ...
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 ...