2
$\begingroup$

Suppose we have a deterministic complete finite automaton which is synchronized, meaning we have a reset word, i.e. a word which resets the automaton to a definite state, regardless from which state we start. Suppose further that the underlying digraph (i.e. the graph which we get when forgetting the labels on the transitions) is Eulerian, meaning that the outdegree equals the indegree at each vertex. Then do you know any (preferable elementary) proof of the following statement:

For every proper subset of the state set of the automaton, there exists a word whose inverse image (i.e. the set of states that are mapped to the given state set under the word) is larger in cardinality as the given set.

The property that the digraph is Eulerian gives that the automaton is strongly connected, and the common value of the outdegree and the indegree equals the size of the alphabet. So, if we denote the state set by $Q$, the alphabet by $\Sigma$ and the state transition function by $\delta : Q \times \Sigma \to Q$, then as the digraph is Eulerian we have for $T \subseteq Q$ and with $\delta^{-1}(T, x) := \{ q \in Q : \delta(q, x) \in T \}$ for $x \in \Sigma$ that $$ \sum_{x \in \Sigma} |\delta^{-1}(T, x)| = |\Sigma||T|. $$ because these are two ways to count the number of incoming edges. Now this gives that for every $T \subseteq Q$ we have exactly one of the two cases $$ \forall x \in \Sigma : |\delta^{-1}(T, x)| = |T| \qquad \mbox{or} \qquad \exists x \in \Sigma : |\delta^{-1}(T, x)| > |T|. $$ This observation might be of help. The above statement written more formal:

For every proper subset $T \subseteq Q$, there exits a word $w \in \Sigma^{\ast}$ such that $|\delta^{-1}(T, w)| > |T|$.

Improve this question
$\endgroup$
2
  • $\begingroup$ This can be found in Karl's paper. It is also in Chapter 15 of my book on representations of monoids. It is easy linear algebra using that the ask ones vector is an eigenvector for the adjancency matrix. $\endgroup$
    – Benjamin Steinberg
    Commented Mar 23, 2018 at 21:39
  • $\begingroup$ The proof of theorem 4 of my paper arxiv.org/pdf/0910.0410.pdf gives a more general result. $\endgroup$
    – Benjamin Steinberg
    Commented Mar 23, 2018 at 21:43

1 Answer 1

Reset to default
2
$\begingroup$

This is proved in Section 4 of Kari's paper here.

Essentially the same proof is in chapter 15 of my book the Representation Theory of Finite Monoids done from a more representation theoretic viewpoint. The main trick is to use ascending chain condition of vector spaces and that if a collection is ever less than its average than it also exceeds its average.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thanks for your answer. Actually I know the paper by Kari, sorry if I did not mentioned this. The whole story is that I read a Master thesis freely avaible titled "Synchronising Automata and a conjecture of Cerny" by Peter J. Walker, and in it (Corollary 2.4.2) this is mentioned as if it would be trivial. But after seeing Kari's paper I saw this Linear Algebra argument. Surely, its simple Linear algebra, but somehow I have the impression that is kind of magic argumenting with vectors that no longer represent actual state sets (which happens in Kari's argument). $\endgroup$
    – StefanH
    Commented Mar 24, 2018 at 12:44
  • $\begingroup$ So I looked for a more combinatorial argument, without using higher algebraic mechanisms. But I was unable to come up with one, so I asked here. If you know any proof along that line please share it! $\endgroup$
    – StefanH
    Commented Mar 24, 2018 at 12:45
  • $\begingroup$ I don't know of any proof not using linear algebra. I $\endgroup$
    – Benjamin Steinberg
    Commented Mar 24, 2018 at 12:46
  • $\begingroup$ Most of the more difficult Cerny proofs use linear algebra. $\endgroup$
    – Benjamin Steinberg
    Commented Mar 24, 2018 at 12:48
  • $\begingroup$ Usually one uses linear algebra to get a word of a certain length under whose preimage T changes size and then uses an averaging argument to find a word making the pre-image larger. $\endgroup$
    – Benjamin Steinberg
    Commented Mar 24, 2018 at 12:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .