Formulas, regular languages and boolean circuits

AbstractThis article surveys the links between regular languages and the class NC1, showing their importance in the classification of the fine structure of this parallel complexity class. Logical characterizations of these two classes are given in which the only difference lies in the use of arbitrary numerical predicates in the circuit case. It is also shown that there is a unique maximal class of numerical predicates which allows us to define only regular languages. Several characterizations of this class are given