Complexity Measures for Language Recognition by Canonic Systems

Abstract

A canonic system C is a specification of a recursively enumerable set, such as a set of strings over a finite alphabet. From this description C, it is possible to generate a system C , called a proof measure function, which is an indication of the complexity of the language defined. For certain simple but important classes of canonic system, algebraic bounds on these functions can be derived from the structure of the system.