6 citations
Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.
- Centre National de la Recherche ScientifiqueFR9 papers
- Institut de Recherche en Informatique FondamentaleFR3 papers
- Université Paris CitéFR3 papers
- Université Paris-SaclayFR3 papers
- Aalborg UniversityDK2 papers
- Czech Academy of Sciences, Institute of SociologyCZ2 papers
- Herzliya Medical CenterIL2 papers
- Laboratoire Méthodes FormellesFR2 papers
- Masaryk UniversityCZ2 papers
- Paris-Est SupFR2 papers
- Radboud University NijmegenNL2 papers
- Sorbonne Paris CitéFR2 papers
12 papers · 1 filter
The Complexity of Defining and Separating Fixpoint Formulae in Modal Logic
Jean Christoph Jung, Jędrzej Kołodziejski
Modal separability for modal fixpoint formulae is the problem to decide for two given modal fixpoint formulae whether there is a modal formula that separates them, in th…
Prover-Adversary games for systems over (non-deterministic) branching programs
Anupam Das, Avgerinos Delkos
We introduce Pudlak-Buss style Prover-Adversary games to characterise proof systems reasoning over deterministic branching programs (BPs) and non-deterministic branching programs (…
Constraint satisfaction problems, compactness and non-measurable sets
Claude Tardif
A finite relational structure A is called compact if for any infinite relational structure B of the same type, the existence of a homomorphism from B to A is equivalent to the exis…
Computation by infinite descent made explicit
Sebastian Enqvist
We introduce a non-wellfounded proof system for intuitionistic logic extended with inductive and co-inductive definitions, based on a syntax in which fixpoint formulas are annotate…
Locality in Residuated-Lattice Structures
James Carr
Many-valued models generalise the structures from classical model theory by defining truth values for a model with an arbitrary algebra. Just as algebraic varieties provide semanti…
Simple Classes of Automatic Structures
Achim Blumensath
We study two subclasses of the class of automatic structures: automatic structures of polynomial growth and Presburger structures. We present algebraic characterisations of the gro…
Polynomial-Time Algorithms for Black-Box Distributive Expanded Groups
Mikhail Anokhin
Let be a finite set of finitary operation symbols. An -expanded group is a group (written additively and called the additive group of the -expanded group) with an -alg…
Going deep and going wide: Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth
Isolde Adler, Eva Fluck, Tim Seppelt +1
We study the expressive power of first-order logic with counting quantifiers, especially the -variable and quantifier-rank- fragment, using homomorphism indistinguishability.…
Hofmann-Streicher lifting of fibred categories
Andrew Slattery, Jonathan Sterling
In 1997, Hofmann and Streicher introduced an explicit construction to lift a Grothendieck universe from the category of sets into the category of set-valued presheaves on a small c…
On the consistency of stronger lower bounds for NEXP
Neil Thapen
It was recently shown by Atserias, Buss and Mueller that the standard complexity-theoretic conjecture NEXP not in P / poly is consistent with the relatively strong bounded arithmet…
Formal Analysis of the Contract Automata Runtime Environment with Uppaal: Modelling, Verification and Testing
Davide Basile
Recently, a distributed middleware application called contract automata runtime environment (CARE) has been introduced to realise service applications specified using a dialect of…
A Dichotomy Theorem for Ordinal Ranks in MSO
Damian Niwiński, Paweł Parys, Michał Skrzypczak
We focus on formulae of monadic second-order logic over the full binary tree, such that the witness is a well-founded set. The ordinal rank $\mathr…