Some classes of languages in NC^ 1
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.
- A characterization of semilinear sets
- A note on semilinear sets and bounded-reversal multihead pushdown automata
- A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
- A taxonomy of problems with fast parallel algorithms
- A useful device for showing the solvability of some decision problems
- Alternation
- An extension of Savitch's theorem to small space bounds
- An NP-Complete Number-Theoretic Problem
- Bounds to Complexities of Networks for Sorting and for Switching
- Eine untere Schranke für den Platzbedarf bei der Analyse beschränkter kontextfreier Sprachen
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3639163 (Why is no real title available?)
- scientific article; zbMATH DE number 3428547 (Why is no real title available?)
- scientific article; zbMATH DE number 3293666 (Why is no real title available?)
- Language recognition by marking automata
- Lower bounds on space complexity for contextfree recognition
- Multi-tape and multi-head pushdown automata
- On tape-bounded complexity classes and multihead finite automata
- On uniform circuit complexity
- One-way simple multihead finite automata
- One-way simple multihead finite automata are not closed under concatenation
- P-uniform circuit complexity
- Reversal-Bounded Multicounter Machines and Their Decision Problems
- Reversal-bounded multipushdown machines
- Some subclasses of context-free languages in NC^ 1
- Space bounds for processing contentless inputs
- The complexity of decision problems for finite-turn multicounter machines
- The complexity of the equivalence problem for two characterizations of Presburger sets
- Some subclasses of context-free languages in NC^ 1
- On the relative complexity of some languages in \(NC^ 1\)
- On the parallel complexity of loops
- On uniformity within \(NC^ 1\)
- Visibly counter languages and the structure of \(\mathrm {NC}^{1}\)
- A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
- On distinguishing \(\mathbf {NC^1}\) and \(\mathbf {NL}\)
- Arithmetizing Classes Around NC 1 and L
- scientific article; zbMATH DE number 4070311 (Why is no real title available?)
- scientific article; zbMATH DE number 4080911 (Why is no real title available?)
- Finite monoids and the fine structure of NC 1
- scientific article; zbMATH DE number 4117877 (Why is no real title available?)
- \(NC^ 1\): The automata-theoretic viewpoint
This page was built for publication: Some classes of languages in \(NC^ 1\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q756426)
