1.1k citations
- École PolytechniqueFR461 papers
- Centre National de la Recherche ScientifiqueFR295 papers
- Institut national de recherche en sciences et technologies du numériqueFR118 papers
- Centre Inria de SaclayFR62 papers
- Institut Polytechnique de ParisFR60 papers
- CRANFR28 papers
- Université Paris CitéFR28 papers
- Université Paris-SaclayFR26 papers
- Sorbonne UniversitéFR25 papers
- Université de LorraineFR18 papers
- Université Paris-SudFR17 papers
- École Normale Supérieure de LyonFR14 papers
28 papers · 1 filter
Non-redundant random generation from weighted context-free languages
Yann Ponty
We address the non-redundant random generation of k words of length n from a context-free language. Additionally, we want to avoid a predefined set of words. We study the limits of…
Decidability of definability
Manuel Bodirsky, Michael Pinsker, Todor Tsankov
For a fixed countably infinite structure Γ with finite relational signature τ, we study the following computational problem: input are quantifier-free τ-formulas ϕ_0,ϕ_1,...,ϕ_n th…
Proceedings 17th International Workshop on Expressiveness in Concurrency
Sibylle Fröschle, Frank D. Valencia
This volume contains the proceedings of the 17th International Workshop on Expressiveness in Concurrency (EXPRESS'10), which took place on 30th August 2010 in Paris, co-located wit…
New Set of Codes for the Maximum-Likelihood Decoding Problem
Morgan Barbier
The maximum-likelihood decoding problem is known to be NP-hard for general linear and Reed-Solomon codes. In this paper, we introduce the notion of A-covered codes, that is, codes…
Medians and means in Finsler geometry
Marc Arnaudon, Frank Nielsen
We investigate existence and uniqueness of p-means and the median of a probability measure on a Finsler manifold, in relation with the convexity of the support of the measure. We p…
Complexity of Existential Positive First-Order Logic
Manuel Bodirsky, Miki Hermann, Florian Richoux
Let gamma be a (not necessarily finite) structure with a finite relational signature. We prove that deciding whether a given existential positive sentence holds in gamma is in Logs…