scientific article; zbMATH DE number 4080911

MaRDI QIDQ3811706zbMATH OpenFDO

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

Publication date 1988

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)

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

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)