Some classes of languages in NC^ 1
From MaRDI portal
Publication:756426
DOI10.1016/0890-5401(91)90061-6zbMATH Open0722.68057OpenAlexW2071346095MaRDI QIDQ756426FDOQ756426
Authors: Oscar H. Ibarra, Tao Jiang, Jik H. Chang, B. Ravikumar 
Publication date: 1991
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0890-5401(91)90061-6
Recommendations
Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Distributed algorithms (68W15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- On uniform circuit complexity
- Reversal-bounded multipushdown machines
- A taxonomy of problems with fast parallel algorithms
- Reversal-Bounded Multicounter Machines and Their Decision Problems
- Alternation
- Title not available (Why is that?)
- Title not available (Why is that?)
- The complexity of decision problems for finite-turn multicounter machines
- P-uniform circuit complexity
- Some subclasses of context-free languages in \(NC^ 1\)
- A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
- On tape-bounded complexity classes and multihead finite automata
- The complexity of the equivalence problem for two characterizations of Presburger sets
- A note on semilinear sets and bounded-reversal multihead pushdown automata
- A useful device for showing the solvability of some decision problems
- Language recognition by marking automata
- One-way simple multihead finite automata are not closed under concatenation
- An extension of Savitch's theorem to small space bounds
- Space bounds for processing contentless inputs
- Lower bounds on space complexity for contextfree recognition
- One-way simple multihead finite automata
- A characterization of semilinear sets
- Bounds to Complexities of Networks for Sorting and for Switching
- Eine untere Schranke für den Platzbedarf bei der Analyse beschränkter kontextfreier Sprachen
- An NP-Complete Number-Theoretic Problem
- Multi-tape and multi-head pushdown automata
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
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- On uniformity within \(NC^ 1\)
- On distinguishing \(\mathbf {NC^1}\) and \(\mathbf {NL}\)
- Title not available (Why is that?)
- 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)
