Publikationen Theoretische Informatik – Institut für Theoretische Informatik

Kontinen J, Mahmood Y, Meier A, Vollmer H. Parameterized complexity of weighted team definability. Mathematical Structures in Computer Science. 2024 Feb 20. Epub 2024 Feb 20. doi: 10.48550/arXiv.2302.00541, 10.1017/S0960129524000033

Creignou N, Durand A, Vollmer H. Enumeration Classes Defined by Circuits. in Szeider S, Ganian R, Silva A, Hrsg., 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2022. 39. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.48550/arXiv.2205.00539, 10.4230/LIPIcs.MFCS.2022.38

Haak A, Meier A, Müller F, Vollmer H. Enumerating teams in first-order team logics. Annals of Pure and Applied Logic. 2022 Dez;173(10):103163. Epub 2022 Jun 14. doi: 10.1016/j.apal.2022.103163

Barlag T, Vollmer H. A Logical Characterization of Constant-Depth Circuits over the Reals. in Silva A, Wassermann R, de Queiroz R, Hrsg., Logic, Language, Information, and Computation: 27th International Workshop, WoLLIC 2021, Virtual Event, October 5–8, 2021, Proceedings. Band abs/2005.04916. Springer, Cham. 2021. S. 16-30. (Lecture Notes in Computer Science (LNCS)). Epub 2021 Okt 6. doi: 10.1007/978-3-030-88853-4_2

Durand A, Haak A, Kontinen J, Vollmer H. Descriptive complexity of #P functions: A new perspective. Journal of Computer and System Sciences. 2021 Mär;116:40-54. Epub 2020 Apr 30. doi: 10.1016/j.jcss.2020.04.002

Hella L, Kuusisto A, Meier A, Vollmer H. Satisfiability of modal inclusion logic: Lax and strict semantics. ACM Transactions on Computational Logic. 2020 Jan 10;21(1):1-18. 7. Epub 2019 Okt. doi: 10.1145/3356043

Creignou N, Kröll M, Pichler R, Skritek S, Vollmer H. A complexity theory for hard enumeration problems. Discrete applied mathematics. 2019 Sep 15;268:191-209. Epub 2019 Mär 6. doi: 10.1016/j.dam.2019.02.025

Creignou N, Ktari R, Meier A, Müller JS, Olive F, Vollmer H. Parameterised Enumeration for Modification Problems. Algorithms. 2019 Sep;12(9):189. 9. Epub 2019 Sep 9. doi: 10.3390/a12090189, 10.15488/10960

Haak A, Vollmer H. A model-theoretic characterization of constant-depth arithmetic circuits. Annals of Pure and Applied Logic. 2019 Sep;170(9):1008-1029. Epub 2019 Apr 11. doi: 10.48550/arXiv.1603.09531, 10.1016/j.apal.2019.04.006

Haak A, Kontinen J, Müller F, Vollmer H, Yang F. Counting of teams in first-order team logics. in Rossmanith P, Heggernes P, Katoen J-P, Hrsg., 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Band abs/1902.00246. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2019. S. 19:1-19:15. 19. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.48550/arXiv.1902.00246, 10.4230/LIPIcs.MFCS.2019.19

Vollmer H, Vallée B. Guest Editorial: Special Issue on Theoretical Aspects of Computer Science. Theory of computing systems. 2019 Jul 15;63(5):923-925. 5. Epub 2019 Jun 28. doi: 10.1007/s00224-019-09934-y

Vollmer H. Künstlicher Geist? Christ in der Gegenwart. 2019 Jan 6;2019(1):17-18.

Vollmer H, Kontinen J, Grädel E, Kolaitis PG. Logics for Dependence and Independence: Report from Dagstuhl Seminar 19031. Dagstuhl Reports. 2019 Jun 19;9(1):28-46. Epub 2019 Jun 19. doi: 10.4230/DagRep.9.1.28

