Search

Your search keyword '"Exponential complexity"' showing total 7 results
Start Over Descriptor "Exponential complexity" Publisher hal ccsd
7 results on '"Exponential complexity"'

1. Canonical Decomposition of Basic Belief Assignment for Decision-Making Support

Author

Florentin Smarandache, Jean Dezert, DTIS, ONERA, Université Paris Saclay [Palaiseau], ONERA-Université Paris-Saclay, UNIVERSITY OF NEW MEXICO GALLUP USA, Partenaires IRSTEA, and Institut national de recherche en sciences et technologies pour l'environnement et l'agriculture (IRSTEA)-Institut national de recherche en sciences et technologies pour l'environnement et l'agriculture (IRSTEA)

Subjects
Exponential complexity, [PHYS]Physics [physics], Canonical decomposition, Theoretical computer science, Computer science, Basic belief, media_common.quotation_subject, PCR5, 020206 networking & telecommunications, 02 engineering and technology, 16. Peace & justice, [SPI]Engineering Sciences [physics], Belief functions, 0202 electrical engineering, electronic engineering, information engineering, Fuse (electrical), Decomposition (computer science), Decomposition method (queueing theory), 020201 artificial intelligence & image processing, Quality (business), Support system, [INFO]Computer Science [cs], [MATH]Mathematics [math], media_common, Decision-making
Abstract

International audience; We present a new methodology for decision-making support based on belief functions thanks to a new theoretical canonical decomposition of dichotomous basic belief assignments (BBAs) that has been developed recently. This decomposition based on proportional conflict redistribution rule no 5 (PCR5) always exists and is unique. This new PCR5-based decomposition method circumvents the exponential complexity of the direct fusion of BBAs with PCR5 rule and it allows to fuse quickly many sources of evidences. The method we propose in this paper provides both a decision and an estimation of the quality of the decision made, which is appealing for decision-making support systems.

Published
2020

2. Characterizing polynomial and exponential complexity classes in elementary lambda-calculus

Author

Patrick Baillot, Simona Ronchi Della Rocca, Erika De Benedetti, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Preuves et Langages (PLUME), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Dipartimento di Informatica [Torino], Università degli studi di Torino = University of Turin (UNITO), ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), ANR-14-CE25-0005,ELICA,Élargir les idées logiques pour l'analyse de complexité(2014), Baillot, Patrick, Community of mathematics and fundamental computer science in Lyon - - MILYON2010 - ANR-10-LABX-0070 - LABX - VALID, Appel à projets générique - Élargir les idées logiques pour l'analyse de complexité - - ELICA2014 - ANR-14-CE25-0005 - Appel à projets générique - VALID, École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Università degli studi di Torino (UNITO), Josep Diaz, Ivan Lanese, Davide Sangiorgi, TC 1, TC 2, WG 2.2, Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)

Subjects
Average-case complexity, Exponential complexity, Polynomial, [INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO], Linear logic, 0102 computer and information sciences, Descriptive complexity theory, [INFO] Computer Science [cs], Characterization (mathematics), 01 natural sciences, Theoretical Computer Science, Structural complexity theory, Computer Science::Logic in Computer Science, Complexity class, Lambda-calculus, [INFO]Computer Science [cs], 0101 mathematics, computer.programming_language, Mathematics, Discrete mathematics, Implicit computational complexity, Hierarchy (mathematics), 010102 general mathematics, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Computer Science Applications, Algebra, PH, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, Computational Theory and Mathematics, 010201 computation theory & mathematics, Lambda calculus, computer, Quantum complexity theory, Information Systems
Abstract

Part 2: Track B: Logic, Semantics, Specification and Verification; International audience; In this paper an implicit characterization of the complexity classes k-EXP and k-FEXP, for k ≥ 0, is given, by a type assignment system for a stratified λ-calculus, where types for programs are witnesses of the corresponding complexity class. Types are formulae of Elementary Linear Logic (ELL), and the hierarchy of complexity classes k-EXP is characterized by a hierarchy of types.

Published
2018

3. Set Adaptive Observers for Linear Parameter-Varying Systems: Application to Fault Detection

Author

Denis Efimov, Tarek Raïssi, Ali Zolghadri, Non-Asymptotic estimation for online systems (NON-A), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Systèmes Non Linéaires et à Retards (SyNeR), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM), Laboratoire de l'intégration, du matériau au système (IMS), Université Sciences et Technologies - Bordeaux 1 (UB)-Institut Polytechnique de Bordeaux-Centre National de la Recherche Scientifique (CNRS), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Université Sciences et Technologies - Bordeaux 1-Institut Polytechnique de Bordeaux-Centre National de la Recherche Scientifique (CNRS)

