Some classes of languages in NC^ 1
From MaRDI portal
Publication:756426
Recommendations
Cites work
- 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?)
- A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
- A characterization of semilinear sets
- A note on semilinear sets and bounded-reversal multihead pushdown automata
- A taxonomy of problems with fast parallel algorithms
- A useful device for showing the solvability of some decision problems
- Alternation
- An NP-Complete Number-Theoretic Problem
- An extension of Savitch's theorem to small space bounds
- Bounds to Complexities of Networks for Sorting and for Switching
- Eine untere Schranke für den Platzbedarf bei der Analyse beschränkter kontextfreier Sprachen
- 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
Cited in
(13)- A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
- Some subclasses of context-free languages in NC^ 1
- \(NC^ 1\): The automata-theoretic viewpoint
- scientific article; zbMATH DE number 4070311 (Why is no real title available?)
- On the relative complexity of some languages in \(NC^ 1\)
- Visibly counter languages and the structure of \(\mathrm {NC}^{1}\)
- Finite monoids and the fine structure of NC 1
- Arithmetizing Classes Around NC 1 and L
- scientific article; zbMATH DE number 4080911 (Why is no real title available?)
- On uniformity within \(NC^ 1\)
- On distinguishing \(\mathbf {NC^1}\) and \(\mathbf {NL}\)
- scientific article; zbMATH DE number 4117877 (Why is no real title available?)
- On the parallel complexity of loops
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)