Some classes of languages in \(NC^ 1\)
type: Item
instance of: scholarly article
title: Some classes of languages in \(NC^ 1\)
zbMATH Open document ID: 0722.68057
DOI: 10.1016/0890-5401(91)90061-6
author: Oscar H. Ibarra
author: Tao Jiang
author: Jik H. Chang
author: B. Ravikumar
published in: Information and Computation
publication date: 1991-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68W15
zbMATH DE Number: 4191118
zbMATH Keywords: parallel complexity
zbMATH Keywords: contextfree languages
reviewed by: Helmut Alt
MaRDI profile type: Publication
full work available at URL: 0890-5401(91)90061-6
OpenAlex ID: W2071346095
cites work: P-uniform circuit complexity
cites work: Eine untere Schranke für den Platzbedarf bei der Analyse beschränkter kontextfreier Sprachen
cites work: Lower bounds on space complexity for contextfree recognition
cites work: Reversal-bounded multipushdown machines
cites work: Alternation
cites work: A taxonomy of problems with fast parallel algorithms
cites work: One-way simple multihead finite automata are not closed under concatenation
cites work: Space bounds for processing contentless inputs
cites work: Q5576254
cites work: An NP-Complete Number-Theoretic Problem
cites work: The complexity of the equivalence problem for two characterizations of Presburger sets
cites work: The complexity of decision problems for finite-turn multicounter machines
cites work: Multi-tape and multi-head pushdown automata
cites work: Q4198075
cites work: Q3862379
cites work: A note on semilinear sets and bounded-reversal multihead pushdown automata
cites work: A useful device for showing the solvability of some decision problems
cites work: Reversal-Bounded Multicounter Machines and Their Decision Problems
cites work: Some subclasses of context-free languages in \(NC^ 1\)
cites work: One-way simple multihead finite automata
cites work: Q5180413
cites work: A characterization of semilinear sets
cites work: Bounds to Complexities of Networks for Sorting and for Switching
cites work: On uniform circuit complexity
cites work: Language recognition by marking automata
cites work: On tape-bounded complexity classes and multihead finite automata
cites work: A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
cites work: An extension of Savitch's theorem to small space bounds
description: scientific article; zbMATH DE number 4191118