Durand A, Haak A, Vollmer H. Model-Theoretic Characterization of Boolean and Arithmetic Circuit Classes of Small Depth. in LICS '18: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science. New York: Association for Computing Machinery (ACM). 2018. S. 354-363. (Proceedings - Symposium on Logic in Computer Science). doi: https://arxiv.org/pdf/1710.01934.pdf, 10.1145/3209108.3209179

Dürr C, Vollmer H. Preface of STACS 2016 Special Issue. Theory of Computing Systems. 2018 Jan;62(1):1-3. Epub 2017 Dez 4. doi: 10.1007/s00224-017-9830-5

Vollmer H, Hannula M, Kontinen J, Virtema J. Complexity of propositional logics in team semantic. ACM Transactions on Computational Logic. 2018 Jan;19(1):2:1-2:14. 2. Epub 2018 Jan 6. doi: 10.1145/3157054

Vollmer H. Die Zukunft der Menschheit: Pierre Teilhard de Cardin und die Künstliche Intelligenz. Herder-Korrespondenz. 2018 Nov;2018(11):28-32.

Creignou N, Kröll M, Pichler R, Skritek S, Vollmer H. On the complexity of hard enumeration problems. in Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Proceedings. Springer Verlag. 2017. S. 183-195. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-53733-7_13

Creignou N, Meier A, Müller JS, Schmidt J, Vollmer H. Paradigms for Parameterized Enumeration. Theory of Computing Systems. 2017 Mai 1;60(4):737-758. Epub 2016 Sep 13. doi: 10.1007/s00224-016-9702-4

Durand A, Haak A, Vollmer H. Model-Theoretic Characterizations of Boolean and Arithmetic Circuit Classes of Small Depth. 2017.

Kontinen J, Müller JS, Schnoor H, Vollmer H. Modal independence logic. Journal of Logic and Computation. 2017 Jul;27(5):1333-1352. Epub 2016 Jun 25. doi: 10.1093/logcom/exw019

Vollmer H, Vallée B. 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany. Leibniz International Proceedings in Informatics, LIPIcs. 2017;66.

Abramsky S, Kontinen J, Väänänen J, Vollmer H. Dependence Logic, Theory and Applications. in Dependence Logic: Theory and Applications. Cham: Birkhäuser. 2016. (Logics for Dependence and Independence). doi: 10.1007/978-3-319-31803-5

Abramsky S, Kontinen J, Väänänen J, Vollmer H. Introduction. in Logics for Dependence and Independence. Cham: Birkhäuser. 2016. S. 1-3 Epub 2016 Jun 30. doi: 10.1007/978-3-319-31803-5_1

Beyersdorff O, Creignou N, Egly U, Vollmer H. SAT and Interactions (Dagstuhl Seminar 16381). 2016. doi: 10.4230/DAGREP.6.9.74

Durand A, Haak A, Kontinen J, Vollmer H. Descriptive complexity of #AC0 functions. in Talbot J-M, Regnier L, Hrsg., Computer Science Logic 2016, CSL 2016. 2016. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.CSL.2016.20

Durand A, Kontinen J, Vollmer H. Expressivity and Complexity of Dependence Logic. in Logics for Dependence and Independence. Cham: Birkhäuser. 2016. S. 5-32 Epub 2016 Jun 30. doi: 10.1007/978-3-319-31803-5_2

Haak A, Vollmer H. A Model-Theoretic Characterization of Constant-Depth Arithmetic Circuits. in Väänänen J, Hirvonen Å, de Queiroz R, Hrsg., Logic, Language, Information, and Computation: 23rd International Workshop, WoLLIC 2016, Puebla, Mexico, August 16-19th, 2016. Proceedings. Berlin: Springer Verlag. 2016. S. 234-248. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.48550/arXiv.1603.09531, 10.1007/978-3-662-52921-8_15

Ollinger N, Vollmer H. 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France. Leibniz International Proceedings in Informatics, LIPIcs. 2016;47.

Bojanczyk M, Mahajan M, Schwentick T, Vollmer H. Circuits, Logic and Games (Dagstuhl Seminar 15401). 2015. doi: 10.4230/DAGREP.5.9.105

