On the relative complexity of some languages in NC^ 1

DOI10.1016/0020-0190(89)90052-5MaRDI QIDQ1124355zbMATHOpenAlexFDO

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

zbMATH Keywords

computational complexityformal languages\(NC^ 1\)

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity of computation (including implicit computational complexity) (03D15)

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

Cites work

• scientific article; zbMATH DE number 3988712 (Why is no real title available?)
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Constant Depth Reducibility
• Finite monoids and the fine structure of NC ¹
• Language recognition by marking automata
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• On the Tape Complexity of Deterministic Context-Free Languages
• On uniform circuit complexity
• Parallel computation with threshold functions
• Parity, circuits, and the polynomial-time hierarchy
• Some subclasses of context-free languages in \(NC^ 1\)
• \(\Sigma_ 1^ 1\)-formulae on finite structures

Cited in

(11)

• scientific article; zbMATH DE number 4080911 (Why is no real title available?)
• Visibly counter languages and the structure of \(\mathrm {NC}^{1}\)
• Some subclasses of context-free languages in \(NC^ 1\)
• Some classes of languages in \(NC^ 1\)
• First-order logics: some characterizations and closure properties
• Circuits and expressions with nonassociative gates
• On uniformity within \(NC^ 1\)
• Extensions of an idea of McNaughton
• scientific article; zbMATH DE number 6970796 (Why is no real title available?)
• Circuit complexity before the dawn of the new millennium
• The parallel complexity of two problems on concurrency

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)