AFL with the semilinear property

摘要

A slip language is a language whose Parikh mapping is a semilinear set. A slip family is a family containing only slip languages. The purpose of this paper is to study slip AFL. A sufficiency condition is given on a slip family which ensures that the family generates a slip AFL. Using this condition, it is proved that (i) there exists a largest slip AFL and (ii) if ℒ is a slip family, then the smallest AFL containing the commutative closure of ℒ is a slip AFL. A new operation called “homomorphic replication” is then introduced. It is shown that the smallest AFL containing a homomorphic replication of a slip AFL is also a slip AFL. Furthermore, the resulting AFL is principal if the original AFL is principal. It is then proved that the smallest AFL containing all homomorphic replications of the regular sets is not principal. Finally, abstract families of acceptors are presented which, respectively, define the smallest AFL containing a particular homomorphic replication of the regular sets and all homomorphic replications of the regular sets.