Extremal Binary PFAs in a Cerny Family

The largest known reset thresholds for DFAs are equal to (n-1)^2, where n is the number of states. This is conjectured to be the maximum possible. PFAs (with partial transition function) can have exponentially large reset thresholds. This is still true if we restrict to binary PFAs. However, asymptotics do not give conclusions for fixed n. We prove that the maximal reset threshold for binary PFAs is strictly greater than (n-1)^2 if and only if n > 5. These results are mostly based on the analysis of synchronizing word lengths for a certain family of binary PFAs. This family has the following properties: it contains the well-known Cerny automata; for n < 11 it contains a binary PFA with maximal possible reset threshold; for all n > 5 it contains a PFA with reset threshold larger than the maximum known for DFAs. Analysis of this family reveals remarkable patterns involving the Fibonacci numbers and related sequences such as the Padovan sequence. We derive explicit formulas for the reset thresholds in terms of these recurrent sequences. Furthermore, we prove that the family asymptotically still gives reset thresholds of polynomial order.

Solving Shisen-Sho boards

We give a simple proof of that determining solvability of Shisen-Sho boards is NP-complete. Furthermore, we show that under realistic assumptions, one can compute in logarithmic time if two tiles form a playable pair. We combine an implementation of the algoritm to test playability of pairs with my earlier algorithm to solve Mahjong Solitaire boards with peeking, to obtain an algorithm to solve Shisen-Sho boards. We sample several Shisen-Sho and Mahjong Solitaire layouts for solvability for Shisen-Sho and Mahjong Solitaire.

Slowly synchronizing DFAs of 7 states and maximal slowly synchronizing DFAs

We compute all synchronizing DFAs with 7 states and synchronization length >= 29. Furthermore, we compute alphabet size ranges for maximal, minimal and semi-minimal synchronizing DFAs with up to 7 states.

A short proof of a theorem of J.-E. Pin

We give a short proof of a theorem of J.-E. Pin (theorem 1.1 below), which can be found in his thesis.

Subset synchronization of DFAs and PFAs, and some other results

This paper contains results which arose from the research which led to arXiv:1801.10436, but which did not fit in arXiv:1801.10436. So arXiv:1801.10436 contains the highlight results, but there are more results which are interesting enough to be shared.

Quadratic homogeneous polynomial maps $H$ and Keller maps $x+H$ with $rk JH=3$

We classify all quadratic homogeneous polynomial maps $H$ and Keller maps of the form $x + H$, for which $rk J H = 3$, over a field $K$ of arbitrary characteristic. In particular, we show that such a Keller map (up to a square part if $char K=2$) is a tame automorphism.

Classification of cubic homogeneous polynomial maps with Jacobian matrices of rank two

Let $K$ be any field with $textup{char}K eq 2,3$. We classify all cubic homogeneous polynomial maps $H$ over $K$ with $textup{rk} JHleq 2$. In particular, we show that, for such an $H$, if $F=x+H$ is a Keller map then $F$ is invertible, and furthermore $F$ is tame if the dimension $n eq 4$.

Lower Bounds for Synchronizing Word Lengths in Partial Automata

It was conjectured by v{C}erny in 1964, that a synchronizing DFA on $n$ states always has a synchronizing word of length at most $(n-1)^2$, and he gave a sequence of DFAs for which this bound is reached. Until now a full analysis of all DFAs reaching this bound was only given for $n leq 5$, and with bounds on the number of symbols for $n leq 12$. Here we give the full analysis for $n leq 7$, without bounds on the number of symbols. For PFAs (partial automata) on $leq 7$ states we do a similar analysis as for DFAs and find the maximal shortest synchronizing word lengths, exceeding $(n-1)^2$ for $n geq 4$. Where DFAs with long synchronization typically have very few symbols, for PFAs we observe that more symbols may increase the synchronizing word length. For PFAs on $leq 10$ states and two symbols we investigate all occurring synchronizing word lengths. We give series of PFAs on two and three symbols, reaching the maximal possible length for some small values of $n$. For $n=6,7,8,9$, the construction on two symbols is the unique one reaching the maximal length. For both series the growth is faster than $(n-1)^2$, although still quadratic. Based on string rewriting, for arbitrary size we construct a PFA on three symbols with exponential shortest synchronizing word length, giving significantly better bounds than earlier exponential constructions. We give a transformation of this PFA to a PFA on two symbols keeping exponential shortest synchronizing word length, yielding a better bound than applying a similar known transformation. Both PFAs are transitive. Finally, we show that exponential lengths are even possible with just one single undefined transition, again with transitive constructions.

Quadratic homogeneous polynomial maps $H$ and Keller maps $x+H$ with $3 le {rm rk} J H le 4$

We compute by hand all quadratic homogeneous polynomial maps $H$ and all Keller maps of the form $x + H$, for which ${rm rk} J H = 3$, over a field of arbitrary characteristic. Furthermore, we use computer support to compute Keller maps of the form $x + H$ with ${rm rk} J H = 4$, namely: $bullet$ all such maps in dimension $5$ over fields with $frac12$; $bullet$ all such maps in dimension $6$ over fields without $frac12$. We use these results to prove the following over fields of arbitrary characteristic: for Keller maps $x + H$ for which ${rm rk} J H le 4$, the rows of $J H$ are dependent over the base field.

The classification of some polynomial maps with nilpotent Jacobians

In the paper, we first classify all polynomial maps $H$ of the following form: $H=big(H_1(x_1,x_2,ldots,x_n),H_2(x_1,x_2),H_3(x_1,x_2),ldots,H_n(x_1,x_2)big)$ with $JH$ nilpotent. After that, we generalize the structure of $H$ to $H=big(H_1(x_1,x_2,ldots,x_n),H_2(x_1,x_2),H_3(x_1,x_2,H_1),ldots,H_n(x_1,x_2,H_1)big)$.