Bodini O.,LIP6 |
Bodini O.,University Paris Diderot |
Gardy D.,University of Versailles |
Gittenberger B.,Institute of Discrete Mathematics and Geometry
8th Workshop on Analytic Algorithmics and Combinatorics 2011, ANALCO 2011 | Year: 2011
We aim at the asymptotic enumeration of lambda-terms of a given size where the order of nesting of abstractions is bounded whereas the size is tending to infinity. This is done by means of a generating function approach and singularity analysis. The generating functions appear to be composed of nested square roots which exhibit unexpected phenomena. We derive the asymptotic number of such lambda-terms and it turns out that the order depends on the bound of the height. Furthermore, we present some observations when generating such lambda randomly and explain why powerful tools for random generation, such as Boltzmann samplers, face serious difficulties in generating lambda-terms. © Copyright (2011) by SIAM: Society for Industrial and Applied Mathematics. All rights reserved.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2013
The aim of this paper is to provide a unifying axiomatic justification for a class of qualitative decision models comprising among others optimistic/pessimistic qualitative utilities, binary possibilistic utility, likelihood-based utility, Spohn's disbelief function-based utility. All those criteria that are instances of Algebraic Expected Utility have been shown to be counterparts of Expected Utility thanks to a unifying axiomatization in a von Neumann-Morgenstern setting when non probabilistic decomposable uncertainty measures are used. Those criteria are based on (⊕,⊗) operators, counterpart of (+, ×) used by Expected Utility, where ⊕ is an idempotent operator and ⊗ is a triangular norm. The axiomatization is lead in the Savage setting which is a more general setting than that of von Neumann-Morgenstern as here we do not assume that the uncertainty representation of the decision-maker is known. © 2013 Springer-Verlag.
Crespelle C.,LIP6 |
Todinca I.,University of Orleans
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2010
The minimal interval completion problem consists in adding edges to an arbitrary graph so that the resulting graph is an interval graph; the objective is to add an inclusion minimal set of edges, which means that no proper subset of the added edges can result in an interval graph when added to the original graph. We give an O(n2)-time algorithm to obtain a minimal interval completion of an arbitrary graph. This improves the previous O(nm) time bound for the problem and lower this bound for the first time below the best known bound for minimal chordal completion. © 2010 Springer-Verlag.
Carpentier G.,IRCAM |
Assayag G.,IRCAM |
Journal of Heuristics | Year: 2010
In this paper a computational approach of musical orchestration is presented. We consider orchestration as the search of relevant sound combinations within large instruments sample databases and propose two cooperating metaheuristics to solve this problem. Orchestration is seen here as a particular case of finding optimal constrained multisets on a large ensemble with respect to several objectives. We suggest a generic and easily extendible formalization of orchestration as a constrained multiobjective search towards a target timbre, in which several perceptual dimensions are jointly optimized. We introduce Orchidée, a time-efficient evolutionary orchestration algorithm that allows the discovery of optimal solutions and favors the exploration of non-intuitive sound mixtures. We also define a formal framework for global constraints specification and introduce the innovative CDCSolver repair metaheuristic, thanks to which the search is led towards regions fulfilling a set of musical-related requirements. Evaluation of our approach on a wide set of real orchestration problems is also provided. © Springer Science+Business Media, LLC 2009.
Frontiers in Artificial Intelligence and Applications | Year: 2012
Setting the values of rewards in Markov decision processes (MDP) may be a difficult task. In this paper, we consider two ordinal decision models for MDPs where only an order is known over rewards. The first one, which has been proposed recently in MDPs , defines preferences with respect to a reference point. The second model, which can been viewed as the dual approach of the first one, is based on quantiles. Based on the first decision model, we give a new interpretation of rewards in standard MDPs, which sheds some interesting light on the preference system used in standard MDPs. The second model based on quantile optimization is a new approach in MDPs with ordinal rewards. Although quantile-based optimality is state-dependent, we prove that an optimal stationary deterministic policy exists for a given initial state. Finally, we propose solution methods based on linear programming for optimizing quantiles. © 2012 The Author(s).