Subjects
Exponential complexity, 0209 industrial biotechnology, Estimation theory, Mechanical Engineering, 020208 electrical & electronic engineering, 02 engineering and technology, State (functional analysis), Resolution (logic), Fault detection and isolation, LPV systems, fault detection, Computer Science Applications, Adaptive observer, Set (abstract data type), 020901 industrial engineering & automation, Adaptive observers, Control and Systems Engineering, Control theory, [INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering, 0202 electrical engineering, electronic engineering, information engineering, Instrumentation, Information Systems, Mathematics
Abstract

International audience; This paper deals with the problem of joint state and parameter estimation based on a set adaptive observer design. The problem is formulated and solved for an LPV (Linear Parameter-Varying) system. The resolution methodology avoids the exponential complexity obstruction usually encountered in the set-membership parameter estimation. A simulation example is presented to illustrate the efficiency of the proposed approach.

Published
2014

4. Partial enumeration of solutions traces for the problem of sorting by signed reversals

Author

Christian Baudet, Zanoni Dias, An algorithmic view on genomes, cells, and environments (BAMBOO), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Institute of Computing [Campinas] (UNICAMP), Universidade Estadual de Campinas (UNICAMP), Institute of Computing [Campinas] (IC), and Universidade Estadual de Campinas = University of Campinas (UNICAMP)

Subjects
Exponential complexity, 0206 medical engineering, Sorting, 0102 computer and information sciences, 02 engineering and technology, Space (commercial competition), 01 natural sciences, [SDV.BIBS]Life Sciences [q-bio]/Quantitative Methods [q-bio.QM], Set (abstract data type), Permutation, 010201 computation theory & mathematics, Enumeration, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Algorithm, 020602 bioinformatics, Mathematics
Abstract

International audience; Traditional algorithms to solve the problem of sorting by signed reversals output just one optional solution while the space of optimal solutions can be huge. Algorithms for enumerating the complete set of solutions traces were developed aiming to support biologists studies of alternative evolutionary scenarios. Due to the exponential complexity of the algorithms, their practical use is limited to small permutations. In this work, we propose and evaluate three di erent approaches to producing a partial enumeration of the complete set of traces to transform a given permutation to another one.

Published
2011

5. MONOTONE ADAPTIVE SET OBSERVERS FOR NONLINEAR CONTINUOUS-TIME SYSTEMS

Author

Denis Efimov, Tarek Raïssi, Ali Zolghadri, and Raïssi, Tarek

Subjects
Set (abstract data type), Exponential complexity, Nonlinear system, Mathematical optimization, Monotone polygon, Control theory, Estimation theory, General Medicine, State (functional analysis), IFAC, [INFO.INFO-AU] Computer Science [cs]/Automatic Control Engineering, Mathematics, Adaptive observer
Abstract

The paper deals with joint state and parameter estimation for nonlinear continuous-time systems. Based on a guaranteed LPV approximation, the problem of set observers design is recasted into more general adaptive observers design problem in order to avoid the exponential complexity obstruction usually met in the set-membership nonlinear estimation. The efficacy of the proposed set adaptive observer is demonstrated on a bioreactor example.

Published
2010

6. A Smell of Orchids

Author

Jean Goubault-Larrecq, Julien Olivain, Laboratoire Spécification et Vérification (LSV), Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Ecole Normale Supérieure Paris-Saclay (ENS Paris Saclay), and Above Security

Subjects
Exponential complexity, Low overhead, Computer science, business.industry, Real-time computing, 020207 software engineering, 02 engineering and technology, Intrusion detection system, Machine learning, computer.software_genre, Abstract interpretation, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Salient, 0202 electrical engineering, electronic engineering, information engineering, Overhead (computing), 020201 artificial intelligence & image processing, Artificial intelligence, business, computer, ComputingMilieux_MISCELLANEOUS
Abstract

Orchids is an intrusion detection tool based on techniques for fast, on-line model-checking. Orchids detects complex, correlated strands of events with very low overhead in practice, although its detection algorithm has worst-case exponential time complexity. The purpose of this paper is twofold. First, we explain the salient features of the basic model-checking algorithm in an intuitive way, as a form of dynamically-spawned monitors. One distinctive feature of the Orchids algorithm is that fresh monitors need to be spawned at a possibly alarming rate. The second goal of this paper is therefore to explain how we tame the complexity of the procedure, using abstract interpretation techniques to safely kill useless monitors. This includes monitors which will provably detect nothing, but also monitors that are subsumed by others, in the sense that they will definitely fail the so-called shortest run criterion. We take the opportunity to show how the Orchids algorithm maintains its monitors sorted in such a way that the subsumption operation is effected with no overhead, and we correct a small, but definitely annoying bug in its core algorithm, as it was published in 2001.

Published
2008

7. Set function over finite sets: transformations and integrals

Author

Michel Grabisch, Systèmes d'aide à la décision et à la formation (SYSDEF), Laboratoire d'Informatique de Paris 6 (LIP6), and Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Exponential complexity, 010102 general mathematics, Inverse, 02 engineering and technology, 16. Peace & justice, 01 natural sciences, Fuzzy logic, Algebra, Formalism (philosophy of mathematics), Set function, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, [INFO]Computer Science [cs], 0101 mathematics, Finite set, Game theory, ComputingMilieux_MISCELLANEOUS, Mathematics
Abstract

This chapter elaborates various transformations of the set functions. Measures in a finite setting are positive-valued set functions with some characteristic properties. It is found that although the finiteness of the universe considerably restricts the interest of the measure concept, it also allows other viewpoints coming from various fields of mathematics—suchas combinatorics, game theory, and complexity—when viewing measures as particular set functions or pseudo-Boolean functions. There is a general formula for the inverse of cardinality operators. The formalism permits to compute easily, simply by combining and inversing operators, all formulas between the different representations of set functions. It is found that any set function can be decomposed on the set of unanimity games or their conjugate. The k-order additive measures or k-additive measures decrease the exponential complexity of fuzzy measures in practical applications. The ordinal interaction transform of a fuzzy measure is also elaborated in the chapter.

Published
2002

Catalog

Books, media, physical & digital resources
See catalog results