Publications

1. N. Creignou, J. Schmidt, M. Thomas
   Complexity of Propositional Abduction for Restricted Sets of Boolean Functions;
   Proc. of the 12th International Conference on the Principles of Knowledge Representation and Reasoning, 2010. To appear.
2. O.Beyersdorff, A. Meier, M. Thomas, H. Vollmer
   The Complexity of Propositional Implication;
   Information Processing Letters, 2009.© 2009 Elsevier
3. M. Thomas
   The Complexity of Circumscriptive Inference in Post's Lattice
   Proc. 10th International Conference on Logic Programming and Nonmonotonic Reasoning, Springer Lecture Notes in Computer Science, 2009. © Springer-Verlag.
4. A. Meier, M. Mundhenk, T. Schneider, M. Thomas, V. Weber, F. Weiss
   The Complexity of Satisfiability for Fragments of Hybrid Logic — Part I
   Proc. 34st International Symposium on Mathematical Foundations of Computer Science, Springer Lecture Notes in Computer Science, 2009. © Springer-Verlag.
5. O. Beyersdorff, A. Meier, M. Mundhenk, T. Schneider, M.Thomas, H. Vollmer
   Model Checking CTL is Almost Always Inherently Sequential
   Proc. 16th International Symposium on Temporal Representation and Reasoning, IEEE Computer Society Press, 2009.
6. N. Creignou, Ph. Kolaitis, H. Vollmer (Eds.)
   Complexity of Constraints;
   Volume 5250 of Lecture Notes in Computer Science, Springer Verlag, 2009.
7. N. Creignou, H. Vollmer
   Boolean constraint satisfaction problems: When does Post’s lattice help?
   In N. Creignou, Ph. Kolaitis, H. Vollmer (Eds.). Complexity of Constraints. Volume 5250 of Lecture Notes in Computer Science, Springer Verlag, 2009, pp. 3–37.
8. E. Allender, M. Bauland, N. Immerman, H. Schnoor, H. Vollmer
   The complexity of satisfiability problems: refining Schaefer's theorem;
   Journal of Computer and System Sciences 75(4): 245–254, 2009.
9. O. Beyersdorff, A. Meier, M. Thomas, H. Vollmer
   The Complexity of Reasoning for Fragments of Default Logic;
   Proc. of the 12th International Conference on Theory and Applications of Satisfiability Testing, Springer Lecture Notes in Computer Science, 2009. © Springer-Verlag.
10. M. Bauland, T. Schneider, H. Schnoor, I. Schnoor, H. Vollmer
    The Complexity of Generalized Satisfiability for Linear Temporal Logic;
    Logical Methods in Computer Science 5(1):1–21, 2009.
11. H. Vollmer
    The complexity of deciding if a Boolean function can be computed by Boolean circuits over a restricted base.
    Theory of Computing Systems 44:82–90, 2009.
12. A. Meier, M. Mundhenk, M. Thomas, H. Vollmer
    The Complexity of Satisfiability for Fragments of CTL and CTL*;
    Proc. of the 2nd Workshop on Reachability Problems, Electronic Notes in Theoretical Computer Science (ENTCS), 2008. © ScienceDirect.
13. P. McKenzie, M. Thomas, H. Vollmer
    Extensional Uniformity for Boolean Circuits;
    Proc. 17th Conference on Computer Science Logic, Springer Lecture Notes in Computer Science, 2008. © Springer-Verlag.
14. J. Kontinen, H. Vollmer
    On Second-Order Monadic Groupoidal Quantifiers;
    Proceedings Workshop on Logic, Language, Information and Computation, Springer Lecture Notes in Computer Science, 2008.
15. B. Vöcking, H. Alt, M. Dietzfelbinger, R. Reischuk, C. Scheideler, H. Vollmer, D. Wagner (Eds.)
    Taschenbuch der Algorithmen;
    Springer Verlag, 2008.
16. M. Bauland, M. Mundhenk, T. Schneider, H. Schnoor, I. Schnoor, H. Vollmer
    The Tractability of Model-Checking for LTL: The Good, the Bad, and the Ugly Fragments
    Electronic Notes in Theoretical Computer Science (ENTCS) 231:277-292, 2009. © ScienceDirect.
