On real-time cellular automata and trellis automata
type: Item
instance of: scholarly article
title: On real-time cellular automata and trellis automata
zbMATH Open document ID: 0534.68039
DOI: 10.1007/BF00264617
published in: Acta Informatica
publication date: 1984-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q80
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3848618
zbMATH Keywords: combinatorics on words
zbMATH Keywords: free monoid
zbMATH Keywords: unavoidable set X
author: Christian Choffrut
author: Karel II Culik
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1007/bf00264617
OpenAlex ID: W2078011493
description: scientific article; zbMATH DE number 3848618