Lehr- und Forschungseinheit für Theoretische Informatik,
Institut für Informatik der Ludwig-Maximilians-Universität München

Jan Johannsen's Publications

Books, Journal Articles, Conference Articles, Reviews, Other Publications.

Submitted Articles

  1. Samuel R. Buss, Jan Hoffmann and Jan Johannsen. Weak Resolution Trees with Lemmas: Resolution Refinements that Characterize DLL-Algorithms with Clause Learning. Submitted for publication, 2008.

Books

  1. Arnold Beckmann and Jan Johannsen. Bounded Arithmetic and Resolution-Based Proof Systems. Collegium Logicum Volume 7, KGS Vienna, 2004. ISBN 3-901546-02-2. Citations

Journal Articles

  1. Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, and Alasdair Urquhart. An exponential separation between regular and general resolution. Theory of Computing 3 article 5, pp. 81-102, 2007. Citations
  2. Jan Johannsen. The complexity of pure literal elimination. Journal of Automated Reasoning 35 No. 1-3, special issue on SAT 2005, pp. 88-95, 2005.
  3. Arnold Beckmann and Jan Johannsen. An unexpected separation result in linearly bounded arithmetic. Mathematical Logic Quarterly 51 no. 2 pp. 191--200, 2005.
  4. Klaus Aehlig and Jan Johannsen. An elementary fragment of second-order lambda calculus. ACM Transactions on Computational Logic 6 no. 2, 2005. Preliminary version available on CoRR as cs.LO/0210022. Citations
  5. Jan Johannsen. Depth lower bounds for monotone semi-unbounded fan-in circuits. RAIRO Theoretical Informatics and Applications 35 no. 3 pp. 277--286, 2001.
  6. Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, and Jan Johannsen. On the relative complexity of resolution refinements and cutting planes proof systems. SIAM Journal on Computing 30 pp. 1462-1484, 2000. Citations
  7. J. Wolfgang Degen and Jan Johannsen. Cumulative higher-order logic as a foundation for set theory. Mathematical Logic Quarterly 46 pp. 147--170, 2000.
  8. Jan Johannsen. Lower bounds for monotone real circuit depth and formula size and tree-like cutting planes. Information Processing Letters 67 pp. 37--41, 1998. Citations
  9. Jan Johannsen. A remark on independence results for sharply bounded arithmetic. Mathematical Logic Quarterly 44 no. 4 pp. 569--570, 1998. Citations
  10. Jan Johannsen. A model-theoretic property of sharply bounded formulae, with some applications. Mathematical Logic Quarterly 44 no. 2 pp. 205--215, 1998. Citations
  11. Jan Johannsen. A note on sharply bounded arithmetic. Archive for Mathematical Logic 33 pp. 159--165, 1994. Citations

