Descriptive Complexity of Parameterised Counting Classes
PD Dr. rer. nat. habil. Arne Meier
© Institut für Theoretische Informatik
PD Dr. rer. nat. habil. Arne Meier
Phone
Email
Address
Appelstraße 9a
30167 Hannover
30167 Hannover
Building
Room
© Institut für Theoretische Informatik
PD Dr. rer. nat. habil. Arne Meier
Phone
Email
My area of expertise is complexity theory. Currently, I focus on the parameterised complexity of problems in non-classical logics. Furthermore, I study enumeration algorithms.
I also enjoy typography and the text typesetting system LaTeX.
INTERESTS
- (Parameterised) Complexity Theory
- Logic in Computer Science (particularly, non-classical logics)
- (Parameterised) Enumeration Algorithms
- LaTeX (see my personal GitHub-Webside for a timeline LaTeX/TikZ package.
ACTIVITIES
-
PC Member
Current/Future Program Committes: AAAI 2023, FoIKS 2024 (co-chair)
Past Program Committees: LCC 2019, AAAI 2021, IJCAI 2021 (distinguished PC), IJCAI 2022 (distinguished PC)
-
Reviewing
Conferences: TAMC'11, SAT'12, STACS'12, SAT'13, AiML'14, STACS'14, SAT'14, ICALP'14, STACS'15, FoSSaCS'15, STACS'16, MFCS'16, WoLLIC'16, STACS'17, STACS'18, SAT'18, CiE'18, CSL'18, CSR'19, STACS'20, ICALP'20, LoDE'20, STACS'21, AAAI'21, ICALP'21, IJCAI'21, ESA'21, CSL'21, LoDE'21, CSL'22, STOC'22, LICS'22, ESA'22, IJCAI'22, MFCS'22
-
Research Projects
Nonclassical logics: parametrised and enumeration complexity
-
Member of Steering Committees
Speaker GI-Special Interest Group ComplexitySTACS
PUBLICATIONS
-
Journal contributions
2022
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. doi.org/10.1007/s10472-021-09730-w
2021
Mahmood Y, Meier A, Schmidt J. Parameterized complexity of abduction in Schaefer's framework. J. Log. Comput. 2021 Jan;31(1):266-296. 1. doi.org/10.1093/logcom/exaa079
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. doi.org/10.1145/3356043
Meier A. Incremental FPT delay. Algorithms. 2020 May 15;13(5). 122. doi.org/10.3390/A13050122
2019
Creignou N, Ktari R, Meier A, Müller JS, Olive F, Vollmer H. Parameterised enumeration for modification problems. Algorithms. 2019 Sep 9;12(9):189. 9. doi.org/10.3390/a12090189
Hella L, Kuusisto A, Meier A, Virtema J. Model checking and validity in propositional and modal inclusion logics. Journal of logic and computation. 2019 Sep 1;29(5):605-630. doi.org/10.1093/logcom/exz008
Krebs A, Meier A, Mundhenk M. The model checking fingerprints of CTL operators. Acta informatica. 2019 Sep 1;56(6):487-519. doi.org/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. doi.org/10.1007/s00453-018-0515-5
2018
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. doi.org/10.1007/s10472-017-9568-4
2017
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. doi.org/10.1007/s00224-016-9702-4
Luck M, Meier A, Schindler I. Parametrised complexity of satisfiability in temporal logic. ACM Transactions on Computational Logic. 2017 Jan;18(1). 1. doi.org/10.1145/3001835
2015
Meier A, Thomas M, Vollmer H, Mundhenk M. Erratum: The Complexity of Satisfiability for Fragments of CTL and CTL^star. Int. J. Found. Comput. Sci. 2015;26(8):1189. doi.org/10.1142/S012905411592001X
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.org/10.1007/S00153-015-0435-X
2013
Meier A, Schneider T. Generalized satisfiability for the description logic ALC. Theor. Comput. Sci. 2013 Sep 23;505:55-73. doi.org/10.1016/J.TCS.2013.02.009
2012
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.org/10.1093/LOGCOM/EXQ061
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.org/10.1145/2159531.2159539
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.
2011
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.org/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.org/10.1007/S00153-011-0245-8
2010
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.org/10.1016/J.JAL.2010.08.001
-
Conference contributions
2022
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)). doi.org/10.1007/978-3-030-93100-1_9
2021
Fichte JK, Hecher M, Mahmood Y, Meier A. Decomposition-Guided Reductions for Argumentation and Treewidth. In Zhou Z-H, 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.org/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
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, March 16-19, 2021, Saarbrücken, Germany (Virtual Conference). 2021. p. 1-17. 40. (Leibniz International Proceedings in Informatics, LIPIcs). doi.org/10.4230/LIPICS.STACS.2021.40
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. (35th AAAI Conference on Artificial Intelligence, AAAI 2021).
2020
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: International Symposium, LFCS 2020, Proceedings. Springer. 2020. p. 195-213. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi.org/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. Vol. 12012. Springer. 2020. p. 157-174. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi.org/10.1007/978-3-030-39951-1_10
2019
Fichte JK, Hecher M, Meier A. Counting complexity for reasoning in abstract argumentation. In 33rd AAAI Conference on Artificial Intelligence, AAAI 2019. AAAI Press/International Joint Conferences on Artificial Intelligence. 2019. p. 2827-2834
2018
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.org/10.1007/978-3-319-90050-6_11
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.org/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, Proceedings. Springer Verlag. 2018. p. 303-321. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi.org/10.1007/978-3-319-90050-6_17
2017
Hella L, Kuusisto A, Meier A, Virtema J. Model checking and validity in propositional and modal inclusion logics. In Larsen KG, Raskin J-F, 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.org/10.4230/LIPIcs.MFCS.2017.32
2016
Durand A, Hannula M, Kontinen J, Meier A, Virtema J. Approximation and Dependence via Multiteam Semantics. In Gyssens M, Simari GR, editors, Foundations of Information and Knowledge Systems - 9th International Symposium, FoIKS 2016, Linz, Austria, March 7-11, 2016. Proceedings. Vol. 9616. Springer. 2016. p. 271-291. (Lecture Notes in Computer Science). doi.org/10.1007/978-3-319-30024-515
Fichte JK, Meier A, Schindler I. Strong Backdoors for Default Logic. In Theory and Applications of Satisfiability Testing - SAT 2016 - 19th International Conference, Bordeaux, France, July 5-8, 2016, Proceedings.. 2016. p. 45-59 doi.org/10.1007/978-3-319-40970-2_4
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. (LIPIcs). doi.org/10.4230/LIPIcs.IPEC.2016.23
2015
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. p. 524-536 doi.org/10.1007/978-3-319-15579-1_41
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.org/10.1007/978-3-662-48057-1_22
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.org/10.1109/TIME.2015.11
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.org/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.org/10.1109/TIME.2015.9
-
Technical reports
2021
Gutsfeld JO, Meier A, Ohrem C, Virtema J. Temporal Team Semantics Revisited. 2021 Oct 25. (CoRR).
2020
Haak A, Meier A, Müller F, Vollmer H. Enumerating Teams in First-Order Team Logics. 2020.
2019
Haak A, Meier A, Prakash O, Rao BVR. Parameterised Counting Classes with Bounded Nondeterminism. 2019. (CoRR).
Mahmood Y, Meier A, Schmidt J. Parameterised Complexity for Abduction. 2019. (CoRR).
Mahmood Y, Meier A. Parametrised Complexity of Model Checking and Satisfiability in Propositional Dependence Logic. 2019. (CoRR).
2018
Meier A. Enumeration in Incremental FPT-Time. 2018 Apr 20.
2017
Meier A, Reinbold C. Enumeration Complexity of Poor Man's Propositional Dependence Logic. 2017. (CoRR).
2016
Hella L, Kuusisto A, Meier A, Virtema J. Model Checking and Validity in Propositional and Modal Inclusion Logics. 2016. (CoRR).
2015
Krebs A, Meier A, Virtema J. Parallel Computational Tree Logic. 2015. (CoRR).
2013
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.
2012
Meier A. Generalized Complexity of ALC Subsumption. 2012. (CoRR).
2010
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).
-
Theses
2020
Meier A. Parametrised enumeration. 2020. doi.org/10.15488/9427
2011
Meier A. On the Complexity of Modal Logic Variants and their Fragments. Cuvillier, 2011.
