scientific article; zbMATH DE number 3922988
[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)].
- Inverse semigroups of partial automaton permutations.
- scientific article; zbMATH DE number 2223017
- scientific article; zbMATH DE number 4201646
- scientific article; zbMATH DE number 3897234
- Inverse semigroups with certain types of partial automorphism monoids
- An instruction sequence semigroup with involutive anti-automorphisms
- scientific article; zbMATH DE number 988807
- Inverse semigroups and extensions of groups by semilattices
- scientific article; zbMATH DE number 4130683
- Automaton semigroups
- Biprefix codes, inverse semigroups and syntactic monoids of injective automata
- scientific article; zbMATH DE number 3848616 (Why is no real title available?)
- scientific article; zbMATH DE number 4201646 (Why is no real title available?)
- scientific article; zbMATH DE number 2070396 (Why is no real title available?)
- Abelian Invertible Automata
- scientific article; zbMATH DE number 3894483 (Why is no real title available?)
- scientific article; zbMATH DE number 2223017 (Why is no real title available?)
- Inverse automata and profinite topologies on a free group
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)