On nonpermutational transformation semigroups with an application to syntactic complexity
classification
💻 cs.FL
keywords
applicationboundcomplexitynonpermutationalsyntacticupperconsistingdefinite
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.