Semigroups arising from asynchronous automata. (Q2016100)

An \textit{asynchronous automaton} is a quadruple \(\mathcal A=(Q,\Sigma,t,o)\) where \(Q\) is a finite set of states, \(\Sigma\) is a finite alphabet, \(t\colon Q\times\Sigma\to Q\) is a transition function and \(o\colon Q\times\Sigma\to\Sigma^*\) is an output function. An asynchronous automaton \(\mathcal A=(Q,\Sigma,t,o)\) one can consider as a directed labelled graph with vertex set \(Q\) and edge from \(q_1\) to \(q_2\) labelled by \(\sigma|w\) if and only if \(t(q_1,\sigma)=q_2\) and \(o(q_1,\sigma)=w\). If an edge of an automaton is labelled by \(\sigma|w\), then \(\sigma\) is called the \textit{input letter} of the edge and \(w\) is called the \textit{output word} of the edge. Each state \(q\in Q\) induces a function \(q\colon\Sigma^*\to\Sigma^*\) in the following way. Let \(w\in\Sigma^*\), that is \(w=\sigma_1\cdots\sigma_n\). Then \(q(w)\) is the word obtained by feeding \(\sigma_1\cdots\sigma_n\) into the automaton as an input path starting at \(q\) and recording the corresponding outputs. Similarly, each state \(q\in Q\) induces a (possibly) partial function \(q^\omega\colon\Sigma^\omega\to\Sigma^\omega\). Given a right-infinite word \(\eta\in\Sigma^\omega\), the word \(q^\omega(\eta)\) is computed as in the previous paragraph. The set \(\{q^\omega\mid q\in Q\}\) is denoted by \(Q^\Omega\). The author suggests the set \(\Sigma^*\) to identify with a regular rooted tree of degree \(|\Sigma|\), where the root vertex is labelled by the empty word \(\emptyset\) and a vertex labelled \(w\) has \(|\Sigma|\) children whose labels are \(w\sigma\) for each \(\sigma\in\Sigma\). Then ``the action of a state \(q\) on \(\Sigma^*\) can be visualized as a transformation of the corresponding tree, where \(q\) sends the vertex \(w\) to the vertex \(q(w)\). The function \(q\) induces a prefix-preserving transformation of \(\Sigma^*\). Furthermore, \(q(\emptyset)=\emptyset\).'' For any asynchronous automaton \(\mathcal A=(Q,\Sigma,t,o)\) there is a natural homomorphism \(\varphi_{\mathcal A}\colon Q^+\to p-pT(\Sigma^*)\), where \(p-pT(\Sigma^*)\) denotes the semigroup of prefix-preserving transformations of \(\Sigma^*\) that fix \(\emptyset\). Similarly, there is a natural homomorphism \(\psi_{\mathcal A}\colon(Q^\Omega)^+\to\text{End\,}\partial(\Sigma^*)\), where \(\text{End\,}\partial(\Sigma^*)\) denotes the semigroup of continuous partial transformations of the boundary of the tree. The set \(\Sigma^\omega\) can be identified with the boundary of the tree corresponding to \(\Sigma^*\). Then \(\Sigma^\omega\) is a metric space with the distance between two rays \(\eta\) and \(\gamma\) defined by \(d(\eta,\gamma)=k^{-|\eta\wedge\gamma|}\), where \(k=|\Sigma|\) and \(|\eta\wedge\gamma|\) is the length of the longest common prefix of \(\eta\) and \(\gamma\). The image of \(\varphi_{\mathcal A}\) is called the \textit{asynchronous automaton semigroup corresponding to \(\mathcal A\)} and denoted by \(S(\mathcal A)\). The image of \(\psi_{\mathcal A}\) is called the \textit{\(\partial\)-asynchronous automaton semigroup corresponding to \(\mathcal A\)} and denoted by \(\partial S(\mathcal A)\). A semigroup \(S\) is called an \textit{asynchronous automaton semigroup} if there exists an asynchronous automaton \(\mathcal A\) with \(S\cong S(\mathcal A)\). An \textit{expanding automaton} is an asynchronous automaton in which the range of the output function is \(\Sigma^+\). In the graphical representation of an expanding automation, \(\emptyset\) is never an output word. A \textit{synchronous automaton} is an asynchronous automaton in which the range of the output function is \(\Sigma\). The author proves the following results. Every free partially commutative monoid is a synchronous automaton semigroup. There is no algorithm that takes as input an asynchronous automaton \(\mathcal A\) over an alphabet \(\Sigma\) and a state \(q\) of \(\mathcal A\) and decides whether or not \(q\) (respectively \(q^\omega\)) has a fixed point in \(\Sigma^*\) (respectively in \(\Sigma^\omega\)). There is an algorithm that takes as input an expanding automaton \(\mathcal A\) and a state \(q\in Q\) and decides whether or not \(q^\omega\) has a fixed point in \(\Sigma^\omega\). Let \(SAS\) denote the class of synchronous automaton semigroups, \(EAS\) denote the class of expanding automaton semigroups, \(AAS\) denote the class of asynchronous automaton semigroups. Then \(SAS\subset EAS\subset AAS\). There are similar other results and some basic algebraic theory of these semigroups, with an emphasis on subgroups.