Ausgabe 1/2010
Special Issue: Symposium on Computer Science, Guest Editors: Sergei Artemov, Volker Diekert and Dima Grigoriev
Inhalt (9 Artikel)
Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth
Artur Jeż, Alexander Okhotin
Equivalence Problems for Circuits over Sets of Natural Numbers
Christian Glaßer, Katrin Herr, Christian Reitwießner, Stephen Travers, Matthias Waldherr
Maximal Intersection Queries in Randomized Input Models
Benjamin Hoffmann, Mikhail Lifshits, Yury Lifshits, Dirk Nowotka
Efficient Algorithms for Sparse Cyclotomic Integer Zero Testing
Qi Cheng, Sergey P. Tarasov, Mikhail N. Vyalyi
Open Access
Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible?
Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolay Vereshchagin