Some classes of languages in \(NC^ 1\)
From MaRDI portal
Publication:756426
DOI10.1016/0890-5401(91)90061-6zbMath0722.68057OpenAlexW2071346095MaRDI QIDQ756426
Jik H. Chang, Tao Jiang, Oscar H. Ibarra, Bala 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
Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Distributed algorithms (68W15)
Related Items (2)
On the parallel complexity of loops ⋮ A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- One-way simple multihead finite automata are not closed under concatenation
- Some subclasses of context-free languages in \(NC^ 1\)
- The complexity of the equivalence problem for two characterizations of Presburger sets
- An extension of Savitch's theorem to small space bounds
- The complexity of decision problems for finite-turn multicounter machines
- On uniform circuit complexity
- A note on semilinear sets and bounded-reversal multihead pushdown automata
- On tape-bounded complexity classes and multihead finite automata
- Space bounds for processing contentless inputs
- Reversal-bounded multipushdown machines
- A useful device for showing the solvability of some decision problems
- Lower bounds on space complexity for contextfree recognition
- One-way simple multihead finite automata
- A characterization of semilinear sets
- P-uniform circuit complexity
- A taxonomy of problems with fast parallel algorithms
- Alternation
- A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
- Bounds to Complexities of Networks for Sorting and for Switching
- Reversal-Bounded Multicounter Machines and Their Decision Problems
- 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
- Language recognition by marking automata
This page was built for publication: Some classes of languages in \(NC^ 1\)