17. H. Vollmer
    Computational Complexity of Constraint Satisfaction;
    Proceedings Computability in Europe 2007, Springer Lecture Notes in Computer Science © Springer-Verlag.
18. M. Bauland, E. Böhler, N. Creignou, S. Reith, H. Schnoor, H. Vollmer
    The complexity of problems for quantified constraints;
    Electronic Colloquium on Computational Complexity, TR 07-023, 2007.
    To appear in Theory of Computing Systems.
19. P. McKenzie, T. Schwentick, D. Therien, H. Vollmer.
    The many faces of a translation.
    Journal of Computer and Systems Sciences 72:163–179, 2006.
    
20. F. Steimann, H. Vollmer.
    Exploiting practical limitations of UML for model validation and execution.
    Software and Systems Modeling 5: 26-47, 2006.
21. P. Chapdelaine, M. Hermann, I. Schnoor
    The Complexity of Default Logic on Generalized Conjunctive Queries;
    Technischer Bericht, 2006.
22. H. Schnoor, I. Schnoor
    New Algebraic Tools for Constraint Satisfaction;
    Dagstuhl Seminar Proceedings, 2006.
23. E. Hemaspaandra, H. Schnoor
    On the Complexity of Elementary Modal Logics;
    Technischer Bericht, 2006.
24. H. Schnoor, I. Schnoor
    Enumerating all Solutions for Constraint Satisfaction Problems;
    Dagstuhl Seminar Proceedings, 2006. Auch: in STACS 2007.
25. M. Bauland, E. Hemaspaandra, H. Schnoor, I. Schnoor
    Generalized Modal Satisfiability;
    Technischer Bericht, 2005, Proceedings of the 23rd Symposium on Theoretical Aspects of Computer Science (STACS 2006).
26. H. Schnoor
    The Complexity of the Boolean Formula Value Problem;
    Technischer Bericht, 2005.
27. E. Böhler, H. Schnoor
    The complexity of the descriptiveness of Boolean circuits over different sets of gates;
    2005, erscheint in Theory of Computing Systems.
28. M. Bauland, E. Böhler, N. Creignou, S. Reith, H. Schnoor, H. Vollmer
    Quantified constraints: the complexity of decision and counting for bounded alternation;
    Electronic Colloqium on Computational Complexity, TR05-024, 2005.
29. E. Böhler, S. Reith, H. Schnoor, H. Vollmer
    Bases for Boolean co-clones;
    Elsevier Information Processing Letters, 96:59-66, 2005.
30. M. Bauland, E. Hemaspaandra.
    Isomorphic implication;
    Proceedings 30th International Symposium on Mathematical Foundations of Computer Science
    Springer Lecture Notes in Computer Science, Vol. 3618, 119-130, 2005. © Springer-Verlag.
31. A. Nickelsen, B. Schelm.
    Average-Case – Comparing AvgP, HP and Nearly-P;
    Proceedings 20th Annual IEEE Conference on Computational Complexity, 235-242, 2005.
32. C. Glaßer, S. Reith, H. Vollmer.
    The complexity of base station positioning in cellular networks;
    Discrete and Applied Mathematics, 48(1):1-12, 2005.
33. B. Schelm.
    Complexity of Nonmonotonic Logics - An Incomplete Survey;
    Technischer Bericht, 2005.
34. E. Böhler, E. Hemaspaandra, S. Reith, H. Vollmer.
    The complexity of Boolean constraint isomorphism;
    Springer Lecture Notes in Computer Science Vol. 2996, 164-175, 2004. © Springer-Verlag.
    ACM Computing Research Repository, Technical Report cs.CC/0306134, 2003.
    Proc. 21st Symposium on Theoretical Aspects of Computer Science,
35. P. McKenzie, H. Vollmer, K. W. Wagner.
    Arithmetic circuits and polynomial replacement systems;
    SIAM Journal on Computing, 33(6):1513-1531, 2004.
36. M. Bauland, P. Chapdelaine, N. Creignou, M. Hermann, H. Vollmer.
    An algebraic approach to the complexity of generalized conjunctive queries;
    Proceedings 7th International Conference on Theory and Applications of Satisfiability Testing (SAT2004), Vancouver (British Columbia, Canada), volume 3542 of Lecture Notes in Computer Science, pages 30-45. Springer-Verlag, May 2004.
