On Nonpermutational Transformation Semigroups with an Application to Syntactic Complexity

Authors

  • Szabolcs Iván
  • Judit Nagy-György

DOI:

https://doi.org/10.14232/actacyb.22.3.2016.9

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.

Downloads

Download data is not yet available.

Downloads

Published

2016-01-01

How to Cite

Iván, S., & Nagy-György, J. (2016). On Nonpermutational Transformation Semigroups with an Application to Syntactic Complexity. Acta Cybernetica, 22(3), 687–701. https://doi.org/10.14232/actacyb.22.3.2016.9

Issue

Section

Regular articles