dblp.uni-trier.dewww.uni-trier.de

Jan Johannsen Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo
Home Page

*2009
29EEJan Johannsen: An Exponential Lower Bound for Width-Restricted Clause Learning. SAT 2009: 128-140
2008
28EEHermann Gruber, Jan Johannsen: Optimal Lower Bounds on Regular Expression Size Using Communication Complexity. FoSSaCS 2008: 273-286
27EESamuel R. Buss, Jan Hoffmann, Jan Johannsen: Resolution Trees with Lemmas: Resolution Refinements that Characterize DLL Algorithms with Clause Learning CoRR abs/0811.1075: (2008)
26EESamuel R. Buss, Jan Hoffmann, Jan Johannsen: Resolution Trees with Lemmas: Resolution Refinements that Characterize DLL Algorithms with Clause Learning. Logical Methods in Computer Science 4(4): (2008)
2007
25EEMichael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart: An Exponential Separation between Regular and General Resolution. Theory of Computing 3(1): 81-102 (2007)
2006
24EEMarkus Jehle, Jan Johannsen, Martin Lange, Nicolas Rachinsky: Bounded Model Checking for All Regular Properties. Electr. Notes Theor. Comput. Sci. 144(1): 3-18 (2006)
2005
23EEKlaus Aehlig, Jan Johannsen: An elementary fragment of second-order lambda calculus. ACM Trans. Comput. Log. 6(2): 468-480 (2005)
22EEJan Johannsen: The Complexity of Pure Literal Elimination. J. Autom. Reasoning 35(1-3): 89-95 (2005)
21EEArnold Beckmann, Jan Johannsen: An unexpected separation result in Linearly Bounded Arithmetic. Math. Log. Q. 51(2): 191-200 (2005)
2004
20EEJan Johannsen: Satisfiability Problems Complete for Deterministic Logarithmic Space. STACS 2004: 317-325
2003
19EEJan Johannsen, Martin Lange: CTL+ Is Complete for Double Exponential Time. ICALP 2003: 767-775
2002
18EEJan Johannsen, N. S. Narayanaswamy: An Optimal Lower Bound for Resolution with 2-Conjunctions. MFCS 2002: 387-398
17EEMichael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart: An exponential separation between regular and general resolution. STOC 2002: 448-456
16EEKlaus Aehlig, Jan Johannsen: An Elementary Fragment of Second-Order Lambda Calculus CoRR cs.LO/0210022: (2002)
2001
15EEKlaus Aehlig, Jan Johannsen, Helmut Schwichtenberg, Sebastiaan Terwijn: Linear Ramified Higher Type Recursion and Parallel Complexity. Proof Theory in Computer Science 2001: 1-21
14EEMichael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart: An Exponential Separation between Regular and General Resolution Electronic Colloquium on Computational Complexity (ECCC) 8(056): (2001)
13EEJan Johannsen: Depth Lower Bounds for Monotone Semi-Unbounded Fan-in Circuits. ITA 35(3): 277-286 (2001)
2000
12EEWolfgang Degen, Jan Johannsen: Cumulative Higher-Order Logic as a Foundation for Set Theory. Math. Log. Q. 46(2): 147-170 (2000)
11EEMaria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, Jan Johannsen: On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems. SIAM J. Comput. 30(5): 1462-1484 (2000)
1999
10EEJan Johannsen: Weak Bounded Arithmetic, the Diffie-Hellman Problem and Constable's Class K. LICS 1999: 268-274
1998
9EEMaria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, Jan Johannsen: Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems. FOCS 1998: 638-647
8 Jan Johannsen, Chris Pollett: On Proofs about Threshold Circuits and Counting Hierarchies. LICS 1998: 444-452
7EEMaria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, Jan Johannsen: Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems Electronic Colloquium on Computational Complexity (ECCC) 5(35): (1998)
6EEJan Johannsen: Lower Bounds for Monotone Real Circuit Depth and Formula Size and Tree-Like Cutting Planes. Inf. Process. Lett. 67(1): 37-41 (1998)
5 Jan Johannsen: A Model Theoretic Property of Sharply Bounded Formulae, with some Applications. Math. Log. Q. 44: 205-215 (1998)
4 Jan Johannsen: A Remark an Independence Results for Sharply Bounded Arithmetic. Math. Log. Q. 44: 568-570 (1998)
1997
3EEJan Johannsen: Lower Bounds for Monotone Real Circuit Depth and Formula Size and Tree-like Cutting Planes Electronic Colloquium on Computational Complexity (ECCC) 4(32): (1997)
1995
2EEJan Johannsen: On Sharply Bounded Length Induction. CSL 1995: 362-367
1993
1 Jan Johannsen: On the Weakness of Sharply Bounded Polynomial Induction. Kurt Gödel Colloquium 1993: 223-230

Coauthor Index

1Klaus Aehlig [15] [16] [23]
2Michael Alekhnovich [14] [17] [25]
3Arnold Beckmann [21]
4Maria Luisa Bonet [7] [9] [11]
5Samuel R. Buss [26] [27]
6Wolfgang Degen [12]
7Juan Luis Esteban [7] [9] [11]
8Nicola Galesi [7] [9] [11]
9Hermann Gruber [28]
10Jan Hoffmann [26] [27]
11Markus Jehle [24]
12Martin Lange [19] [24]
13N. S. Narayanaswamy [18]
14Toniann Pitassi [14] [17] [25]
15Chris Pollett [8]
16Nicolas Rachinsky [24]
17Helmut Schwichtenberg [15]
18Sebastiaan Terwijn [15]
19Alasdair Urquhart [14] [17] [25]

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)