On nonpermutational transformation semigroups with an application to syntactic complexity
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...
Elmentve itt :
| Szerzők: | |
|---|---|
| Dokumentumtípus: | Cikk |
| Megjelent: |
2016
|
| Sorozat: | Acta cybernetica
22 No. 3 |
| Kulcsszavak: | Programozás - szintaxis |
| Tárgyszavak: | |
| doi: | 10.14232/actacyb.22.3.2016.9 |
| Online Access: | http://acta.bibl.u-szeged.hu/40270 |
| Tartalmi kivonat: | 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. |
|---|---|
| Terjedelem/Fizikai jellemzők: | 687-701 |
| ISSN: | 0324-721X |