syntactic semigroup

syntactic semigroup

[sin′tak·tik ′sem·i‚grüp]
(systems engineering)
For a sequential machine, the set of all transformations performed by all input sequences.
References in periodicals archive ?
n] is most complex in its class under the following measures of complexity: the size of the syntactic semigroup, the quotient complexities of the left quotients of [L.
n] meet the upper bounds for the size of the syntactic semigroup, the quotient complexities of left quotients, the number of atoms (intersections of complemented and uncomplemented left quotients), the quotient complexities of the atoms, and the quotient complexities of the following operations: reversal, star, product (concatenation), and all binary boolean operations.
L] is a semigroup called the syntactic semigroup of L.
For regular right ideals, a four-letter alphabet was necessary to achieve this, because fewer than four letters are not sufficient for the size of the syntactic semigroup to be maximal.
It was shown in [10] that the syntactic semigroup of a left ideal of complexity n has cardinality at most [n.
It was shown in [10] that the syntactic semigroup of a two-sided ideal of complexity n has cardinality at most [n.