scientific article; zbMATH DE number 4080911

zbMATH Open0661.68042MaRDI QIDQ3811706FDOQ3811706

Authors: Oscar H. Ibarra, Tao Jiang, Jik H. Chang, B. Ravikumar 

Publication date: 1988

Title of this publication is not available (Why is that?)

Recommendations

• Some classes of languages in \(NC^ 1\)
• 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
• Formulas, regular languages and Boolean circuits

zbMATH Keywords

context-free languagessemilinear setalternating Turing machine\(NC^ 1\)

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Cited In (8)

• Some subclasses of context-free languages in \(NC^ 1\)
• On the relative complexity of some languages in \(NC^ 1\)
• A note on some languages in uniform \(ACC^ 0\)
• Aspects of Molecular Computing
• Some classes of languages in \(NC^ 1\)
• On the complexity of regular-grammars with integer attributes
• Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties
• On distinguishing \(\mathbf {NC^1}\) and \(\mathbf {NL}\)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3811706)