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. |