Conference Articles

  1. Hermann Gruber and Jan Johannsen. Optimal lower bounds on regular expression size using communication complexity, in: Roberto Amadio (ed.): Foundations of Software Science and Computational Structures, 11th Intl. Conference FOSSACS 2008, Springer LNCS 4962, pp. 273-286, 2008. Citations
  2. Markus Jehle, Jan Johannsen, Martin Lange and Nicolas Rachinsky. Bounded model checking for all regular properties, Proceedings of the third International Workshop on Bounded Model Checking (BMC 2005), Electronic Notes in Theoretical Computer Science 144 no. 1, pp. 1-92. Citations
  3. Jan Johannsen. Satisfiability problems complete for deterministic logarithmic space. In: Volker Diekert and Michel Habib (eds.): STACS 2004, 21st Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. Springer LNCS 2996, pp. 317-325, 2004. Citations
  4. Jan Johannsen and Martin Lange. CTL+ is complete for double exponential time. In: J. C. M. Baeten et al., editors, Proc. 30th Int. Coll. on Automata, Logics and Programming (ICALP'03), Springer LNCS 2719, pp. 767-775, 2003. Citations
  5. Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, and Alasdair Urquhart. An exponential separation between regular and general resolution. In Proceedings of the 34th ACM Symposium on Theory of Computing (STOC), pages 448--456, 2002. Citations
  6. Jan Johannsen and N. S. Narayanaswamy. An optimal lower bound for resolution with 2-conjunctions. In Krzysztof Diks and Wojciech Rytter, editors, Mathematical Foundations of Computer Science 2002, Springer LNCS 2420, pages 387--398, 2002.
  7. Klaus Aehlig, Jan Johannsen, Helmut Schwichtenberg, and Sebastiaan A. Terwijn. Linear ramified higher type recursion and parallel complexity. In Reinhard Kahle, Peter Schröder-Heister, and Robert Stärk, editors, Proof Theory in Computer Science, pages 1--21. Springer LNCS 2183, 2001. Citations
  8. Jan Johannsen and Chris Pollett. On the Δb1-bit-comprehension rule. In Sam Buss, Petr Hájek, and Pavel Pudlák, editors, Logic Colloquium 98, pages 262--279. ASL Lecture Notes in Logic, 2000. Citations
  9. Jan Johannsen. Weak bounded arithmetic, the Diffie-Hellman problem, and Constable's class K. In Proc. 14th IEEE Symposium on Logic in Computer Science, pages 268--274, 1999. Citations
  10. Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, and Jan Johannsen. Exponential separations between restricted resolution and cutting planes proof systems. In Proc. 39th Symposium on Foundations of Computer Science, pages 638--647, 1998. Citations
  11. Jan Johannsen. Equational calculi and constant-depth propositional proofs. In Paul Beame and Samuel R. Buss, editors, Proof Complexity and Feasible Arithmetics, pages 149--162. AMS DIMACS Series Vol. 39, 1998. Citations
  12. Jan Johannsen and Chris Pollett. On proofs about threshold circuits and counting hierarchies (extended abstract). In Proc. 13th IEEE Symposium on Logic in Computer Science, pages 444--452, 1998. Citations
  13. Jan Johannsen. A bounded arithmetic theory for constant depth threshold circuits. In Petr Hájek, editor, GÖDEL `96, pages 224--234, 1996. Springer Lecture Notes in Logic 6. Citations
  14. Jan Johannsen. On sharply bounded length induction. In Hans Kleine Büning, editor, Computer Science Logic, pages 362--367. Springer, 1996.
  15. Jan Johannsen. On the weakness of sharply bounded polynomial induction. In Georg Gottlob, Alexander Leitsch, and Daniele Mundici, editors, Computational Logic and Proof Theory, pages 223--230. Springer LNCS 713, 1993. Citations

Reviews

  1. Review of Grzegorz Herman, Tim Paterson and Michael Soltys: A propositional proof system with quantification over permutations. Mathematical Reviews MR2346238.
  2. Review of Joost J. Joosten: Propositional proof systems and fast consistency provers. Mathematical Reviews MR2336354.
  3. Review of Jan Krajícek, Alan Skelley and Neil Thapen: NP search problems in low fragments of bounded arithmetic. Mathematical Reviews MR2320295.
  4. Review of Satoru Kuroda: Generalized quantifier and a bounded arithmetic theory for LOGCFL. Mathematical Reviews MR2321590 (2008e:03102).
  5. Review of Emil Jerábek: The strength of sharply bounded induction. Mathematical Reviews MR2282404 (2007k:03160).
  6. Review of Arnold Beckmann: Generalised Dynamic Ordinals - universal measures for implicit computational complexity. Mathematical Reviews MR2258702 (2007k:03160).
  7. Review of Michael Soltys: LA, permutations, and the Hajós Calculus. Mathematical Reviews MR2181385 (2006h:03053)
  8. Review of Arnold Beckmann: Uniform proof complexity. Mathematical Reviews MR2157726 (2006d:03102)

Other Publications

  1. Jan Johannsen. Schwache Fragmente der Arithmetik und Schwellwertschaltkreise beschränkter Tiefe. PhD thesis, Universität Erlangen-Nürnberg, 1996. Citations
  2. Jan Johannsen. Semantische Vollständigkeit halbformaler Systeme der transfiniten Typentheorie. Diploma Thesis, Universität Erlangen-Nürnberg, 1991.
  3. Jan Johannsen. Kumulative Typenlogik mit einer infinitären Schlußregel. Student project, Universität Erlangen-Nüurnberg, 1990.
Home Page          TCS          Computer Science Institute          University