On real-time cellular automata and trellis automata (Q790615)

A subset X of a free monoid \(A^*\) is said to be unavoidable if all but finitely many words in \(A^*\) contain some word of X as a subword, i.e., if \(A^*\)-\(A^*XA^*\) is finite. This notion has been introduced by \textit{A. Ehrenfeucht}, \textit{D. Haussler} and \textit{G. Rozenberg} in their paper ''On regularity of context free languages'' [Theor. Comput. Sci. 27, 311-332 (1983)] where a generalization of Higman's theorem on the well quasi order defined by the subsequence embedding is given. We consider in our paper the following conjecture, usually attributed to Ehrenfeucht and Haussler: Every unavoidable set X is extendible in the sense that there exist \(x\in X\) and \(a\in A\) such that \((X-\{x\})\cup \{xa\}\) is itself unavoidable. We prove the conjecture for two particular cases. The first one consists in assuming that X contains a word which is ''large'' compared to all others. This enables us to prove that the two way version of the conjecture (i.e. having the possibility of extending to the right or to the left) is equivalent to the above conjecture. In the second case we consider a letter \(a\in A\) and a power \(a^ n\) belonging to \(X\) (such a power exists if \(X\) is unavoidable) and states under which conditions \((X-\{a^ n\})\cup \{a^{n+1}\}\) is unavoidable. A reduction results establishes that the conjecture needs only be proven in the case where \(A\) is a two letter alphabet. We propose a representation of finite sets (every unavoidable set has a finite subset which is unavoidable) by means of finite automata and show how the basic properties of unavoidability, extendibility and minimality (as unavoidable set) can be easily tested.