scientific article; zbMATH DE number 4024792

MaRDI QIDQ3766852zbMATH OpenFDO

Authors Birgit Jenner, Bernd Kirsig, Klaus-Jörn Lange

Publication date 1987

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• [[:Publication:1118407|The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^Template:\mathcal L=A\Pi_ 2^Template:\mathcal L\)]]
• scientific article; zbMATH DE number 45125
• Publication:4725752
• A hierarchy that does not collapse : alternations in low level space
• Sublogarithmic $\sum _2$-space is not closed under complement and other separation results

Cited in

(5)

• [[:Publication:1118407|The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^Template:\mathcal L=A\Pi_ 2^Template:\mathcal L\)]]
• Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata
• scientific article; zbMATH DE number 1775408 (Why is no real title available?)
• scientific article; zbMATH DE number 3999297 (Why is no real title available?)
• Regular expressions with backreferences and lookaheads capture NLOG

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 Q3766852)