Publications

2019

• A. Dawar, E. Grädel, and W. Pakusa. Approximations of Isomorphism and Logics with Linear-Algebraic Operators. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) (C. Baier, I. Chatzigiannakis, P. Flocchini, and S. Leonardi, Eds.), vol. 132 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 112:1–112:14, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019.             
  BibTeX

  @inproceedings{dawar_et_al:LIPIcs:2019:10688,
       author = {Anuj Dawar and Erich Gr{\"a}del and Wied Pakusa},
       title = {{Approximations of Isomorphism and Logics with Linear-Algebraic Operators}},
       booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
       pages = {112:1--112:14},
       series = {Leibniz International Proceedings in Informatics (LIPIcs)},
       isbn = {978-3-95977-109-2},
       issn = {1868-8969},
       year = {2019},
       volume = {132},
       editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
       publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
       address = {Dagstuhl, Germany},
       url = {http://drops.dagstuhl.de/opus/volltexte/2019/10688},
       urn = {urn:nbn:de:0030-drops-106887},
       doi = {10.4230/LIPIcs.ICALP.2019.112},
       annote = {Keywords: Finite Model Theory, Graph Isomorphism, Descriptive Complexity, Algebra},
  }
  

• A. Dawar, E. Grädel, and W. Pakusa. Approximations of Isomorphism and Logics with Linear-Algebraic Operators. arXiv:1902.06648 [cs.LO], 2019.             
  BibTeX

  @misc{DGP19,
       title = {Approximations of Isomorphism and Logics with Linear-Algebraic Operators},
       author = {Anuj Dawar and Erich Gr{\"a}del and Wied Pakusa},
       url = {https://arxiv.org/abs/1902.06648},
       howpublished = {arXiv:1902.06648 [cs.LO]},
       year = {2019},
       month = {February},
  }
  

• E. Grädel, M. Grohe, B. Pago, and W. Pakusa. A Finite-Model-Theoretic View on Propositional Proof Complexity. Logical Methods in Computer Science, vol. Volume 15, Issue 1, 2019.             
  BibTeX

  @article{GGPW19,
       title = {{A Finite-Model-Theoretic View on Propositional Proof Complexity}},
       author = {Erich Gr{\"a}del and Martin Grohe and Benedikt Pago and Wied Pakusa},
       url = {https://lmcs.episciences.org/5119},
       doi = {},
       journal = {{Logical Methods in Computer Science}},
       volume = {{Volume 15, Issue 1}},
       year = {2019},
       month = {January},
  }
  

• E. Grädel and W. Pakusa. Rank logic is dead, long live rank logic! The Journal of Symbolic Logic, vol. 84(1), 2019.             
  BibTeX

  @article{GW19,
       title = {{Rank logic is dead, long live rank logic!}},
       author = {Erich Gr{\"a}del and Wied Pakusa},
       url = {https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/rank-logic-is-dead-long-live-rank-logic/F161E336281F2B67E8B3E4CDA5614933},
       doi = {{10.1017/jsl.2018.33}},
       journal = {The Journal of Symbolic Logic},
       volume = {84},
       number = {1},
       publisher = {Cambridge University Press},
       year = {2019},
       month = {March},
  }
  

2017

• F. Abu Zaid, A. Dawar, E. Grädel, and W. Pakusa. Definability of Summation Problems for Abelian Groups and Semigroups. In Proceedings of 32th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2017.             
  BibTeX

  @inproceedings{AbuDawGraPak17,
       author = {Faried {Abu Zaid} and Anuj Dawar and Erich Gr{\"a}del and Wied Pakusa},
       title = {{Definability of Summation Problems for Abelian Groups and Semigroups}},
       url = {http://www.logic.rwth-aachen.de/pub/graedel/AbuzaidDawGraPak17.pdf},
       booktitle = {{Proceedings of 32th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)}},
       year = {2017},
  }
  

• M. Grohe and W. Pakusa. Descriptive Complexity of Linear Equation Systems and Applications to Propositional Proof Complexity. In Proceedings of 32th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2017.             
  BibTeX

  @inproceedings{GroPak17,
       author = {Martin Grohe and Wied Pakusa},
       title = {{Descriptive Complexity of Linear Equation Systems and Applications to Propositional Proof Complexity}},
       url = {http://www.logic.rwth-aachen.de/pub/pakusa/GrohePak17.pdf},
       booktitle = {{Proceedings of 32th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)}},
       year = {2017},
  }
  

• E. Grädel, B. Pago, and W. Pakusa. The Model-Theoretic Expressiveness of Propositional Proof Systems. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017), 2017.             
  BibTeX

  @inproceedings{GrPaPa17,
       author = {Erich Gr{\"a}del and Benedikt Pago and Wied Pakusa},
       title = {{The Model-Theoretic Expressiveness of Propositional Proof Systems}},
       url = {http://www.logic.rwth-aachen.de/pub/graedel/GrPaPa17.pdf},
       booktitle = {{26th EACSL Annual Conference on Computer Science Logic (CSL 2017)}},
       year = {2017},
  }
  

2016

• W. Pakusa. Linear Equation Systems and the Search for a Logical Characterisation of Polynomial Time. PhD thesis, RWTH Aachen University, 2016.             
  BibTeX

  @phdthesis{Pakusa16,
       author = {Wied Pakusa},
       school = {{RWTH} Aachen University},
       title = {Linear Equation Systems and the Search for a Logical Characterisation of Polynomial Time},
       url = {https://logic.rwth-aachen.de/~pakusa/diss.pdf},
       year = {2016},
  }
  

• W. Pakusa, S. Schalthöfer, and E. Selman. Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time. In 25th EACSL Annual Conference on Computer Science Logic (CSL 2016) (J. Talbot and L. Regnier, Eds.), vol. 62 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 19:1–19:17, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016.             
  BibTeX

  @inproceedings{PaScSe16,
       author = {Wied Pakusa and Svenja Schalth{\"o}fer and Erkal Selman},
       title = {{Definability of Cai-F\"urer-Immerman Problems in Choiceless Polynomial Time}},
       booktitle = {25th EACSL Annual Conference on Computer Science Logic (CSL 2016)},
       pages = {19:1--19:17},
       series = {Leibniz International Proceedings in Informatics (LIPIcs)},
       isbn = {978-3-95977-022-4},
       issn = {1868-8969},
       year = {2016},
       volume = {62},
       editor = {Jean-Marc Talbot and Laurent Regnier},
       publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
       address = {Dagstuhl, Germany},
       url = {http://logic.rwth-aachen.de/pub/schalthoefer/PaScSe16.pdf},
       urn = {urn:nbn:de:0030-drops-65595},
       doi = {http://dx.doi.org/10.4230/LIPIcs.CSL.2016.19},
       annote = {Keywords: finite model theory, descriptive complexity, logic for textsc{Ptime}, Choiceless Polynomial Time, Cai-F{\"u}rer-Immerman},
  }
  

2015

• F. Canavoi, E. Grädel, S. Lessenich, and W. Pakusa. Defining winning strategies in fixed-point logic. In Proceedings of 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2015.             
  BibTeX

  @inproceedings{CGLP15,
       author = {Felix Canavoi and Erich Gr{\"{a}}del and Simon Lessenich and Wied Pakusa},
       booktitle = {{Proceedings of 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)}},
       title = {{Defining winning strategies in fixed-point logic}},
       url = {http://www.logic.rwth-aachen.de/pub/graedel/CGLP15.pdf},
       year = {2015},
  }
  

• E. Grädel, Ł. Kaiser, W. Pakusa, and S. Schalthöfer. Characterising Choiceless Polynomial Time with First-Order Interpretations. In Proceedings of 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2015.             
  BibTeX

  @inproceedings{GKPS15,
       author = {Erich Gr{\"{a}}del and \L{}ukasz Kaiser and Wied Pakusa and Svenja Schalth{\"{o}}fer},
       booktitle = {{Proceedings of 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)}},
       title = {{Characterising Choiceless Polynomial Time with First-Order Interpretations}},
       url = {http://www.logic.rwth-aachen.de/pub/schalthoefer/GKPS15.pdf},
       year = {2015},
  }
  

• E. Grädel and W. Pakusa. Rank logic is dead, long live rank logic! CoRR (a conference version appeared in the proceedings of CSL'15), vol. abs/1503.05423, 2015.             
  BibTeX

  @article{GrPa15,
       author = {Erich Gr{\"{a}}del and Wied Pakusa},
       title = {Rank logic is dead, long live rank logic!},
       journal = {CoRR (a conference version appeared in the proceedings of CSL'15)},
       volume = {abs/1503.05423},
       year = {2015},
       url = {http://logic.rwth-aachen.de/pub/pakusa/GrPa15.pdf},
  }
  

2014

• F. Abu Zaid, E. Grädel, M. Grohe, and W. Pakusa. Choiceless Polynomial Time on structures with small Abelian colour classes. In Mathematical Foundations of Computer Science 2014, vol. 8634 of Lecture Notes in Computer Science, pp. 50-62. Springer, 2014.             
  BibTeX

  @incollection{AGGP14,
       author = {Faried {Abu Zaid} and Erich Gr{\"a}del and Martin Grohe and Wied Pakusa},
       title = {{Choiceless Polynomial Time on structures with small Abelian colour classes}},
       url = {http://logic.rwth-aachen.de/pub/pakusa/cptcan.pdf},
       year = {2014},
       booktitle = {Mathematical Foundations of Computer Science 2014},
       volume = {8634},
       series = {Lecture Notes in Computer Science},
       publisher = {Springer},
       pages = {50-62},
  }
  

2013

• F. Abu Zaid, E. Grädel, Ł. Kaiser, and W. Pakusa. Model-Theoretic Properties of omega-Automatic Structures. Theory of Computing Systems, Special Issue dedicated to STACS 2012, 2013.             
  BibTeX

  @article{AGKP12,
       author = {Faried {Abu Zaid} and Erich Gr{\"a}del and \L{}ukasz Kaiser and Wied Pakusa},
       title = {Model-Theoretic Properties of omega-Automatic Structures},
       journal = {Theory of Computing Systems, Special Issue dedicated to STACS 2012},
       url = {http://www.logic.rwth-aachen.de/pub/abuzaid/modelprop.pdf},
       note = {published online 17 October 2013},
       doi = {http://dx.doi.org/10.1007/s00224-013-9508-6},
       year = {2013},
  }
  

• A. Dawar, E. Grädel, B. Holm, E. Kopczynski, and W. Pakusa. Definability of linear equation systems over groups and rings. Logical Methods in Computer Science, Special Issue dedicated to CSL 2012, 2013.             
  BibTeX

  @article{DGHKP13,
       author = {Anuj Dawar and Erich Gr{\"a}del and Bjarki Holm and Eryk Kopczynski and Wied Pakusa},
       title = {{Definability of linear equation systems over groups and rings}},
       journal = {Logical Methods in Computer Science, Special Issue dedicated to CSL 2012},
       url = {http://www.lmcs-online.org/ojs/viewarticle.php?id=1325},
       year = {2013},
  }
  

2012

• A. Dawar, E. Grädel, B. Holm, E. Kopczynski, and W. Pakusa. Definability of linear equation systems over groups and rings. In Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (P. Cégielski and A. Durand, Eds.), vol. 16 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 213–227, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2012.                                 
  Abstract   BibTeX

  Motivated by the quest for a logic for PTIME and recent insights that the descriptive complexity of problems from linear algebra is a crucial aspect of this problem, we study the solvability of linear equation systems over finite groups and rings from the viewpoint of logical (inter-)definability. All problems that we consider are decidable in polynomial time, but not expressible in fixed-point logic with counting. They also provide natural candidates for a separation of polynomial time from rank logics, which extend fixed-point logics by operators for determining the rank of definable matrices and which are sufficient for solvability problems over fields. Based on the structure theory of finite rings, we establish logical reductions among various solvability problems. Our results indicate that all solvability problems for linear equation systems that separate fixed-point logic with counting from PTIME can be reduced to solvability over commutative rings. Further, we prove closure properties for classes of queries that reduce to solvability over rings. As an application, these closure properties provide normal forms for logics extended with solvability operators.

  @inproceedings{DGHKP12,
       author = {Anuj Dawar and Erich Gr{\"a}del and Bjarki Holm and Eryk Kopczynski and Wied Pakusa},
       title = {{Definability of linear equation systems over groups and rings}},
       booktitle = {Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL},
       pages = {213--227},
       series = {Leibniz International Proceedings in Informatics (LIPIcs)},
       isbn = {978-3-939897-42-2},
       issn = {1868-8969},
       year = {2012},
       volume = {16},
       editor = {Patrick C{\'e}gielski and Arnaud Durand},
       publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
       address = {Dagstuhl, Germany},
       url = {http://drops.dagstuhl.de/opus/volltexte/2012/3674},
       urn = {urn:nbn:de:0030-drops-36749},
       doi = {http://dx.doi.org/10.4230/LIPIcs.CSL.2012.213},
       annote = {Keywords: inite model theory, logics with algebraic operators},
  }
  

2010

• W. Pakusa. Finite Model Theory with Operators from Linear Algebra. Staatsexamensarbeit, RWTH-Aachen University, 2010.             
  BibTeX

  @misc{Pa10,
       author = {Wied {Pakusa}},
       howpublished = {Staatsexamensarbeit, RWTH-Aachen University},
       title = {{Finite Model Theory with Operators from Linear Algebra}},
       url = {http://logic.rwth-aachen.de/~pakusa/staatsarbeit.pdf},
       year = {2010},
  }