Abstract families of relations

摘要

A generalization of an abstract family of languages—abstract family of relations (AFR)—is introduced and its special cases are considered. The properties of AFR's and their special cases and their relation to abstract families of languages are studied. Many known formal schemes for description of language translations are shown to define AFRs. As an application of the concept of AFR, it is shown that the class of mappings defined by any finitely encodable abstract family of transducers can be generated from a single language over a 2-letter alphabet by pairs of finite state transductions.