Institut für Informatik
print
Navigationspfad
Inhaltsbereich

Publikationen

Mein Profil bei Google Scholar und DBLP

Bücher

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

Zeitschriften

  1. Jan Johannsen. Backdoors into Two Occurrences. Journal on Satisfiability, Boolean Modeling and Computation 12, no. 1, pp. 1-15, 2020.
  2. Samuel R. Buss und Jan Johannsen. On Linear Resolution. Journal on Satisfiability, Boolean Modeling and Computation 10, no. 1, pp. 23-35, 2017.
  3. Maria Luisa Bonet, Samuel R. Buss und Jan Johannsen. Improved Separations of Regular Resolution from Clause Learning Proof Systems. Journal of Artificial Intelligence Research 49, pp. 669-703, 2014.
  4. Samuel R. Buss, Jan Hoffmann und Jan Johannsen. Resolution Trees with Lemmas: Resolution Refinements that Characterize DLL-Algorithms with Clause Learning. Logical Methods in Computer Science 4 (4:13), 2008.
  5. Michael Alekhnovich, Jan Johannsen, Toniann Pitassi und Alasdair Urquhart. An exponential separation between regular and general resolution. Theory of Computing 3 article 5, pp. 81-102, 2007.
  6. 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.
  7. Arnold Beckmann und Jan Johannsen. An unexpected separation result in linearly bounded arithmetic. Mathematical Logic Quarterly 51 no. 2 pp. 191--200, 2005.
  8. Klaus Aehlig und 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.
  9. Jan Johannsen. Depth lower bounds for monotone semi-unbounded fan-in circuits. RAIRO Theoretical Informatics and Applications 35 no. 3 pp. 277--286, 2001.
  10. Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi und Jan Johannsen. On the relative complexity of resolution refinements and cutting planes proof systems. SIAM Journal on Computing 30 pp. 1462-1484, 2000.
  11. J. Wolfgang Degen und Jan Johannsen. Cumulative higher-order logic as a foundation for set theory. Mathematical Logic Quarterly 46 pp. 147--170, 2000.
  12. 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.
  13. Jan Johannsen. A remark on independence results for sharply bounded arithmetic. Mathematical Logic Quarterly 44 no. 4 pp. 569--570, 1998.
  14. Jan Johannsen. A model-theoretic property of sharply bounded formulae, with some applications. Mathematical Logic Quarterly 44 no. 2 pp. 205--215, 1998.
  15. Jan Johannsen. A note on sharply bounded arithmetic. Archive for Mathematical Logic 33 pp. 159--165, 1994.

Konferenzen

  1. Marc Vinyals, Jan Elffers, Jan Johannsen und Jakob Nordström. Simplified and Improved Separations Between Regular and General Resolution by Lifting, in: Luca Pulina and Martina Seidl (eds.), Theory and Applications of Satisfiability Testing, 23rd International Conference SAT 2020, Springer LNCS 12178, pp. 182-200, 2020.
  2. Jan Elffers, Jan Johannsen, Massimo Lauria, Thomas Magnard, Jakob Nordström und Marc Vinyals. Trade-Offs between Time and Memory in a Tighter Model of CDCL SAT Solvers, in: Nadia Creignou and Daniel LeBerre (eds.), Theory and Applications of Satisfiability Testing, 19th International Conference SAT 2016, Springer LNCS 9710, pp. 160-176, 2016.
  3. Jan Johannsen. Exponential separations in a hierarchy of clause learning proof systems, in: Matti Järvisalo and Allen van Gelder (eds.), Theory and Applications of Satisfiability Testing, 16th International Conference SAT 2013, Springer LNCS 7962, pp. 40-51, 2013.
  4. Eli Ben-Sasson und Jan Johannsen. Lower Bounds for width-restricted clause learning on formulas of small width, in: Toby Walsh (ed.), Proceedings of the 22nd International Joint Conference on Artificial Intelligence, IJCAI 2011 Best paper track, pp. 2570-2575, 2011.
  5. Eli Ben-Sasson und Jan Johannsen. Lower Bounds for width-restricted clause learning on small width formulas, in: Ofer Strichman and Stefan Szeider (eds.), Theory and Applications of Satisfiability Testing, 13th International Conference SAT 2010, Springer LNCS 6175, pp. 16-29, 2010.
  6. Jan Johannsen. An exponential lower bound for width-restricted clause learning, in: Oliver Kullmann (ed.), Theory and Applications of Satisfiability Testing, 12th International Conference SAT 2009, Springer LNCS 5584, pp. 128-140, 2009.
  7. Hermann Gruber und 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.
  8. Markus Jehle, Jan Johannsen, Martin Lange und 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.
  9. 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.
  10. Jan Johannsen und 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.
  11. Michael Alekhnovich, Jan Johannsen, Toniann Pitassi und 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.
  12. Jan Johannsen und 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.
  13. Klaus Aehlig, Jan Johannsen, Helmut Schwichtenberg und 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.
  14. Jan Johannsen und 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.
  15. 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.
  16. Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi und 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.
  17. 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.
  18. Jan Johannsen und 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.
  19. Jan Johannsen. A bounded arithmetic theory for constant depth threshold circuits. In Petr Hájek, editor, GÖDEL `96, pages 224--234, 1996. Lecture Notes in Logic 6.
  20. Jan Johannsen. On sharply bounded length induction. In Hans Kleine Büning, editor, Computer Science Logic, pages 362--367. Springer, 1996.
  21. 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.

Abschlussarbeiten

  1. Jan Johannsen. Schwache Fragmente der Arithmetik und Schwellwertschaltkreise beschränkter Tiefe. Dissertation, Universität Erlangen-Nürnberg, 1996.
  2. Jan Johannsen. Semantische Vollständigkeit halbformaler Systeme der transfiniten Typentheorie. Diplomarbeit, Universität Erlangen-Nürnberg, 1991.
  3. Jan Johannsen. Kumulative Typenlogik mit einer infinitären Schlußregel. Studienarbeit, Universität Erlangen-Nürnberg, 1990.

Reviews für Mathematical Reviews