Creignou N, Vollmer H. Parameterized Complexity of Weighted Satisfiability Problems - Decision, Enumeration, Counting. Fundam. Informaticae. 2015;136(4):297-316. doi: 10.3233/FI-2015-1159

Creignou N, Ktari R, Meier A, Müller J-S, Olive F, Vollmer H. Parameterized Enumeration for Modification Problems. in Adrian-Horia Dediu, Enrico Formenti, Carlos Martín-Vide, Bianca Truthe: Language and Automata Theory and Applications - 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings.. 2015. S. 524-536 doi: 10.1007/978-3-319-15579-1_41

Durand A, Ebbing J, Kontinen J, Vollmer H. Dependence logic with a majority quantifier. Journal of Logic, Language and Information. 2015 Sep;24:289-305. Epub 2015 Jun 25. doi: 10.48550/arXiv.1109.4750, 10.1007/s10849-015-9218-3

Durand A, Ebbing J, Kontinen J, Vollmer H. Dependence Logic with a Majority Quantifier. J. Log. Lang. Inf. 2015;24(3):289-305. doi: 10.1007/S10849-015-9218-3

Grädel E, Kontinen J, Väänänen J, Vollmer H. Logics for Dependence and Independence (Dagstuhl Seminar 15261). 2015. doi: 10.4230/DAGREP.5.6.70

Hannula M, Kontinen J, Virtema J, Vollmer H. Complexity of Propositional Independence and Inclusion Logic. in Mathematical Foundations of Computer Science 2015: 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part I. 2015. S. 269-280 doi: 10.1007/978-3-662-48057-1_21

Hannula M, Kontinen J, Virtema J, Vollmer H. Complexity of Propositional Logics in Team Semantic. 2015 Apr 23. doi: 10.48550/arXiv.1504.06135

Hella L, Kuusisto A, Meier A, Vollmer H. Modal Inclusion Logic - Being Lax is Simpler than Being Strict. in Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings. 2015. S. 281-292 doi: 10.1007/978-3-662-48057-1_22

Kontinen J, Müller J-S, Schnoor H, Vollmer H. A Van Benthem Theorem for Modal Team Semantics. in 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). 2015. S. 277-291 doi: 10.4230/LIPICS.CSL.2015.277

Meier A, Vollmer H. Komplexität von Algorithmen. Lehmanns Media, 2015.

Meier A, Schindler I, Schmidt J, Thomas M, Vollmer H. On the parameterized complexity of non-monotonic logics. Arch. Math. Log. 2015;54(5-6):685-710. doi: 10.1007/S00153-015-0435-X

Aschinger M, Drescher C, Gottlob G, Vollmer H. LoCo - A Logic for Configuration Problems. ACM Trans. Comput. Log. 2014;15(3):20:1-20:25. doi: 10.1145/2629454

Ebbing J, Kontinen J, Müller J-S, Vollmer H. A Fragment of Dependence Logic Capturing Polynomial Time. Logical Methods in Computer Science, Volume. 2014;10(3). doi: 10.2168/LMCS-10(3:3)2014

Kontinen J, Müller J-S, Schnoor H, Vollmer H. Modal Independence Logic. in Goré R, Kooi BP, Kurucz A, Hrsg., Advances in Modal Logic 10, invited and contributed papers from the tenth conference on "Advances in Modal Logic," held in Groningen, The Netherlands, August 5-8, 2014. College Publications. 2014. S. 353-372

Abramsky S, Kontinen J, Väänänen JA, Vollmer H. Dependence Logic - Theory and Applications (Dagstuhl Seminar 13071). 2013. doi: 10.4230/DAGREP.3.2.45

Beyersdorff O, Datta S, Krebs A, Mahajan M, Scharfenberger-Fabian G, Sreenivasaiah K et al. Verifying proofs in constant depth. ACM Trans. Comput. Theory. 2013;5(1):2:1-2:23. doi: 10.1145/2462896.2462898

