On uniformity within NC/sup 1/
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
The study of circuit complexity classes within NC/sup 1/ in a uniform setting requires a uniformity condition that is more restrictive than those in common use. Two such conditions, stricter than NC/sup 1/ uniformity, have appeared in recent research. It is shown that the two notions are equivalent, leading to a natural notion of uniformity for low-level circuit complexity classes, and that recent results on the structure of NC/sup 1/ still hold true in this very uniform setting. A parallel notion of uniformity, still more restrictive, that is based on the regular languages is investigated. Characterizations of subclasses of the regular languages based on their logical expressibility are given.Keywords
This publication has 0 references indexed in Scilit: