@InProceedings{HN:MFCS05, 
    author    = {Andr\'{e} Hernich and Arfst Nickelsen}, 
    title     = {Combining Self-Reducibility and Partial Information 
                 Algorithms}, 
    booktitle = {Proceedings of the 30th International Symposium on
                 Mathematical Foundations of Computer Science},
    year      = {2005},
    pages     = {483--494},
    editor    = {Joanna J\c{e}drzejowicz and Andrzej Szepietowski},
    series    = {Lecture Notes in Computer Science},
    volume    = {3618},
    publisher = {Springer-Verlag},
    abstract  = {<p>A partial information algorithm for a language <i>A</i> 
                 computes for some fixed <i>m</i> and for input words 
                 <i>x</i><sub>1</sub>, ..., <i>x</i><sub><i>m</i></sub> 
                 a set of bitstrings containing the characteristic string 
                 of <i>x</i><sub>1</sub>, ..., <i>x</i><sub><i>m</i></sub> 
                 with respect to <i>A</i>. 
                 E.g., p-selective, approximable, and easily countable 
                 languages are defined by the existence of 
                 polynomial-time partial information algorithms of 
                 specific type.
                 Self-reducible languages, for different types of 
                 self-reductions, form subclasses of PSPACE.</p>
                 
                 <p>For a self-reducible language <i>A</i>, the existence 
                 of a partial information algorithm sometimes helps to 
                 place <i>A</i> into some subclass of PSPACE.
                 The most prominent known result in this respect is:
                 P-selective languages which are self-reducible are in 
                 P [Buhrman, van Helden, Torenvliet 1993].</p>
                 
                 <p>Closely related is the fact that the existence of a 
                 partial information algorithm for <i>A</i> simplifies 
                 the type of reductions or self-reductions to <i>A</i>.
                 The most prominent known result in this respect is:
                 Turing reductions to easily countable languages 
                 simplify to truth-table reductions [Beigel, Kummer, 
                 Stephan 1995].</p>
                 
                 <p>We prove new results of this type. We show:</p>

                 <ol>
                     <li>Self-reducible languages which are easily 
                         2-countable are in P.
                         This partially confirms a conjecture of 
                         [Beigel, Kummer, Stephan 1995].</li>
                     <li>Self-reducible languages which are 
                         (2<i>m</i>-1,<i>m</i>)-verbose are truth-table
                         self-reducible.
                         This generalizes the result of [Buhrman, van
                         Helden, Torenvliet 1993] for p-selective 
                         languages, which are 
                         (<i>m</i>+1,<i>m</i>)-verbose.</li>
                     <li>Self-reducible languages, where the language 
                         and its complement are strongly 2-membership 
                         comparable, are in P.
                         This generalizes the corresponding result for 
                         p-selective languages of [Buhrman, van Helden,
                         Torenvliet 1993].</li>
                     <li>Disjunctively truth-table self-reducible 
                         languages which are 2-membership comparable 
                         are in UP.</li>
                 </ol>}
}