Creignou N, Meier A, Müller J-S, Schmidt J, Vollmer H. Paradigms for Parameterized Enumeration. in Chatterjee K, Sgall J, Hrsg., Mathematical Foundations of Computer Science 2013: 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Springer Berlin Heidelberg. 2013. S. 290-301. (Lecture Notes in Computer Science (LNCS)). doi: 10.1007/978-3-642-40313-2_27

Creignou N, Meier A, Müller J-S, Schmidt J, Vollmer H. Paradigms for Parameterized Enumeration. 2013. (CoRR).

Creignou N, Ktari R, Meier A, Müller J-S, Olive F, Vollmer H. Parameterized Enumeration with Ordering. 2013.

Ebbing J, Hella L, Meier A, Müller J-S, Virtema J, Vollmer H. Extended Modal Dependence Logic. in Logic, Language, Information, and Computation - 20th International Workshop, WoLLIC 2013, Darmstadt, Germany, August 20-23, 2013. Proceedings. 2013. S. 126-137 doi: 10.1007/978-3-642-39992-3_13

Lohmann P, Vollmer H. Complexity Results for Modal Dependence Logic. STUD LOGICA. 2013;101(2):343-366. doi: 10.1007/S11225-013-9483-6

Müller J-S, Vollmer H. Model Checking for Modal Dependence Logic: An Approach Through Post's Lattice. in Logic, Language, Information, and Computation. 2013. S. 238-250 doi: 10.1007/978-3-642-39992-3_21

Aschinger M, Drescher C, Vollmer H. LoCo - A Logic for Configuration Problems.. 2012. doi: 10.3233/978-1-61499-098-7-73

Beyersdorff O, Meier A, Thomas M, Vollmer H. The complexity of reasoning for fragments of default logic. J. Log. Comput. 2012;22(3):587-604. doi: 10.1093/LOGCOM/EXQ061

Beyersdorff O, Datta S, Krebs A, Mahajan M, Scharfenberger-Fabian G, Sreenivasaiah K et al. Verifying Proofs in Constant Depth. Electron. Colloquium Comput. Complex. 2012;TR12-079.

Creignou N, Vollmer H. Parameterized Complexity of Weighted Satisfiability Problems.. 2012. doi: 10.1007/978-3-642-31612-8_26

Creignou N, Galesi N, Kullmann O, Vollmer H. SAT Interactions (Dagstuhl Seminar 12471). 2012. doi: 10.4230/DAGREP.2.11.87

Creignou N, Meier A, Vollmer H, Thomas M. The Complexity of Reasoning for Fragments of Autoepistemic Logic. ACM Trans. Comput. Log. 2012;13(2):17:1-17:22. doi: 10.1145/2159531.2159539

Datta S, Mahajan M, Rao BVR, Thomas M, Vollmer H. Counting classes and the fine structure between NC1 and L. Theor. Comput. Sci. 2012;417:36-49. doi: 10.1016/J.TCS.2011.05.050

Meier A, Müller J-S, Mundhenk M, Vollmer H. Complexity of Model Checking for Logics over Kripke models. Bull. EATCS. 2012;108:49-89.

Meier A, Schmidt J, Thomas M, Vollmer H. On the Parameterized Complexity of Default Logic and Autoepistemic Logic. in Language and Automata Theory and Applications: 6th International Conference, LATA 2012, A Coruña, Spain, March 5-9, 2012. Proceedings. 2012. S. 389-400 doi: 10.1007/978-3-642-28332-1_33

Bauland M, Mundhenk M, Schneider T, Schnoor H, Schnoor I, Vollmer H. The tractability of model checking for LTL - The good, the bad, and the ugly fragments. ACM Trans. Comput. Log. 2011;12(2):13:1-13:28. doi: 10.1145/1877714.1877719

Beyersdorff O, Meier A, Mundhenk M, Schneider T, Thomas M, Vollmer H. Model Checking CTL is Almost Always Inherently Sequential. Log. Methods Comput. Sci. 2011;7(2). doi: 10.2168/LMCS-7(2:12)2011

