Decidability of finite quasivarieties generated by certain transformation semigroups. (Q1771861)

Given a class \(\mathcal C\) of finite semigroups, the least pseudovariety containing \(\mathcal C\) is known to be \({\mathbb H \mathbb S \mathbb P}_{\text{fin}} ({\mathcal C})\). Many famous open problems about formal languages and formal automata lead to the pseudovariety membership problem (PMP): given an effectively described class \(\mathcal C\) of finite semigroups, can the pseudovariety \({\mathbb H \mathbb S \mathbb P}_{\text{fin}} ({\mathcal C})\) be effectively described? A similar problem for the least finite quasivariety \({\mathbb S \mathbb P}_{\text{fin}} ({\mathcal C})\) containing the class \(\mathcal C\), the so-called quasivariety membership problem (QMP), can be formulated analogously. It is known that the answer to some instances of the PMP or QMP is negative. The aim of the paper is to establish a fairly general property of a class \(\mathcal C\) of finite transformation semigroups which ensures that the answer to the QMP is affirmative. This property holds for example for the class of semigroups of total (or partial, or partial injective) order preserving (or decreasing, or decreasing and order-preserving) transformations of a finite chain.