scientific article; zbMATH DE number 3922988

From MaRDI portal
Publication:3699028





[For the entire collection see Zbl 0549.00009.] Let \(\Sigma\) be a finite nonempty set called an alphabet. An automaton \({\mathcal A}=(Q,i,T)\) over \(\Sigma\) consists of a finite set of states Q, an initial state \(i\in Q\) and a set of terminal states \(T\subseteq Q\) together with a morphism \(\alpha\) of \(\Sigma^*\), the free monoid on \(\Sigma\), into \({\mathcal P}{\mathcal T}(Q)\), the monoid of partial transformation of Q (under composition). For any \(\sigma\in \Sigma\), the image of \(\sigma\) under \(\alpha\) is denoted by \(\alpha_{\sigma}\) and called the action of \(\sigma\) on Q. The range of \(\alpha\), i.e. \(\Sigma^*\alpha\), is denoted by M(\({\mathcal A})\) and called the action monoid of \({\mathcal A}\). The language recognized by an automaton \({\mathcal A}\) is the set of all words \(w\in \Sigma^*\) such that \(i\alpha_ w\in T\). A prefix code is any subset P of \(\Sigma^*\) such that for all \(p,w\in \Sigma^*\), p,pw\(\in P\) implies \(w=1\). A biprefix code is a prefix code whose set of reversed words is also a prefix code. Let \({\mathcal A}=(Q,i,T)\) be an automaton over \(\Sigma\) with actions \(\{\alpha_{\sigma}:\) \(\sigma\in \Sigma \}\) and \({\mathcal B}=(Q',i',T')\) be an automaton over \(\Gamma\) with actions \(\{\beta_{\gamma}:\) \(\gamma\in \Gamma \}\). Then \({\mathcal A}\) is said to simulate \({\mathcal B}\) if Q'\(\subseteq Q\) and for each \(\gamma\in \Gamma\) there is a word \(w(\gamma)\in \Sigma^*\) such that \(\alpha_{w(\gamma)}=\beta_{\gamma}\). For any even integer \(n\geq 4\), the author constructs an automaton \({\mathcal A}\) with \(2n+1\) states which has the following properties: (i) \({\mathcal A}\) is injective and minimal and the language recognized by \({\mathcal A}\) is of the form \(B^*\) where B is a finite biprefix code; (ii) the action monoid M(\({\mathcal A})\) is an inverse semigroup; (iii) \({\mathcal A}\) simulates any injective automaton on \(n+1\) or fewer states, and any inverse semigroup with \(n+1\) or fewer elements is embeddable in M(\({\mathcal A}).\) This is the main result of the paper which has a number of interesting corollaries. The paper is based on the author's talk at the 1984 Marquette Conference on Semigroups and gives a summary of Section 2 of the author's paper [Theor. Comput. Sci. 32, 201-213 (1984; Zbl 0567.68047)].











This page was built for publication:

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