SYNCHRONIZATION FUNCTIONS OF SYNCHRONIZED CONTEXT-FREE GRAMMARS AND LANGUAGES

摘要

Synchronization functions are introduced to measure the amount of communication necessary to generate synchronized context-free (SCF) languages. The family of SCF languages with a bounded synchronization function equals the family of context-free languages and for non-context-free SCF languages, the synchronization function is proven to be at least linear and at most quadratic. Examples of SCF grammars with synchronization functions that are linear, quadratic and strictly between linear and quadratic are provided.