3
$\begingroup$

We encountered this question as an exercise in a Büchi automata book a couple of decades ago, and back then gave a few tries thinking that it should be easy. But haven't seen a solution. My friend Deepak helped me with the problem statement, here it is:

Given a DFA $A = (Q,Letters,\delta,Final)$ with $n$ states, each letter $a$ induces a function $f_a: Q \to Q$, given by $f_a(q) = \delta(q,a)$. A word $w$, by extension, also induces a function $f_w : Q \to Q$.

The problem was to show that for any $w$, we can find a $w'$ of length $\leq n!$, such that $f_{w'} = f_w$.

Wondering if there is any bound on the word length, even if not a $n!$ (like $n^n$).

$\endgroup$
  • 1
    $\begingroup$ The $n^n$ version is easy to get by repeatedly using the pigeonhole principle on the prefixes of $w$. $\endgroup$ – Klaus Draeger Oct 15 '14 at 17:07
3
$\begingroup$

The following argument works as long as $f_w$ is injective. The same ideas should also work for general $f_w$. Indeed, below I show how they give a bound $|w| \leq O(n!)$. However, even further down I show a much better bound, $|w| \leq e^{2(1+o(1))\sqrt{n\log n}}$, which is tight up to the constant $2$.

Consider some word $w$ which is the minimal length word resulting in $f_w$, and suppose that the range of $f_w$ is $Q$. We want to show that $|w| \leq n!$. Let $w_{\leq i}$ denote the prefix of $w$ of length $i$. If $f_{w_{\leq i}} = f_{w_{\leq j}}$ for some $i < j$ then $f_{w_{\leq i} w_{>j}} = f_w$, contradicting the assumption that $w$ has minimal length. We conclude that $f_{w_{\leq i}}$ is different for all $i$. Since the range of $f_w$ is full, all $f_{w_{\leq i}}$ must be permutations of $Q$. Since there are $n!$ permutations of $Q$, we conclude that $|w| \leq n!-1$.

Suppose now that $f_w$ is not injective, and write $w = x_1\ldots x_k$, where each step passing from $x_i$ to $x_{i+1}$ decreases the image. The same argument as before shows that $|x_1| \leq n!$, $|x_2| \leq n!/1!$, $|x_3| \leq n!/2!$, and so on. In total, we get that $|w| \leq n!(1+1+1/2+1/6+\cdots) \leq e n!$.

We can do slightly better. For example, if $f_{x_1}(q_1) = f_{x_2}(q_2)$ then when bounding $x_1$, it is enough to consider permutations up to a permutation of the images of $q_1$ and $q_2$, and so when $k \geq 2$ we can conclude that $|x_1| \leq n!/2$. This argument probably gives $|w| \leq (3/2)n!$. One can probably push the argument further, but that would require looking across the boundaries of the segmentation $w=x_1\ldots x_k$.


The following construction shows that $n!-1$ cannot be replaced by anything smaller than roughly $e^{\sqrt{n\log n}}$. Landau's function $g(n)$ is the maximal order of an element in $S_n$. It is known that $g(n) = e^{(1\pm o(1))\sqrt{n\log n}}$. Given an element $\pi \in S_n$ of maximal order, we can construct an automaton over the one language alphabet $\{a\}$ in which $Q = \{1,\ldots,n\}$ and $f_a = \pi$. The word $a^{g(n)-1}$, which generates the permutation $\pi^{-1}$, cannot be shortened.


Consider again the case of injective $f_w$. We can think of the letters of $w$ as generating a subgroup of $S_n$. Babai and Seress show that the diameter of the corresponding Cayley graph is at most $e^{(1+o(1)) \sqrt{n\log n}}$. This means that every permutation in the subgroup, including $f_w$, can be written as a word over the letters of $w$ and their inverses of length at most $e^{(1+o(1)) \sqrt{n\log n}}$. Since the order of each permutation is at most $e^{(1+o(1))\sqrt{n\log n}}$, we can replace the inverse of each letter by at most $e^{(1+o(1))\sqrt{n\log n}}$ copies of itself, obtaining a word of length $e^{2(1+o(1))\sqrt{n\log n}}$. This bound can perhaps be improved by looking at the construction of Babai and Seress.

