Some classes of languages in NC^ 1

DOI10.1016/0890-5401(91)90061-6MaRDI QIDQ756426zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

parallel complexitycontextfree languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Distributed algorithms (68W15)

Recommendations

• scientific article; zbMATH DE number 4080911
• Some subclasses of context-free languages in NC^ 1
• On the relative complexity of some languages in \(NC^ 1\)
• \(NC^ 1\): The automata-theoretic viewpoint
• scientific article; zbMATH DE number 4041256

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 ¹
• 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)