×

On nonpermutational transformation semigroups with an application to syntactic complexity. (English) Zbl 1363.20059

Summary: We give an upper bound of \(n((n-1)!-(n-3)!)\) for the possible largest size of a subsemigroup of the full transformational semigroup over \(n\) elements consisting only of nonpermutational transformations. As an application we gain the same upper bound for the syntactic complexity of (generalized) definite languages as well.

MSC:

20M20 Semigroups of transformations, relations, partitions, etc.
68Q70 Algebraic theory of languages and automata
68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.