Questions tagged [word-combinatorics]

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

7 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6
votes
0answers
78 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 $\...
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 =...
5
votes
0answers
78 views

Growth function for non-regular languages

For language $L$ over an alphabet $\Sigma$ denote $\gamma_L(n)$ as the number of words of length $n$ in the language $L$. It is known that for regular languages this function represents a sequence ...
2
votes
1answer
139 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"....
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 ...
1
vote
0answers
42 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 $...
0
votes
1answer
28 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 ...