On nonpermutational transformation semigroups with an application to syntactic complexity

Abstract

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.

arXiv admin note: substantial text overlap with arXiv:1304.5714

Cited by in corpus (3)

• Checking Whether an Automaton Is Monotonic Is NP-complete
• Large Aperiodic Semigroups
• Syntactic complexity of bifix-free languages