pith. sign in

arxiv: 1402.7289 · v1 · pith:2DMKDLT6new · submitted 2014-02-28 · 💻 cs.FL

On nonpermutational transformation semigroups with an application to syntactic complexity

classification 💻 cs.FL
keywords applicationboundcomplexitynonpermutationalsyntacticupperconsistingdefinite
0
0 comments X
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.