Beyersdorff O, Meier A, Müller S, Thomas M, Vollmer H. Proof complexity of propositional default logic. Arch. Math. Log. 2011;50(7-8):727-742. doi: 10.1007/S00153-011-0245-8

Beyersdorff O, Datta S, Mahajan M, Scharfenberger-Fabian G, Sreenivasaiah K, Thomas M et al. Verifying Proofs in Constant Depth. in Mathematical Foundations of Computer Science 2011: 36th International Symposium, MFCS 2011, Warsaw, Poland, August 22-26, 2011. Proceedings. 2011. S. 84-95 doi: 10.1007/978-3-642-22993-0_11

Durand A, Ebbing J, Kontinen J, Vollmer H. Dependence logic with a majority quantifier. in IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Band abs/1109.4750. 2011. S. 252-263 doi: 10.4230/LIPICS.FSTTCS.2011.252

Vöcking B, Alt H, Dietzfelbinger M, Reischuk R, Scheideler C, Vollmer H et al. Algorithms Unplugged. Fachbuch. 2011. doi: 10.1007/978-3-642-15328-0

Bauland M, Böhler E, Creignou N, Reith S, Schnoor H, Vollmer H. The Complexity of Problems for Quantified Constraints. Theory Comput. Syst. 2010;47(2):454-490. doi: 10.1007/S00224-009-9194-6

Beyersdorff O, Meier A, Müller S, Thomas M, Vollmer H. Proof Complexity of Propositional Default Logic. in Strichman O, Szeider S, Hrsg., Theory and Applications of Satisfiability Testing: SAT 2010, 13th International Conference, SAT 2010, Edinburgh, UK, July 11-14, 2010. Proceedings. Springer. 2010. S. 30-43. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-14186-75

Beyersdorff O, Meier A, Müller S, Thomas M, Vollmer H. Proof Complexity of Propositional Default Logic. Dagstuhl Seminar Proceedings. 2010;10061.

Böhler E, Creignou N, Galota M, Reith S, Schnoor H, Vollmer H. Boolean Circuits as a Data Structure for Boolean Functions - Efficient Algorithms and Hard Problems. Log. Methods Comput. Sci. 2010;8(3). doi: 10.2168/LMCS-8(3:31)2012, 10.2168/LMCS-8(3:27)2012

Creignou N, Meier A, Thomas M, Vollmer H. The Complexity of Reasoning for Fragments of Autoepistemic Logic. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany. 2010. (Dagstuhl Seminar Proceedings).

Creignou N, Meier A, Thomas M, Vollmer H. The Complexity of Reasoning for Fragments of Autoepistemic Logic. 2010. (CoRR).

Creignou N, Meier A, Thomas M, Vollmer H. The Complexity of Reasoning for Fragments of Autoepistemic Logic^∗. in Dagstuhl Seminar: Circuits, Logic, and Games 2010. Band 10061. 2010. (Dagstuhl Seminar Proceedings).

Datta S, Mahajan M, Rao BVR, Thomas M, Vollmer H. Counting classes and the fine structure between NC1 and L. in MFCS. 2010. S. 306-317 doi: 10.1007/978-3-642-15155-2_28

Datta S, Mahajan M, Rao BVR, Thomas M, Vollmer H. Counting classes and the fine structure between NC1 and L. Electron. Colloquium Comput. Complex. 2010;TR10.

Kontinen J, Vollmer H. On Second-Order Monadic Monoidal and Groupoidal Quantifiers. Log. Methods Comput. Sci. 2010;6(3). doi: 10.2168/LMCS-6(3:25)2010

Lohmann P, Vollmer H. Complexity Results for Modal Dependence Logic. in Dawar A, Veith H, Hrsg., Computer Science Logic: 24th International Workshop, CSL 2010, 19th Annual Conference of the EACSL, Brno, Czech Republic, August 23-27, 2010. Proceedings. Springer. 2010. S. 411-425. (Lecture Notes in Computer Science). doi: 10.48550/arXiv.1104.0607, 10.1007/978-3-642-15205-4_32

