Some classes of languages in \(NC^ 1\) (Q756426): Difference between revisions

The article considers the relationship of the class \(NC^ 1\) of problems solvable by uniform Boolean circuit families of polynomial size and logarithmic depth with subclasses of contextfree languages and some space complexity classes. In particular the following language classes are shown to be subclasses of \(NC^ 1:\) semilinear sets given in binary encoding, bounded contextfree languages, languages accepted by deterministic one-reversal counter machines, bounded languages that are in NSPACE(\(\sqrt{\log n})\). In addition closure properties of the class \(NC^ 1\) are shown, such as the closure under inverse homomorphisms and marked Kleene closure.