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
64 papers
Quadratic Equations in Graph Products of Groups and the Exponent of Periodicity
Volker Diekert, Silas Natterer, Alexander Thumm
In 1977, Makanin established the decidability of equations in free monoids. A key ingredient in his proof is the exponent of periodicity: for a word , it is the largest exponent…
The group identification problem for -groups of small order
Bettina Eick, Henrik Schanze
We investigate which group-theoretic invariants are powerful in distinguishing among non-isomorphic p-groups. Based on this, we devise an effective algorithm to solve the group ide…
On the Diophantine problem related to power circuits
Alexander Rybalov
Myasnikov, Ushakov, and Won introduced power circuits in 2012 to construct a polynomial-time algorithm for the word problem in the Baumslag group, which has a non-elementary Dehn f…
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…
Algorithms for Markov Binomial Chains
Alejandro Alarcón Gonzalez, Niel Hens, Tim Leys +1
We study algorithms to analyze a particular class of Markov population processes that is often used in epidemiology. More specifically, Markov binomial chains are the model that ar…
On Polynomial-Time Decidability of k-Negations Fragments of First-Order Theories
Christoph Haase, Alessio Mansutti, Amaury Pouly
This paper introduces a generic framework that provides sufficient conditions for guaranteeing polynomial-time decidability of fixed-negation fragments of first-order theories that…
The Size-Change Principle for Mixed Inductive and Coinductive types
Pierre Hyvernat
This paper shows how to use Lee, Jones and Ben Amram's size-change principle to check correctness of arbitrary recursive definitions in an ML / Haskell like programming language wi…
The categorical contours of the Chomsky-Schützenberger representation theorem
Paul-André Melliès, Noam Zeilberger
We develop fibrational perspectives on context-free grammars and on nondeterministic finite-state automata over categories and operads. A generalized CFG is a functor from a free c…
Using weakest application conditions to rank graph transformations for graph repair
Lars Fritsche, Alexander Lauer, Maximilian Kratz +2
When using graphs and graph transformations to model systems, consistency is an important concern. While consistency has primarily been viewed as a binary property, i.e., a graph i…
Computing the unit group of a commutative finite -algebra
Martin Kreuzer, Florian Walsh
For a commutative finite -algebra, i.e., for a commutative ring whose additive group is finitely generated, it is known that the group of units of is finitely g…
A categorical account of composition methods in logic (extended version)
Tomáš Jakl, Dan Marsden, Nihil Shah
We present a categorical theory of the composition methods in finite model theory -- a key technique enabling modular reasoning about complex structures by building them out of sim…
Constrained inhomogeneous spherical equations: average-case hardness
Alexander Ushakov
In this paper we analyze computational properties of the Diophantine problem (and its search variant) for spherical equations (and its variants…
On the Unprovability of Circuit Size Bounds in Intuitionistic
Lijie Chen, Jiatu Li, Igor C. Oliveira
We show that there is a constant such that Buss's intuitionistic theory does not prove that SAT requires co-nondeterministic circuits of size at least .…