On the relative complexity of some languages in NC^ 1
From MaRDI portal
Publication:1124355
DOI10.1016/0020-0190(89)90052-5zbMATH Open0678.68065OpenAlexW1968327120MaRDI QIDQ1124355FDOQ1124355
Authors: David A. Mix Barrington, James C. Corbett 
Publication date: 1989
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(89)90052-5
Recommendations
- scientific article; zbMATH DE number 4080911
- Some classes of languages in \(NC^ 1\)
- Nonuniform complexity and the randomness of certain complete languages
- On asymptotic estimates of the complexity of circuit realization of languages
- Nondeterministic complexity of operations on closed and ideal languages
- Complexity of certain decision problems about congruential languages
- On complexity classes and algorithmically random languages (extended abstract)
- On the cover complexity of finite languages
- Nondeterministic complexity in subclasses of convex languages
- On the complexity of decidable cases of the commutation problem of languages
Formal languages and automata (68Q45) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- On uniform circuit complexity
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Parity, circuits, and the polynomial-time hierarchy
- Parallel computation with threshold functions
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Finite monoids and the fine structure of NC 1
- Some subclasses of context-free languages in \(NC^ 1\)
- On the Tape Complexity of Deterministic Context-Free Languages
- Constant Depth Reducibility
- Language recognition by marking automata
- Title not available (Why is that?)
Cited In (10)
- Extensions of an idea of McNaughton
- Title not available (Why is that?)
- Circuit complexity before the dawn of the new millennium
- Some subclasses of context-free languages in \(NC^ 1\)
- Circuits and expressions with nonassociative gates
- The parallel complexity of two problems on concurrency
- Title not available (Why is that?)
- Some classes of languages in \(NC^ 1\)
- On uniformity within \(NC^ 1\)
- First-order logics: some characterizations and closure properties
This page was built for publication: On the relative complexity of some languages in \(NC^ 1\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1124355)