In the general case, segment $w=x_1\ldots x_k$ as before, where $k \leq n$. A similar argument shows that $|x_i| \leq e^{2(1+o(1))\sqrt{n\log n}}$, and so $|w| \leq e^{2(1+o(1))\sqrt{n\log n}}$.


This still leaves open the value of the smallest $\ell(n)$ such that the minimal word $w$ with given $f_w$ has length at most $\ell(n)$. Our arguments show that $e^{(1+o(1))\sqrt{n\log n}} \leq \ell(n) \leq e^{2(1+o(1))\sqrt{n\log n}}$, leaving a small gap.

$\endgroup$
  • $\begingroup$ Thank you for the wonderful argument... am I right in saying that the bound established is then (3/2)n! ? $\endgroup$ – zrini Oct 16 '14 at 0:17
  • $\begingroup$ Yes, though the methods can probably be pushed further. There's also an asymptotically much better bound of $e^{2(1+o(1))\sqrt{n\log n}}$ which I also prove. This bound is almost optimal, since there is a lower bound of $e^{(1+o(1))(\sqrt{n\log n})}$. $\endgroup$ – Yuval Filmus Oct 16 '14 at 1:58
  • $\begingroup$ While I completely agree with your derivation of the upper bound for $\ell(n)$ in the group case, I can't agree that the similar arguments also work for the general case. Consider, for example, a DFA that has the states $Q=\{0, 1,\ldots, n\}$ and the input alphabet $A=\{a_1,\ldots,a_m\}$, where $m=\binom{n}{k}-1$. Suppose that all the $k$-subsets $Q_1,\ldots,Q_k$ of $\{1,\ldots, n\}$ are lexicographically ordered and $a_i$ sends $Q_i$ to $Q_{i+1}$ while sending all other states to $0$. In this case the function $f_w$, $w=a_1\ldots a_m$, can not be obtained by a shorter word $w'$. $\endgroup$ – Pavel Panteleev Nov 30 '14 at 0:11
  • $\begingroup$ @Pavel Thanks, that always happens when details aren't written down in full... $\endgroup$ – Yuval Filmus Nov 30 '14 at 0:12
4
$\begingroup$

The question is quite old. To the best of my knowledge this problem was first considered in 1976 by Sokolovskii [1], where it was proved that: for the group case ($f_w$ is a permutation) the upper bound is $n!^{\frac12(1+o(1))}$ and the lower bound is $\mathrm{e}^{\sqrt{n\ln n}(1+o(1))}$; for the general case the upper bound is $n^{\frac{n}{2}(1+o(1)))}$ and the lower bound is $\Omega(2^n/\sqrt{n})$.

Much later in 2003 this problem was also independently of Sokolovskii considered among many other problems in [2] by Salomaa but the results were weaker then in the Sokolovskii's paper. In 2006 Babai [3] obtained an optimal upper bound $\mathrm{e}^{\sqrt{n\ln n}(1+o(1))}$ for the group case.

For the general case an optimal estimate $2^n\mathrm{e}^{\sqrt{\frac{n}{2}\ln n}(1+o(1))}$ was obtained in my resent paper [4] accepted for publication in the forthcoming LATA 2015 proceedings.

[1] Sokolovskii, M.N.: The complexity of the generation of transformations, and experiments with automata. In: Discrete analysis methods in the theory of codes and schemes, vol. 29, pp. 68-86. Institute of Mathematics, Siberian. Branch USSR Acad. Sci. (1976), (in Russian)

[2] Salomaa, A.: Composition sequences for functions over a fi nite domain. Theoret. Comput. Sci. 292, 263-281 (2003)

[3] Babai, L.: On the diameter of eulerian orientations of graphs. In: SODA06: proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithms. pp. 822-831. ACM, New York, NY, USA (2006)

[4] Panteleev, P.: Preset Distinguishing Sequences and Diameter of Transformation Semigroups, (accepted for publication in LATA 2015)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.