
Accession Number : AD0704813
Title : AFL WITH THE SEMILINEAR PROPERTY,
Corporate Author : SYSTEM DEVELOPMENT CORP SANTA MONICA CALIF
Personal Author(s) : Ginsburg,Seymour ; Spanier,Edwin H.
Report Date : 10 FEB 1970
Pagination or Media Count : 58
Abstract : 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 the 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 (1) there exists a largest slip AFL and (2) if L is a slip family then the smallest AFL containing the commutative closure of L 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. (Author)
Descriptors : (*PROGRAMMING LANGUAGES, MATHEMATICAL MODELS), (*COMPUTATIONAL LINGUISTICS, SET THEORY), AUTOMATA, MAPPING(TRANSFORMATIONS), THEOREMS
Subject Categories : Linguistics
Computer Programming and Software
Distribution Statement : APPROVED FOR PUBLIC RELEASE