37. H. Vollmer.
    First-order logic with groupoidal quantifiers;
    in: A. Beckmann, N. Preining (eds.): ESSLLI 2003, Collecium Logicum Vol. VI, Kurt-Gödel-Society, 71-105, 2004.
38. E. Böhler, N. Creignou, S. Reith, H. Vollmer.
    Playing with Boolean blocks, part II: constraint satisfaction problems;
    ACM SIGACT-Newsletter, 35(1):22-35, 2004.
39. E. Böhler, N. Creignou, S. Reith, H. Vollmer.
    Playing with Boolean blocks, part I: Post's lattice with applications to complexity theory;
    ACM SIGACT-Newsletter, 34(4):38-52, 2003.
40. T. Ebert, W. Merkle, H. Vollmer.
    On the autoreducibility of random sequences;
    SIAM Journal on Computing, 32(6):1542-1569, 2003.
41. M. Galota, H. Vollmer.
    Functions computable in polynomial space;
    Information and Computation, 198(1):56-70, 2005.
42. H. Vollmer.
    Complexity theory made easy – the formal language approach to the definition of complexity classes;
    Proc. 7th Developments in Language Theory,
    Springer Lecture Notes in Computer Science Vol. 2710, 95-110, 2003. © Springer-Verlag
43. S. Reith, H. Vollmer.
    Optimal satisfiability for propositional calculi and constraint satisfaction problems;
    Information and Computation, 186:1-19, 2003.
44. M. Galota, S. Kosub, H. Vollmer.
    Generic separations and leaf languages;
    Mathematical Logic Quarterly, 49(4):353-362, 2003.
45. E. Böhler, E. Hemaspaandra, S. Reith, H. Vollmer.
    Equivalence and isomorphism for Boolean constraint satisfaction;
    Proc. Computer Science Logic,
    Springer Lecture Notes in Computer Science Vol. 2471, 412-426, 2002. © Springer-Verlag
46. E. Böhler, H. Vollmer.
    Boolean functions and Post's lattice with applications to complexity theory;
    Lecture Notes for Logic et Interaction 2002, École thématique: Complexité et Calcul, Centre International de Rencontres Mathématiques, 2002.
47. T. Schwentick, D. Therien, H. Vollmer
    Partially-ordered two-way automata: a new characterization of DA;
    Proc. 5th Developments in Language Theory,
    Springer Lecture Notes in Computer Science Vol. 2295, 239-250, 2002. © Springer-Verlag
48. M. Galota, H. Vollmer.
    A generalization of the Büchi-Elgot-Trakhtenbrot theorem;
    Proc. Computer Science Logic 2001,
    Springer Lecture Notes in Computer Science Vol. 2142, 355-368, 2001. © Springer-Verlag
49. M. Galota, C. Glaßer, S. Reith, H. Vollmer.
    A polynomial-time approximation scheme for base station positioning in UMTS networks;
    Proc. 5th Discrete Algorithms and Methods for Mobile Computing and Communications, 52-59, 2001.
50. T. Peichl, H. Vollmer.
    Finite automata with generalized acceptance criteria;
    Discrete Mathematics and Theoretical Computer Science, 4:179-192, 2001.
51. C. Lautemann, P. McKenzie, T. Schwentick, H. Vollmer.
    The descriptive complexity approach to LOGCFL;
    Journal of Computer and Systems Sciences, 62(4),629-652, 2001.
52. S. Reith, H. Vollmer.
    Ist P = NP? Einführung in die Theorie der NP-Vollständigkeit;
    Technischer Bericht 269, Fachbereich Mathematik und Informatik, Universität Würzburg, 2001.
53. M. Agrawal, E. Allender, S. Datta, H. Vollmer, K. W. Wagner.
    Characterizing small depth and small space classes by operators of higher types;
    Chicago Journal on Theoretical Computer Science, Article 2, 2000.
54. U. Hertrampf, S. Reith, H. Vollmer.
    A note on closure properties of logspace MOD-classes;
    Information Processing Letters, 75(3):91-93, 2000.
55. S. Kosub, H. Schmitz, H. Vollmer.
    Uniform characterizations of complexity classes of functions;
    International Journal of Foundations of Computer Science, 11(4):525-551, 2000.
