On the complexity of properties of partial bijection semigroups

For \(n\in \mathbb{N}\), let \([n]=\{1,\ldots,n\}\). The full transformation semigroup over \([n]\), denoted by \(T_{n}\), is the set of all mappings \[a:[n] \rightarrow [n]\] together with function composition. The full partial bijection semigroup over \([n]\), denoted by \(I_{n}\), is the set of all partial bijective mappings \(a:[n] \rightarrow [n]\), together with function composition. Note that \(I_{n}\) is an inverse semigroup (known as the symmetric inverse semigroup) and that the inverse of \(a\in I_{n}\) is denoted by \(a^{-1}\), that is \(a^{-1}\) is the unique element in \(I_{n}\) such that \(aa^{-1}a=a\) and \(a^{-1}aa^{-1}=a^{-1}\). For elements \(a_{1}, \ldots, a_{r}\) in \(I_{n}\) (or in \(T_{n}\)), let \(\langle a_{1}, \ldots, a_{r}\rangle\) be the subsemigroup of \(I_{n}\) (\(T_{n}\)) generated by \(a_{1}, \ldots, a_{r}\). The analysis in the paper under review reference the following complexity classes:\N\N\begin{itemize}\N\item \(\mathtt{AC}^{0}\) is the class of first-order definable properties.\N\item \(\mathtt{L}\) (\(\mathtt{NL}\)) is the class of sets decidable by a deterministic (nondeterministic) Turing machine using at most logarithmic space.\N\item \(\mathtt{P}\) (\(\mathtt{PSPACE}\)) consist of sets that are decidable by a deterministic Turing machine in polynomial time (space).\N\end{itemize}\NEspecially, the computational complexity of checking some properties in \(\langle a_{1}, \ldots, a_{r}\rangle\) are examined. In particular, it is shown that\N\begin{itemize}\N\item checking if \(\langle a_{1}, \ldots, a_{r}\rangle\) is Clifford is in \(\mathtt{AC}^{0}\),\N\item checking if \(\langle a_{1}, \ldots, a_{r}, a_{1}^{-1}, \ldots, a_{r}^{-1}\rangle\) satisfies a fixed semigroup identity is in \(\mathtt{NL}\) and\N\item checking if \(b\in \langle a_{1}, \ldots, a_{r}\rangle\) is a \(\mathtt{PSPACE}\)-complete problem,\N\end{itemize}\Nwhere \(a_{1}, \ldots, a_{r},b\in I_{n}\) and \(b\) is an idempotent. Moreover, if \(a_{1}, \ldots, a_{r}\in T_{n}\), then it is shown that the identities in \(\langle a_{1}, \ldots, a_{r}\rangle\) can be enumerated in \(\mathtt{AC}^{0}\).

Cites work

This page was built for publication: On the complexity of properties of partial bijection semigroups

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