8 citations · 14 across the 4 of their papers we have counts for
5 papers
Computational Complexity of Alignments
Christopher T. Schwanen, Wied Pakusa, Wil M. P. van der Aalst
In process mining, alignments quantify the degree of deviation between an observed event trace and a business process model and constitute one of the most important conformance che…
Approximations of Isomorphism and Logics with Linear-Algebraic Operators
Anuj Dawar, Erich Grädel, Wied Pakusa
Invertible map equivalences are approximations of graph isomorphism that refine the well-known Weisfeiler-Leman method. They are parametrised by a number k and a set Q of primes. T…
A Finite-Model-Theoretic View on Propositional Proof Complexity
Erich Grädel, Martin Grohe, Benedikt Pago +1
We establish new, and surprisingly tight, connections between propositional proof complexity and finite model theory. Specifically, we show that the power of several propositional…
Rank logic is dead, long live rank logic!
Erich Grädel, Wied Pakusa
Motivated by the search for a logic for polynomial time, we study rank logic (FPR) which extends fixed-point logic with counting (FPC) by operators that determine the rank of matri…
Definability of linear equation systems over groups and rings
Anuj Dawar, Eryk Kopczynski, Bjarki Holm +2
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 s…