McKenzie P, Thomas M, Vollmer H. Extensional Uniformity for Boolean Circuits. SIAM J. Comput. 2010;39(7):3186-3206. 7. doi: 10.48550/arXiv.0805.4072, 10.1137/080741811

Rossman B, Schwentick T, Thérien D, Vollmer H. 10061 Abstracts Collection - Circuits, Logic, and Games. in Circuits, Logic, and Games. 2010

Rossman B, Schwentick T, Thérien D, Vollmer H. 10061 Executive Summary - Circuits, Logic, and Games. in Circuits, Logic, and Games. 2010

Thomas M, Vollmer H. Complexity of Non-Monotonic Logics. Bull. EATCS. 2010;102:53-82.

Allender E, Bauland M, Immerman N, Schnoor H, Vollmer H. The complexity of satisfiability problems: Refining Schaefer's theorem. J. Comput. Syst. Sci. 2009;75(4):245-254. 4. doi: 10.1016/j.jcss.2008.11.001

Bauland M, Schneider T, Schnoor H, Schnoor I, Vollmer H. The Complexity of Generalized Satisfiability for Linear Temporal Logic. Log. Methods Comput. Sci. 2009;5(1):1.

Bauland M, Mundhenk M, Schneider T, Schnoor H, Schnoor I, Vollmer H. The Tractability of Model-Checking for LTL: The Good, the Bad, and the Ugly Fragments. Electron. Notes Theor. Comput. Sci. 2009;231:277-292. doi: 10.1016/j.entcs.2009.02.041, 10.15488/1519

Beyersdorff O, Meier A, Thomas M, Vollmer H, Mundhenk M, Schneider T. Model Checking CTL is Almost Always Inherently Sequential. in Lutz C, Raskin J-F, Hrsg., TIME 2009, 16th International Symposium on Temporal Representation and Reasoning, Bressanone-Brixen, Italy, 23-25 July 2009, Proceedings. IEEE Computer Society. 2009. S. 21-28 doi: 10.1109/TIME.2009.12

Beyersdorff O, Meier A, Thomas M, Vollmer H. The complexity of propositional implication. Information Processing Letters. 2009;109(18):1071-1077. doi: 10.1016/j.ipl.2009.06.015

Meier A, Thomas M, Vollmer H, Mundhenk M. The Complexity of Satisfiability for Fragments of CTL and CTL*. Int. J. Found. Comput. Sci. 2009;20(5):901-918. doi: 10.1016/j.entcs.2008.12.040, 10.1142/S0129054109006954, 10.1142/S012905411592001X

Bauland M, Schneider T, Schnoor H, Schnoor I, Vollmer H. The Complexity of Generalized Satisfiability for Linear Temporal Logic. Logical Methods in Computer Science, Volume. 2008 Dez 28. doi: 10.2168/LMCS-5(1:1)2009

Beyersdorff O, Meier A, Thomas M, Vollmer H. The Complexity of Reasoning for Fragments of Default Logic. in Kullmann O, Hrsg., Theory and Applications of Satisfiability Testing - SAT 2009, 12th International Conference, SAT 2009, Swansea, UK, June 30 - July 3, 2009. Proceedings. Band 5584. Springer. 2008. S. 51-64. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-02777-27

Creignou N, Vollmer H. Boolean constraint satisfaction problems: When does post's lattice help? 2008. doi: 10.1007/978-3-540-92800-3_2

Kontinen J, Vollmer H. On second-order monadic groupoidal quantifiers. 2008. doi: 10.1007/978-3-540-69937-8_21

McKenzie P, Thomas M, Vollmer H. Extensional uniformity for Boolean circuits. 2008. doi: 10.1007/978-3-540-87531-4_7

Meier A, Mundhenk M, Thomas M, Vollmer H. The Complexity of Satisfiability for Fragments of CTL and CTL*. in Proceedings of the Second Workshop on Reachability Problems in Computational Models (RP 2008). Band 223. 2008. S. 201-213. (Electron. Notes Theor. Comput. Sci.). doi: 10.1016/j.entcs.2008.12.040