56. H. Vollmer.
    Generalized quantifiers in computational complexity theory;
    in: Komplexität, Graphen und Automaten - Sammelband mit wissenschaftlichen Beiträgen, Gerd Wechsung zum 60. Geburtstag; 1999.
    Vorabversion erschienen in: J. Väänänen (Ed.), Generalized Quantifiers and Computation;
    Proc. ESSLLI'97 Workshop, Springer Lecture Notes in Computer Science Vol. 1754, 99-120, 2000.
57. H. Vollmer.
    Was leistet die Komplexitätstheorie für die Praxis?;
    Informatik-Spektrum, 22(5):317-327, 1999.
58. H. Vollmer.
    Introduction to Circuit Complexity – A Uniform Approach;
    Texts in Theoretical Computer Science, An EATCS Series; Springer-Verlag, 1999.
59. S. Fenner, F. Green, S. Homer, A. Selman, T. Thierauf, H. Vollmer.
    Complements of multivalued functions;
    Chicago Journal on Theoretical Computer Science, Article 3, 1999.
60. H. Vollmer.
    Uniform characterizations of complexity classes;
    ACM SIGACT-Newsletter, 30(1):17-27, 1999.
61. Hans-Jörg Burtschick, H. Vollmer.
    Lindström quantifiers and leaf language definability;
    International Journal of Foundations of Computer Science, 9:277-294, 1998.
62. H. Vollmer.
    Relating polynomial time to constant depth;
    Theoretial Computer Science, 207:159-170, 1998.
63. R. V. Book, H. Vollmer, K. Wagner.
    Probabilistic type-2 operators and ALMOST-classes;
    Computational Complexity, 7:265-289, 1998.
64. H. Caussinus, P. McKenzie, D. Therien, H. Vollmer.
    Nondeterministic NC¹ computation;
    Journal of Computer and System Sciences, 57:200-212, 1998.
65. C. Cronauer, U. Hertrampf, H. Vollmer, K. W. Wagner.
    The chain method to separate counting classes;
    Theory of Computing Systems, 31:93-108, 1998.
66. K. W. Regan, H. Vollmer.
    Gap-languages and log-time complexity classes;
    Theoretical Computer Science, 188:101-116, 1997.
67. H. Vollmer, K. W. Wagner.
    Measure 1 results in computational complexity;
    in: D.-Z. Du and K.-I Ko (eds.), Advances in Algorithms, Languages, and Complexity,
    Kluwer Academic Publishers, 285-312, 1997.
68. H. Vollmer, K. W. Wagner.
    Recursion theoretic characterizations of complexity classes of counting functions;
    Theoretical Computer Science, 163:245-258, 1996.
69. U. Hertrampf, H. Vollmer, K. W. Wagner.
    On balanced vs. unbalanced computation trees;
    Mathematical Systems Theory, 29:411-421, 1996.
70. H. Vollmer, K. W. Wagner.
    Complexity classes of optimization functions;
    Information and Computation, 120:198-219, 1995.
71. U. Hertrampf, H. Vollmer, K. W. Wagner.
    On the power of number-theoretic operations with respect to counting;
    Proc. 10th Structure in Complexity Theory Conference, 299-314, 1995.
72. L. Hemaspaandra, H. Vollmer.
    The satanic notations: counting classes beyond #P and other definitional adventures;
    ACM SIGACT-Newsletter, 26(1):2-13, 1995.
73. H. Vollmer.
    On different reducibility notions for function classes;
    Proc. 11th Symposium on Theoretical Aspects of Computer Science,
    Springer Lecture Notes in Computer Science Vol. 775, 449-460, 1994. © Springer-Verlag
74. H. Vollmer, K. W. Wagner.
    The complexity of finding middle elements;
    International Journal of Foundations of Computer Science, 4:293-307, 1993.
75. U. Hertrampf, C. Lautemann, T. Schwentick, H. Vollmer, K. W. Wagner.
    On the power of polynomial time bit-reductions;
    Proc. 8th Structure in Complexity Theory Conference, 200-207, 1993.
76. H. Vollmer.
    The gap-language technique revisited;
    Proc. 4th Computer Science Logic,
    Springer Lecture Notes in Computer Science Vol. 533, 389-399, 1990. © Springer-Verlag

---

Please note: The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that the publications are offered here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each copyright holder, and make use of the documents only for research and education purpose. These publications may not be reposted without the explicit permission of the copyright holder.