Semigroups arising from asynchronous automata.

Free semigroups, generators and relations, word problems (20M05) Semigroups of transformations, relations, partitions, etc. (20M20) Semigroups in automata theory, linguistics, etc. (20M35) Algebraic theory of languages and automata (68Q70)

Abstract: We introduce a new class of semigroups arising from a restricted class of asynchronous automata. We call these semigroups "expanding automaton semigroups." We show that the class of synchronous automaton semigroups is strictly contained in the class of expanding automaton semigroups, and that the class of expanding automaton semigroups is strictly contained in the class of asynchronous automaton semigroups. We investigate the dynamics of expanding automaton semigroups acting on regular rooted trees, and show that undecidability arises in these actions. We show that this class is not closed under taking normal ideal extensions, but the class of asynchronous automaton semigroups is closed under taking these extensions. We construct every free partially commutative monoid as a synchronous automaton semigroup.

Review text

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.

Recommendations

Cites work

Cited in

(10)

This page was built for publication: Semigroups arising from asynchronous automata.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2016100)