Return to Answer

Edit: This problem has since been solved (and generalized) by Aleksi Saarela.

Stepan Holub is offering €200 for a solution to the following problem:

Do there exist $n\ge 2$ and nonempty words $u_1,\ldots,u_n$ such that

$(u_1 \ldots u_n)^2 = u_1^2 \ldots u_n^2$ and

$(u_1 \ldots u_n)^3 = u_1^3 \ldots u_n^3$

but the $u_i$ don't all commute with one another?

(I guess the $n\ge 2$ and nonemptiness requirement are technically redundant.)

Source: https://www.student.cs.uwaterloo.ca/~cs462/openproblems.html

New problem from the same page:

Jeffrey Shallit offers \$100 for any significantly improved bounds on the distinguishing strings problem. Which is: Given two words of length at most $n$, what is the size of the smallest DFA that accepts one and rejects the other? Current bounds are that $\Omega(\log n)$ states are needed and $O(n^{2/5} (\log n)^{3/5})$ are sufficient.

(That page also lists a third problem with a monetary award but it has since been claimed so I won't bother listing it here! It was problem 24 there, though.)

Edit: This problem has since been solved (and generalized) by Aleksi Saarela.

Stepan Holub is offering €200 for a solution to the following problem:

Do there exist $n\ge 2$ and nonempty words $u_1,\ldots,u_n$ such that

$(u_1 \ldots u_n)^2 = u_1^2 \ldots u_n^2$ and

$(u_1 \ldots u_n)^3 = u_1^3 \ldots u_n^3$

but the $u_i$ don't all commute with one another?

(I guess the $n\ge 2$ and nonemptiness requirement are technically redundant.)

Source: CS 462/662: Open Problems

New problem from the same page:

Jeffrey Shallit offers \$100 for any significantly improved bounds on the distinguishing strings problem. Which is: Given two words of length at most $n$, what is the size of the smallest DFA that accepts one and rejects the other? Current bounds are that $\Omega(\log n)$ states are needed and $O(n^{2/5} (\log n)^{3/5})$ are sufficient.

(That page also lists a third problem with a monetary award but it has since been claimed so I won't bother listing it here! It was problem 24 there, though.)

Edit: This problem has since been solved (and generalized) by Aleksi Saarela.

Stepan Holub is offering €200 for a solution to the following problem:

Do there exist $n\ge 2$ and nonempty words $u_1,\ldots,u_n$ such that

$(u_1 \ldots u_n)^2 = u_1^2 \ldots u_n^2$ and

$(u_1 \ldots u_n)^3 = u_1^3 \ldots u_n^3$

but the $u_i$ don't all commute with one another?

(I guess the $n\ge 2$ and nonemptiness requirement are technically redundant.)

Source: https://www.student.cs.uwaterloo.ca/~cs462/openproblems.html

Edit: This problem has since been solved (and generalized) by Aleksi Saarela.

Stepan Holub is offering €200 for a solution to the following problem:

Do there exist $n\ge 2$ and nonempty words $u_1,\ldots,u_n$ such that

$(u_1 \ldots u_n)^2 = u_1^2 \ldots u_n^2$ and

$(u_1 \ldots u_n)^3 = u_1^3 \ldots u_n^3$

but the $u_i$ don't all commute with one another?

(I guess the $n\ge 2$ and nonemptiness requirement are technically redundant.)

Source: https://www.student.cs.uwaterloo.ca/~cs462/openproblems.html

New problem from the same page:

Jeffrey Shallit offers \$100 for any significantly improved bounds on the distinguishing strings problem. Which is: Given two words of length at most $n$, what is the size of the smallest DFA that accepts one and rejects the other? Current bounds are that $\Omega(\log n)$ states are needed and $O(n^{2/5} (\log n)^{3/5})$ are sufficient.

(That page also lists a third problem with a monetary award but it has since been claimed so I won't bother listing it here! It was problem 24 there, though.)

Stepan Holub is offering €200 for a solution to the following problem:

Do there exist $n\ge 2$ and nonempty words $u_1,\ldots,u_n$ such that

$(u_1 \ldots u_n)^2 = u_1^2 \ldots u_n^2$ and

$(u_1 \ldots u_n)^3 = u_1^3 \ldots u_n^3$

but the $u_i$ don't all commute with one another?

(I guess the $n\ge 2$ and nonemptiness requirement are technically redundant.)

Source: https://www.student.cs.uwaterloo.ca/~cs462/openproblems.html

Edit: This problem has since been solved (and generalized) by Aleksi Saarela.

Stepan Holub is offering €200 for a solution to the following problem:

Do there exist $n\ge 2$ and nonempty words $u_1,\ldots,u_n$ such that

$(u_1 \ldots u_n)^2 = u_1^2 \ldots u_n^2$ and

$(u_1 \ldots u_n)^3 = u_1^3 \ldots u_n^3$

but the $u_i$ don't all commute with one another?

(I guess the $n\ge 2$ and nonemptiness requirement are technically redundant.)

Source: https://www.student.cs.uwaterloo.ca/~cs462/openproblems.html