Bauland M, Schneider T, Schnoor H, Schnoor I, Vollmer H. The complexity of generalized satisfiability for linear temporal logic. in Foundations of Software Science and Computational Structures - 10th International Conference, FOSSACS 2007. Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2007. Springer Verlag. 2007. S. 48-62. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-71389-0_5

Vollmer H. Computational complexity of constraint satisfaction. in Computation and Logic in the Real World - Third Conference on Computability in Europe, CiE 2007, Proceedings. 2007. S. 748-757. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-73001-9_80

McKenzie P, Schwentick T, Thérien D, Vollmer H. The many faces of a translation. Journal of Computer and System Sciences. 2006. doi: 10.1016/j.jcss.2005.08.003

Steimann F, Vollmer H. Exploiting practical limitations of UML diagrams for model validation and execution. Software and systems modeling. 2006 Apr;5(1):26-47. doi: 10.1007/s10270-005-0097-y

Bauland M, Chapdelaine P, Creignou N, Hermann M, Vollmer H. An algebraic approach to the complexity of generalized conjunctive queries. Lecture Notes in Computer Science. 2005;3542:30-45. doi: 10.1007/11527695_3

Böhler E, Reith S, Schnoor H, Vollmer H. Bases for Boolean co-clones. Information processing letters. 2005 Okt 31;96(2):59-66. doi: 10.1016/j.ipl.2005.06.003

Galota M, Vollmer H. Functions computable in polynomial space. Information and computation. 2005. doi: 10.1016/j.ic.2005.02.002

Glaßer C, Reith S, Vollmer H. The complexity of base station positioning in cellular networks. Discrete applied mathematics. 2005 Apr 30;148(1):1-12. doi: 10.1016/j.dam.2004.07.005

Böhler E, Hemaspaandra E, Reith S, Vollmer H. The complexity of Boolean constraint isomorphism. in Diekert V, Habib M, Hrsg., Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2004. S. 164-175. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-24749-4_15

Mckenzie P, Vollmer H, Wagner KW. Arithmetic circuits and polynomial replacement systems. SIAM journal on computing. 2004. doi: 10.1137/S009753970139207X

Ebert T, Merkle W, Vollmer H. On the autoreducibility of random sequences. SIAM journal on computing. 2003. doi: 10.1137/S0097539702415317

Galota M, Kosub S, Vollmer H. Generic separations and leaf languages. Mathematical logic quarterly. 2003. doi: 10.1002/malq.200310037

Reith S, Vollmer H. Optimal satisfiability for propositional calculi and constraint satisfaction problems. Inf. Comput. 2003;186(1):1-19. doi: 10.1016/S0890-5401(03)00092-0

Vollmer H. Complexity theory made easy: The formal language approach to the definition of complexity classes. 2003.

Böhler E, Hemaspaandra E, Reith S, Vollmer H. Equivalence and isomorphism for boolean constraint satisfaction. 2002.

Schwentick T, Therien D, Vollmer H. Partially-ordered two-way automata: A new characterization of DA. 2002.

Galota M, Vollmer H. A generalization of the Büchi-Elgot-Trakhtenbrot theorem. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2001.

Galota M, Glaßer C, Reith S, Vollmer H. A polynomial-time approximation scheme for base station positioning in UMTS networks. in Proceedings of the 5th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M 2001), Rome, Italy, July 21, 2001. Association for Computing Machinery (ACM). 2001. S. 52-59 doi: 10.1145/381448.381455

Lautemann C, McKenzie P, Schwentick T, Vollmer H. The descriptive complexity approach to LOGCFL. Journal of Computer and System Sciences. 2001. doi: 10.1006/jcss.2000.1742

Ebert T, Vollmer H. On the autoreducibility of random sequences. 2000. doi: 10.1007/3-540-44612-5_29

Hertrampf U, Reith S, Vollmer H. Note on closure properties of logspace MOD classes. Information processing letters. 2000. doi: 10.1016/S0020-0190(00)00091-0

