A prime decomposition theorem for grammatical families

摘要

Two basic operations on families of languages, in general, and grammatical families, in particular, are sum (formed by taking unions of member languages) and product (formed by taking unions of pairwise products of member languages). In this paper, a grammatical family is defined to be prime if it is contained in one of two grammatical families whenever it is contained in their product, and the following Prime Decomposition Theorem is then established: Every grammatical family can be represented as a minimal sum of products of primes in a unique way.This theorem leads to a general method for decomposing a grammatical family into simpler ones. A subsequent paper uses this method to obtain a decision procedure for determining whether two grammar forms generate the same grammatical family, as well as a canonical representation for grammatical families.