47 citations · 115 across the 13 of their papers we have counts for
16 papers
Karp's NP-complete problems over first-order definable structures
Aidan Healy, Bartek Klin
We determine the decidability of Karp's NP-complete problems on structures which are first-order definable over the theory of equality, also known as orbit-finite sets with atoms o…
The Finite Length Property of the Rado Graph and Friends
Jingjie Yang, Mikołaj Bojańczyk, Bartek Klin
An infinite structure has the finite length property (over a given field) if, for each of its finite powers, chains of equivariant subspaces in the corresponding free vector space…
Polyregular functions on unordered trees of bounded height
Mikołaj Bojańczyk, Bartek Klin
We consider injective first-order interpretations that input and output trees of bounded height. The corresponding functions have polynomial output size, since a first-order interp…
Countdown -calculus
Jędrzej Kołodziejski, Bartek Klin
We introduce the countdown -calculus, an extension of the modal -calculus with ordinal approximations of fixpoint operators. In addition to properties definable in the classi…
Monadic Monadic Second Order Logic
Mikołaj Bojańczyk, Bartek Klin, Julian Salamanca
One of the main reasons for the correspondence of regular languages and monadic second-order logic is that the class of regular languages is closed under images of surjective lette…
Orbit-Finite-Dimensional Vector Spaces and Weighted Register Automata
Mikołaj Bojańczyk, Joanna Fijalkow, Bartek Klin +1
We develop a theory of vector spaces spanned by orbit-finite sets. Using this theory, we give a decision procedure for equivalence of weighted register automata, which are the comm…