Showing results 1 - 218 out of 218
2025
Barlag T, Fröhlich N, Hankala T, Hannula M, Hirvonen M, Holzapfel V et al. Logic and Computation Through the Lens of Semirings. 2025 Feb 18. Epub 2025 Feb 18. doi: 10.48550/arXiv.2502.12939
Gutleben J, Meier A. A SUBSET-SUM Characterisation of the A-Hierarchy. In Královič R, Kůrková V, editors, SOFSEM 2025: Theory and Practice of Computer Science - 50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025, Proceedings. Springer Science and Business Media Deutschland GmbH. 2025. p. 31-44. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2025 Feb 15. doi: 10.1007/978-3-031-82697-9_3, 10.48550/arXiv.2409.07996
Hannula M, Hirvonen M, Kontinen J, Mahmood Y, Meier A, Virtema J. Logics with probabilistic team semantics and the Boolean negation. Journal of Logic and Computation. 2025 Mar 30;35(3):3. doi: 10.1093/logcom/exaf021
2024
Barlag T, Holzapfel V, Strieker L, Virtema J, Vollmer H. Graph Neural Networks and Arithmetic Circuits. Advances in Neural Information Processing Systems. 2024;37. doi: 10.48550/arXiv.2402.17805
Barlag T, Chudigiewitsch F, Gaube SA. Logical characterizations of algebraic circuit classes over integral domains. Mathematical Structures in Computer Science. 2024 May;34(5):346-374. Epub 2024 May 13. doi: 10.1017/S0960129524000136
Creignou N, Durand A, Vollmer H. Special issue on logic and complexity. Mathematical Structures in Computer Science. 2024 May;34:344-345. doi: 10.1017/S0960129524000148
Fichte JK, Hecher M, Meier A. Counting Complexity for Reasoning in Abstract Argumentation. Journal of Artificial Intelligence Research. 2024 Jun 23;80:805–834. doi: 10.1613/jair.1.16210
Fichte JK, Hecher M, Mahmood Y, Meier A. Rejection in Abstract Argumentation: Harder Than Acceptance? In Endriss U, Melo FS, Bach K, Bugarin-Diz A, Alonso-Moral JM, Barro S, Heintz F, editors, ECAI 2024 - 27th European Conference on Artificial Intelligence, Including 13th Conference on Prestigious Applications of Intelligent Systems, PAIS 2024, Proceedings. IOS Press BV. 2024. p. 3212-3219. (Frontiers in Artificial Intelligence and Applications). doi: 10.48550/arXiv.2408.10683, 10.3233/FAIA240867
Fichte JK, Meier A, Schindler I. Strong Backdoors for Default Logic. ACM Transactions on Computational Logic. 2024 Jun 17;25(3):15. Epub 2024 Mar 30. doi: 10.1145/3655024
Fröhlich N, Meier A. Submodel Enumeration for CTL Is Hard. In Wooldridge M, Dy J, Natarajan S, editors, AAAI Proceedings. AAAI Press/International Joint Conferences on Artificial Intelligence. 2024. p. 10517-10524. (Proceedings of the AAAI Conference on Artificial Intelligence; 9). doi: 10.48550/arXiv.2312.09868, 10.1609/aaai.v38i9.28921
Hecher M, Mahmood Y, Meier A, Schmidt J. Quantitative Claim-Centric Reasoning in Logic-Based Argumentation. In Larson K, editor, Proceedings of the 33rd International Joint Conference on Artificial Intelligence, IJCAI 2024. 2024. p. 3404-3412. (IJCAI International Joint Conference on Artificial Intelligence).
Kontinen J, Virtema J, Vollmer H, Yang F, Fröhlich N. Logics for Dependence and Independence: Expressivity and Complexity (Dagstuhl Seminar 24111). Dagstuhl Reports. 2024 Sept 19;14(3):31-51. 3. doi: 10.4230/DagRep.14.3.31
Kontinen J, Mahmood Y, Meier A, Vollmer H. Parameterized complexity of weighted team definability. Mathematical Structures in Computer Science. 2024 May;34(5):375-389. Epub 2024 Feb 20. doi: 10.1017/S0960129524000033, 10.48550/arXiv.2302.00541
Krebs A, Meier A, Virtema J, Zimmermann M. Synchronous Team Semantics for Temporal Logics. 2024. Epub 2024. doi: 10.48550/arXiv.2409.18667
Mahmood Y, Virtema J, Barlag T, Ngomo ACN. Computing Repairs Under Functional and Inclusion Dependencies via Argumentation. In Meier A, Ortiz M, editors, Foundations of Information and Knowledge Systems : 13th International Symposium, FoIKS 2024. Springer Science and Business Media Deutschland GmbH. 2024. p. 23-42. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.48550/arXiv.2312.01973, 10.1007/978-3-031-56940-1_2
Meier A, (ed.), Ortiz M, (ed.). Foundations of Information and Knowledge Systems: 13th International Symposium, FoIKS 2024, Sheffield, UK, April 8-11, 2024, Proceedings. 1 ed. Cham: Springer, Cham, 2024. 402 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2024 Mar 28. doi: 10.1007/978-3-031-56940-1
Müller F. Counting and enumerating in first-order team logics. Hannover: Leibniz Universität Hannover, 2024. 87 p. doi: 10.15488/16831
2023
Barlag T, Hannula M, Kontinen J, Pardal N, Virtema J. Unified Foundations of Team Semantics via Semirings. In Marquis P, Son TC, Kern-Isberner G, editors, Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning, KR 2023. Association for the Advancement of Artificial Intelligence. 2023. p. 75-85. (Proceedings of the International Conference on Knowledge Representation and Reasoning). doi: 10.48550/arXiv.2303.07926, 10.24963/kr.2023/8
Chandoo M. Logical labeling schemes. Discrete mathematics. 2023 Oct;346(10):113565. Epub 2023 Jun 20. doi: 10.15488/11960, 10.1016/j.disc.2023.113565
Fichte JK, Hecher M, Mahmood Y, Meier A. Quantitative Reasoning and Structural Complexity for Claim-Centric Argumentation. In Elkind E, editor, Proceedings of the 32nd International Joint Conference on Artificial Intelligence, IJCAI 2023. 2023. p. 3212-3220. (IJCAI International Joint Conference on Artificial Intelligence). doi: 10.24963/ijcai.2023/358
Haak A, Meier A, Prakash O, Rao BVR. Parameterised Counting in Logspace. ALGORITHMICA. 2023 Oct;85(10):2923-2961. 10. Epub 2023 Apr 21. doi: 10.1007/s00453-023-01114-2
Hannula M, Hirvonen M, Kontinen J, Mahmood Y, Meier A, Virtema J. Logics with Probabilistic Team Semantics and the Boolean Negation. In Gaggl S, Martinez MV, Ortiz M, Ortiz M, editors, JELIA 2023: Logics in Artificial Intelligence. Cham: Springer. 2023. p. 665-680. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.48550/arXiv.2306.00420, 10.1007/978-3-031-43619-2_45
Mahmood Y, Meier A, Schmidt J. Parameterized Complexity of Logic-based Argumentation in Schaefer's Framework. ACM Trans. Comput. Log. 2023 May 10;24(3):26:1-26:25. 26. Epub 2023 Jan 31. doi: 10.1145/3582499
2022
Creignou N, Durand A, Vollmer H. Enumeration Classes Defined by Circuits. In Szeider S, Ganian R, Silva A, editors, 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
Fröhlich N, Meier A. Submodel Enumeration of Kripke Structures in Modal Logic. In Fernandez-Duque D, Palmigiano A, Palmigiano A, Pinchinat S, editors, AiML. 2022. p. 391-406. (Advances in Modal Logic).
Gaube SA, Schober B. Algorithmic local monomialization of a binomial: a comparison of different approaches. International Journal of Algebra and Computation. 2022 Dec 9;33(1):161-195. doi: 10.48550/arXiv.2012.14910, 10.1142/S0218196723500108
Gutsfeld JO, Meier A, Ohrem C, Virtema J. Temporal Team Semantics Revisited. In LICS 22: Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science. New York: Association for Computing Machinery (ACM). 2022. p. 44:1-44:13. 3533360 Epub 2022 Aug 4. doi: 10.1145/3531130.3533360
Haak A, Meier A, Müller F, Vollmer H. Enumerating teams in first-order team logics. Annals of Pure and Applied Logic. 2022 Dec;173(10):103163. Epub 2022 Jun 14. doi: 10.1016/j.apal.2022.103163
Kontinen J, Meier A, Mahmood Y. A parameterized view on the complexity of dependence and independence logic. J. Log. Comput. 2022 Dec;32(8):1624-1644. Epub 2022 Nov 14. doi: 10.1093/logcom/exac070
Kontinen J, Meier A, Mahmood Y. A Parameterized View on the Complexity of Dependence Logic. In Artemov S, Nerode A, editors, Logical Foundations of Computer Science: International Symposium, LFCS 2022, Deerfield Beach, FL, USA, January 10-13, 2022, Proceedings.. Cham. 2022. p. 125-142. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2021 Dec 16. doi: 10.1007/978-3-030-93100-1_9
Mahmood Y, Meier A. Parameterised complexity of model checking and satisfiability in propositional dependence logic. Annals of Mathematics and Artificial Intelligence. 2022 Mar;90(2-3):271-296. Epub 2021 Feb 27. doi: 10.48550/arXiv.1904.06107, 10.1007/s10472-021-09730-w
2021
Barlag T, Vollmer H. A Logical Characterization of Constant-Depth Circuits over the Reals. In Silva A, Wassermann R, de Queiroz R, editors, Logic, Language, Information, and Computation: 27th International Workshop, WoLLIC 2021, Virtual Event, October 5–8, 2021, Proceedings. Vol. abs/2005.04916. Springer, Cham. 2021. p. 16-30. (Lecture Notes in Computer Science (LNCS)). Epub 2021 Oct 6. doi: 10.1007/978-3-030-88853-4_2
Durand A, Haak A, Kontinen JA, Vollmer H. Descriptive complexity of #P functions: A new perspective. Journal of Computer and System Sciences. 2021 Mar;116:40-54. Epub 2020 Apr 30. doi: 10.1016/j.jcss.2020.04.002
Fichte JK, Hecher M, Mahmood Y, Meier A. Decomposition-Guided Reductions for Argumentation and Treewidth. In Zhou ZH, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021.. 2021. p. 1880-1886. (IJCAI International Joint Conference on Artificial Intelligence). doi: 10.24963/ijcai.2021/259
Fichte JK, Hecher M, Meier A. Knowledge-Base Degrees of Inconsistency - Complexity and Counting. In 35th AAAI Conference on Artificial Intelligence, AAAI 2021. 2021. p. 6349-6357. (AAAI-21 Technical Tracks; 7). doi: 10.1609/aaai.v35i7.16788
Haak A. Descriptive Complexity of Circuit-Based Counting Classes. Hannover: Leibniz Universität Hannover, 2021. 183 p. doi: 10.15488/11353
Haak A, Meier A, Prakash O, Rao BVR. Parameterised Counting in Logspace. In Blaser M, Monmege B, editors, 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021. 2021. p. 1-17. 40. (Leibniz International Proceedings in Informatics, LIPIcs). Epub 2019. doi: 10.48550/arXiv.1904.12156, 10.4230/LIPICS.STACS.2021.40
Mahmood Y, Meier A, Schmidt J. Parameterized complexity of abduction in Schaefer's framework. J. Log. Comput. 2021 Jan;31(1):266-296. 1. Epub 2020 Dec 29. doi: 10.1093/logcom/exaa079
Mahmood Y, Meier A, Schmidt J. Parameterized Complexity of Logic-Based Argumentation in Schaefer's Framework. In 35th AAAI Conference on Artificial Intelligence, AAAI 2021. 2021. p. 6426-6434 doi: 10.1609/aaai.v35i7.16797
2020
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 Oct. doi: 10.1145/3356043
Lück M. Team Logic: Axioms, Expressiveness, Complexity. Hannover: Leibniz Universität Hannover, 2020. 216 p. doi: 10.15488/9376
Mahmood Y, Meier A, Schmidt J. Parameterised Complexity of Abduction in Schaefer’s Framework. In Artemov S, Nerode A, editors, Logical Foundations of Computer Science (LFCS 2020): International Symposium, LFCS 2020, Proceedings. Cham: Springer. 2020. p. 195-213. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2019 Dec 20. doi: 10.48550/arXiv.1906.00703, 10.1007/978-3-030-36755-8_13
Mahmood Y, Meier A. Parameterised Complexity of Model Checking and Satisfiability in Propositional Dependence Logic. In Herzig A, Kontinen J, editors, Foundations of Information and Knowledge Systems - 11th International Symposium, FoIKS 2020, Dortmund, Germany, February 17-21, 2020, Proceedings. Springer. 2020. p. 157-174. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-39951-1_10, 10.15488/12823
Meier A. Incremental FPT delay. Algorithms. 2020 May 15;13(5):122. doi: 10.3390/A13050122
Meier A. Parametrised enumeration. Hannover: Leibniz Universität Hannover, 2020. 111 p. doi: 10.15488/9427
2019
Creignou N, Kröll M, Pichler R, Skritek S, Vollmer H. A complexity theory for hard enumeration problems. Discrete applied mathematics. 2019 Sept 15;268:191-209. Epub 2019 Mar 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 Sept;12(9):189. 9. Epub 2019 Sept 9. doi: 10.3390/a12090189, 10.15488/10960
Fichte JK, Hecher M, Meier A. Counting complexity for reasoning in abstract argumentation. In AAAI-19, IAAI-19, EAAI-19 Proceedings. Vol. 1. AAAI Press/International Joint Conferences on Artificial Intelligence. 2019. p. 2827-2834. (Proceedings of the AAAI Conference on Artificial Intelligence). doi: 10.48550/arXiv.1811.11501, 10.1609/aaai.v33i01.33012827
Greenyer J, Gritzner D, Harel D, Marron A. Towards Automated Defect Analysis Using Execution Traces of Scenario-Based Models. In Pires LF, Selic B, Hammoudi S, editors, Model-Driven Engineering and Software Development: 6th International Conference, MODELSWARD 2018, Revised Selected Papers. Springer Verlag. 2019. p. 335-354. (Communications in Computer and Information Science). doi: 10.1007/978-3-030-11030-7_15
Haak A, Vollmer H. A model-theoretic characterization of constant-depth arithmetic circuits. Annals of Pure and Applied Logic. 2019 Sept;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 JP, editors, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Vol. abs/1902.00246. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2019. p. 19:1-19:15. 19. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.MFCS.2019.19, 10.48550/arXiv.1902.00246
Hella L, Kuusisto A, Meier A, Virtema J. Model checking and validity in propositional and modal inclusion logics. Journal of logic and computation. 2019 Sept;29(5):605-630. Epub 2019 Apr 10. doi: 10.1093/logcom/exz008, 10.15488/3364
Krebs A, Meier A, Mundhenk M. The model checking fingerprints of CTL operators. Acta informatica. 2019 Sept 1;56(6):487-519. Epub 2018 Aug 1. doi: 10.48550/arXiv.1504.04708, 10.1007/s00236-018-0326-9
Meier A, Ordyniak S, Ramanujan MS, Schindler I. Backdoors for Linear Temporal Logic. ALGORITHMICA. 2019 Feb 15;81(2):476-496. Epub 2018 Sept 18. doi: 10.1007/s00453-018-0515-5, 10.15488/1267
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
2018
Chandoo M. Computational complexity aspects of implicit graph representations. Hannover: Leibniz Universität Hannover, 2018. 89 p. doi: 10.15488/3569
Durand A, Hannula M, Kontinen J, Meier A, Virtema J. Approximation and dependence via multiteam semantics. Annals of Mathematics and Artificial Intelligence. 2018 Aug;83(3-4):297-320. Epub 2018 Jan 18. doi: 10.1007/s10472-017-9568-4, 10.48550/arXiv.1510.09040
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. p. 354-363. (Proceedings - Symposium on Logic in Computer Science). doi: https://arxiv.org/pdf/1710.01934.pdf, 10.1145/3209108.3209179
Durand A, Hannula M, Kontinen J, Meier A, Virtema J. Probabilistic team semantics. In Woltran S, Ferrarotti F, editors, Foundations of Information and Knowledge Systems - 10th International Symposium, FoIKS 2018, Proceedings. Springer Verlag. 2018. p. 186-206. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-90050-6_11
Dürr C, Vollmer H. Preface of STACS 2016 Special Issue. Theory of Computing Systems. 2018 Jan;62(1):1-3. Epub 2017 Dec 4. doi: 10.1007/s00224-017-9830-5
Fichte JK, Hecher M, Schindler I. Default Logic and Bounded Treewidth. In Martin-Vide C, Klein ST, Shapira D, editors, Language and Automata Theory and Applications - 12th International Conference, LATA 2018, Proceedings. Springer Verlag. 2018. p. 130-142. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2018 Mar 8. doi: 10.48550/arXiv.1706.09393, 10.1007/978-3-319-77313-1_10
Greenyer J, Gritzner D, Harel D, Marron A. Towards systematic and automatic handling of execution traces associated with scenario-based models. In Hammoudi S, Pires LF, Selic B, editors, MODELSWARD 2018 - Proceedings of the 6th International Conference on Model-Driven Engineering and Software Development. SciTePress. 2018. p. 560-566 doi: 10.5220/0006671105600566
Krebs A, Meier A, Virtema J, Zimmermann M. Team semantics for the specification and verification of hyperproperties. In Potapov I, Worrell J, Spirakis P, editors, 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2018. 10. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.MFCS.2018.10
Meier A, Reinbold C. Enumeration complexity of poor man’s propositional dependence logic. In Woltran S, Ferrarotti F, editors, Foundations of Information and Knowledge Systems: 10th International Symposium, FoIKS 2018, Budapest, Hungary, May 14–18, 2018, Proceedings. 1. ed. Springer Verlag. 2018. p. 303-321. (Lecture Notes in Computer Science (LNCS)). (Information Systems and Applications, incl. Internet/Web, and HCI (LNISA)). Epub 2018 Apr 18. doi: 10.48550/arXiv.1704.03292, 10.1007/978-3-319-90050-6_17
Meier A. Enumeration in Incremental FPT-Time. 2018 Apr 20. Epub 2018 Apr 20.
Schindler I. Parameterized complexity of decision problems in non-classical logics. Hannover: Leibniz Universität Hannover, 2018. 117 p. doi: 10.15488/3570
Steinberg S, Greenyer J, Gritzner D, Harel D, Katz G, Marron A. Efficient distributed execution of multi-component scenario-based models. In Selic B, Pires LF, Hammoudi S, editors, Model-Driven Engineering and Software Development. Springer Verlag. 2018. p. 449-483. (Communications in Computer and Information Science). doi: 10.1007/978-3-319-94764-8_19
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.
2017
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. p. 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 May 1;60(4):737-758. Epub 2016 Sept 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.
Hella L, Kuusisto A, Meier A, Virtema J. Model checking and validity in propositional and modal inclusion logics. In Larsen KG, Raskin JF, Bodlaender HL, editors, 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2017. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.MFCS.2017.32
Luck M, Meier A, Schindler I. Parametrised complexity of satisfiability in temporal logic. ACM Transactions on Computational Logic. 2017 Jan;18(1):1. doi: 10.1145/3001835
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 (Print). 2017;66.
2016
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. p. 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, Hannula M, Kontinen J, Meier A, Virtema J. Approximation and Dependence via Multiteam Semantics. In Gyssens M, Simari G, editors, Foundations of Information and Knowledge Systems: 9th International Symposium, FoIKS 2016, Linz, Austria, March 7-11, 2016. Proceedings. Cham: Springer. 2016. p. 271-291. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-30024-5_15, 10.1007/s10472-017-9568-4
Durand A, Haak A, Kontinen J, Vollmer H. Descriptive complexity of #AC0 functions. In Talbot JM, Regnier L, editors, 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. p. 5-32 Epub 2016 Jun 30. doi: 10.1007/978-3-319-31803-5_2
Fichte JK, Meier A, Schindler I. Strong Backdoors for Default Logic. In Le Berre D, Creignou N, editors, Theory and Applications of Satisfiability Testing – SAT 2016 - 19th International Conference, Proceedings. Cham: Springer. 2016. p. 45-59. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2016 Jun 11. doi: 10.1007/978-3-319-40970-2_4
Haak A, Vollmer H. A Model-Theoretic Characterization of Constant-Depth Arithmetic Circuits. In Väänänen J, Hirvonen Å, de Queiroz R, editors, Logic, Language, Information, and Computation: 23rd International Workshop, WoLLIC 2016, Puebla, Mexico, August 16-19th, 2016. Proceedings. Berlin: Springer Verlag. 2016. p. 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
Hella L, Kuusisto A, Meier A, Virtema J. Model Checking and Validity in Propositional and Modal Inclusion Logics. 2016. (CoRR).
Kontinen J, Müller JS, Schnoor H, Vollmer H. Modal independence logic. Journal of Logic and Computation. 2016 Jun 25;27(5):1333-1352. doi: 10.1093/logcom/exw019
Meier A, Ordyniak S, Sridharan R, Schindler I. Backdoors for Linear Temporal Logic. In Guo J, Hermelin D, editors, 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, August 24-26, 2016, Aarhus, Denmark. Vol. 63. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany. 2016. p. 23:1-23:17. 23. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.IPEC.2016.23
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 (Print). 2016;47.
2015
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 JS, 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. p. 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 Sept;24:289-305. Epub 2015 Jun 25. doi: 10.48550/arXiv.1109.4750, 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. p. 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. p. 281-292 doi: 10.1007/978-3-662-48057-1_22
Kontinen J, Müller JS, Schnoor H, Vollmer H. A Van Benthem Theorem for Modal Team Semantics. In 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). 2015. p. 277-291 doi: 10.4230/LIPICS.CSL.2015.277
Krebs A, Meier A, Virtema J. A Team Based Variant of CTL. In 22nd International Symposium on Temporal Representation and Reasoning, TIME 2015, Kassel, Germany, September 23-25, 2015. 2015. p. 140-149 doi: 10.1109/TIME.2015.11
Krebs A, Meier A, Virtema J. Parallel Computational Tree Logic. 2015. (CoRR).
Krebs A, Meier A, Mundhenk M. The model checking fingerprints of CTL operators. In Grandi F, Lange M, Lomuscio A, editors, 22nd International Symposium on Temporal Representation and Reasoning, TIME 2015, Kassel, Germany, September 23-25, 2015. IEEE Computer Society. 2015. p. 101-110. (CoRR). doi: 10.1109/TIME.2015.13
Lück M, Meier A. LTL Fragments are Hard for Standard Parameterisations. In 22nd International Symposium on Temporal Representation and Reasoning, TIME 2015, Kassel, Germany, September 23-25, 2015. 2015. p. 59-68 doi: 10.1109/TIME.2015.9
Lück M, Meier A, Schindler I. Parameterized Complexity of CTL - A Generalization of Courcelle's Theorem. In Dediu AH, Formenti E, Martín-Vide C, Truthe B, editors, Language and Automata Theory and Applications - 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings. Vol. 8977. Springer. 2015. p. 549-560. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-15579-143
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
2014
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 JS, Vollmer H. A Fragment of Dependence Logic Capturing Polynomial Time. Logical methods in computer science: LMCS. 2014;10(3). doi: 10.2168/LMCS-10(3:3)2014
Kontinen J, Müller JS, Schnoor H, Vollmer H. Modal Independence Logic. In Goré R, Kooi BP, Kurucz A, editors, 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. p. 353-372
Lück M, Meier A, Schindler I. Parameterized Complexity of CTL: Courcelle's Theorem For Infinite Vocabularies. Electronic colloquium on computational complexity (ECCC). 2014;2014:134.
2013
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 JS, Schmidt J, Vollmer H. Paradigms for Parameterized Enumeration. In Chatterjee K, Sgall J, editors, Mathematical Foundations of Computer Science 2013: 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Springer Berlin Heidelberg. 2013. p. 290-301. (Lecture Notes in Computer Science (LNCS)). doi: 10.1007/978-3-642-40313-2_27
Creignou N, Meier A, Müller JS, Schmidt J, Vollmer H. Paradigms for Parameterized Enumeration. 2013. (CoRR).
Creignou N, Ktari R, Meier A, Müller JS, Olive F, Vollmer H. Parameterized Enumeration with Ordering. 2013.
Ebbing J, Hella L, Meier A, Müller JS, 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. p. 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
Meier A, Schneider T. Generalized satisfiability for the description logic ALC. Theor. Comput. Sci. 2013 Sept 23;505:55-73. doi: 10.1016/J.TCS.2013.02.009
Müller JS, Vollmer H. Model Checking for Modal Dependence Logic: An Approach Through Post's Lattice. In Logic, Language, Information, and Computation. 2013. p. 238-250 doi: 10.1007/978-3-642-39992-3_21
2012
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. Electronic colloquium on computational complexity (ECCC). 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 Transactions on Computational Logic. 2012 Apr;13(2):a17. doi: 10.1145/2159531.2159539
Datta S, Mahajan M, Raghavendra Rao BV, Thomas M, Vollmer H. Counting classes and the fine structure between N C 1 and L. Theoretical computer science. 2012 Feb 3;417:36-49. Epub 2011 Jun 13. doi: 10.1016/j.tcs.2011.05.050
Göller S, Meier A, Mundhenk M, Schneider T, Thomas M, Weiß F. The Complexity of Monotone Hybrid Logics over Linear Frames and the Natural Numbers. In Advances in Modal Logic 9, papers from the ninth conference on "Advances in Modal Logic," held in Copenhagen, Denmark, 22-25 August 2012. 2012. p. 261-278
Meier A, Müller JS, Mundhenk M, Vollmer H. Complexity of Model Checking for Logics over Kripke models. Bull. EATCS. 2012;108:49-89.
Meier A. Generalized Complexity of ALC Subsumption. 2012. (CoRR).
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. p. 389-400 doi: 10.1007/978-3-642-28332-1_33
2011
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. Logical methods in computer science: LMCS. 2011;7(2). doi: 10.2168/LMCS-7(2:12)2011
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, Proceedings. 2011. p. 84-95. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-22993-0_11
Durand A, Ebbing J, Kontinen J, Vollmer H. Dependence logic with a majority quantifier. In Proceedings of the 31st International Conference on Foundations of Software Technology and Theoretical Computer Science. 2011. p. 252-263. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.FSTTCS.2011.252
Meier A, Schneider T. Generalized Satisfiability for the Description Logic ALC - (Extended Abstract). In Ogihara M, Tarui J, editors, Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Tokyo, Japan, May 23-25, 2011. Proceedings. Vol. 6648. Springer. 2011. p. 552-562. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-20877-553
Meier A. On the Complexity of Modal Logic Variants and their Fragments. Cuvillier, 2011.
Meier A, Müller S, Thomas M, Vollmer H. Proof complexity of propositional default logic. Archive for Mathematical Logic. 2011;50(7-8):727-742. doi: 10.1007/s00153-011-0245-8
Vöcking B, Alt H, Dietzfelbinger M, Reischuk R, Scheideler C, Vollmer H et al. Algorithms Unplugged. 2011. (Fachbuch). doi: 10.1007/978-3-642-15328-0
2010
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, editors, Theory and Applications of Satisfiability Testing: SAT 2010, 13th International Conference, SAT 2010, Edinburgh, UK, July 11-14, 2010. Proceedings. Springer. 2010. p. 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. In Dagstuhl Seminar: Circuits, Logic, and Games 2010. Vol. 10061. 2010. (Dagstuhl Seminar Proceedings (DSP)).
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. Logical methods in computer science: LMCS. 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∗. In Dagstuhl Seminar: Circuits, Logic, and Games 2010. Vol. 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. p. 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. Electronic colloquium on computational complexity (ECCC). 2010;TR10.
Kontinen J, Vollmer H. On Second-Order Monadic Monoidal and Groupoidal Quantifiers. Logical methods in computer science: LMCS. 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, editors, Computer Science Logic: 24th International Workshop, CSL 2010, 19th Annual Conference of the EACSL, Brno, Czech Republic, August 23-27, 2010. Proceedings. Springer. 2010. p. 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
Meier A, Mundhenk M, Schneider T, Thomas M, Weber V, Weiss F. The complexity of satisfiability for fragments of hybrid logic - Part I. IMA Journal of Applied Mathematics. 2010;8(4):409-421. doi: 10.1016/J.JAL.2010.08.001
Meier A, Schneider T. The Complexity of Satisfiability for Sub-Boolean Fragments of ALC. In Proceedings of the 23rd International Workshop on Description Logics (DL 2010). 2010
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
Rossman B, Schwentick T, Thérien D, Vollmer H. Circuits, Logic, and Games. Dagstuhl Seminar Proceedings (DSP). 2010;10061.
Thomas M, Vollmer H. Complexity of Non-Monotonic Logics. Bull. EATCS. 2010;102:53-82.
2009
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. Logical methods in computer science: LMCS. 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. Electronic Notes in Theoretical Computer Science (ENTCS). 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 JF, editors, TIME 2009, 16th International Symposium on Temporal Representation and Reasoning, Bressanone-Brixen, Italy, 23-25 July 2009, Proceedings. IEEE Computer Society. 2009. p. 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
Meier A, Mundhenk M, Schneider T, Thomas M, Weber V, Weiss F. The Complexity of Satisfiability for Fragments of Hybrid Logic-Part I. In Královic R, Niwinski D, editors, Mathematical Foundations of Computer Science 2009, 34th International Symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009. Proceedings. Vol. 5734. Springer. 2009. p. 587-599. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-03816-750
2008
Bauland M, Schneider T, Schnoor H, Schnoor I, Vollmer H. The Complexity of Generalized Satisfiability for Linear Temporal Logic. Logical methods in computer science: LMCS. 2008 Dec 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, editor, Theory and Applications of Satisfiability Testing - SAT 2009, 12th International Conference, SAT 2009, Swansea, UK, June 30 - July 3, 2009. Proceedings. Vol. 5584. Springer. 2008. p. 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). Vol. 223. 2008. p. 201-213. (Electron. Notes Theor. Comput. Sci.). doi: 10.1016/j.entcs.2008.12.040
2007
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. p. 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
Schwentick T, Thérien D, Vollmer H. Circuits, Logic, and Games, 06451. Dagstuhl Seminar Proceedings (DSP). 2007;6451.
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. p. 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
2006
Creignou N, Kolaitis PG, Vollmer H. Executive Summary of Dagstuhl-Seminar Complexity of Constraints, 06401. Dagstuhl Seminar Proceedings (DSP). 2006;6401.
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
2005
Allender E, Bauland M, Immerman N, Schnoor H, Vollmer H. The complexity of satisfiability problems: Refining Schaefer's theorem. Lecture Notes in Computer Science. 2005;3618:71-82. doi: 10.1007/11549345_8
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 Oct 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
2004
Böhler E, Hemaspaandra E, Reith S, Vollmer H. The complexity of Boolean constraint isomorphism. In Diekert V, Habib M, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2004. p. 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
2003
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.
2002
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.
2001
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. p. 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
2000
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
1999
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
1998
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 Sept 28.
Reith S, Vollmer H. The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae. 1998 Sept 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
1997
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
1996
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.
1995
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
1994
Vollmer H. On different reducibility notions for function classes. 1994.
1993
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
1991
Vollmer H. The gap-language-technique revisited. 1991. doi: 10.1007/3-540-54487-9_72