Kosub S, Schmitz H, Vollmer H, Cai J. Uniform characterizations of complexity classes of functions. International Journal of Foundations of Computer Science. 2000. doi: 10.1142/S0129054100000326

McKenzie P, Vollmer H, Wagner KW. Arithmetic circuits and polynomial replacement systems. 2000.

McKenzie P, Schwentick T, Thérien D, Vollmer H. The many faces of a translation. 2000.

Reith S, Vollmer H. Optimal satisfiability for propositional calculi and constraint satisfaction problems. 2000. doi: 10.1007/3-540-44612-5_59

Lautemann C, McKenzie P, Schwentick T, Vollmer H. The descriptive complexity approach to LOGCFL. 1999.

Peichl T, Vollmer H. Finite automata with generalized acceptance criteria. 1999.

Vollmer H. A generalized quantifier concept in computational complexity theory. 1999. doi: 10.1007/3-540-46583-9_5

Book RV, Vollmer H, Wagner KW. Probabilistic type-2 operators and "almost"-classes. Computational complexity. 1998. doi: 10.1007/s000370050012

Caussinus H, McKenzie P, Thérien D, Vollmer H. Nondeterministic NC1 Computation. Journal of Computer and System Sciences. 1998. doi: 10.1006/jcss.1998.1588

Cronauer K, Hertrampf U, Vollmer H, Wagner KW. The chain method to separate counting classes. Theory of computing systems. 1998. doi: 10.1007/s002240000080

Kosub S, Schmitz H, Vollmer H. Uniformly defining complexity classes of functions. 1998. doi: 10.1007/BFb0028595

Lautemann C, McKenzie P, Schwentick T, Vollmer H. The descriptive complexity approach to LOGCFL. 1998 Sep 28.

Reith S, Vollmer H. The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae. 1998 Sep 28.

Vollmer H. A Generalized Quantifier Concept in Computational Complexity Theory. in f. 1998. (Annals of Pure and Applied Logic).

Vollmer H. Relating polynomial time to constant depth. Theoretical computer science. 1998. doi: 10.1016/S0304-3975(98)00061-9

Regan KW, Vollmer H. Gap-languages and log-time complexity classes. Theoretical computer science. 1997. doi: 10.1016/S0304-3975(96)00288-5

Vollmer H, Wagner KW. On operators of higher types. in Proceedings of the Annual IEEE Conference on Computational Complexity. 1997 doi: 10.1109/CCC.1997.612313

Book RV, Vollmer H, Wagner KW. On type-2 probabilistic quantifiers. 1996.

Fenner S, Green F, Homer S, Selman AL, Thierauf T, Vollmer H. Complements of multivalued functions. in Proceedings of the Annual IEEE Conference on Computational Complexity. 1996

Hertrampf U, Vollmer H, Wagner KW. On balanced versus unbalanced computation trees. Theory of computing systems. 1996. doi: 10.1007/BF01192696

Vollmer H, Wagner KW. Recursion theoretic characterizations of complexity classes of counting functions. Theoretical computer science. 1996. doi: 10.1016/0304-3975(95)00237-5

Vollmer H. Relations among parallel and sequential computation models. 1996.

Hertrampf U, Vollmer H, Wagner KW. On the power of number-theoretic operations with respect to counting. in Proceedings of the IEEE Annual Structure in Complexity Theory Conference. 1995

Vollmer H, Wagner KW. Complexity classes of optimization functions. Information and computation. 1995. doi: 10.1006/inco.1995.1109

Vollmer H. On different reducibility notions for function classes. 1994.

Hertrampf U, Lautemann C, Schwentick T, Vollmer H, Wagner KW. On the power of polynomial time bit-reductions. in Proceedings of the Eighth Annual Structure in Complexity Theory Conference. 1993

Vollmer H. The gap-language-technique revisited. 1991. doi: 10.1007/3-540-54487-9_72

Publikationen zur Theoretischen Informatik

2024

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

2003

2002

2001

2000

1999

1998

1997

1996

1995

1994

1993

1991