International Professional University of Technology in Nagoya Repository
Not a member yet
15131 research outputs found
Sort by
Lipschitz continuity in the Hurst parameter of functionals of stochastic differential equations driven by a fractional Brownian motion
No full textInternational audienceSensitivity analysis w.r.t. the long-range/memory noise parameter for probability distributions of functionals of solutions to stochastic differential equations is an important stochastic modeling issue in many applications.In this paper we consider solutions to stochastic differential equations driven by frac{t}ional Brownian motions.We develop two innovative sensitivity analyseswhen the Hurst parameter~ of the noise tends to the critical Brownian parameter from above or from below. First, we examine expected smooth functions of at a fixed time horizon~. Second, we examine Laplace transforms of functionals which are irregular with regard to Malliavin calculus, namely, first passage times of at a given threshold.In both cases we exhibit the Lipschitz continuity w.r.t.~ around the value . Therefore, our results show that theMarkov Brownian model is a good proxy model as long as the Hurst parameter remains close to~
Enhancing rich content wikis with real-time collaboration
No full textInternational audienceWikis are one of the most important tools of Web 2.0 allowing users to easily edit shared data. However, wikis offer limited support for merging concurrent contributions on the same pages. Users have to manually merge concurrent changes and there is no support for an automatic merging. Real-time collaborative editing reduces the number of conflicts as the time frame for concurrent work is very short. In this paper we propose extending wiki systems with real-time collaboration. We propose an automatic merging solution adapted for rich content wikis. Our solution is integrated into a widely used wiki system
Data Modeling in the NoSQL World
No full textInternational audienceNoSQL systems have gained their popularity for many reasons, including the flexibility they provide in organizing data, as they relax the rigidity provided by the relational model and by the other structured models. This flexibility and the heterogeneity that has emerged in the area have led to a little use of traditional modeling techniques, as opposed to what has happened with databases for decades. In this paper, we argue how traditional notions related to data modeling can be useful in this context as well. Specifically, we propose NoAM (NoSQL Abstract Model), a novel abstract data model for NoSQL databases, which exploits the commonalities of various NoSQL systems. We also propose a database design methodology for NoSQL systems based on NoAM, with initial activities that are independent of the specific target system. NoAM is used to specify a system-independent representation of the application data and, then, this intermediate representation can be implemented in target NoSQL databases, taking into account their specific features. Overall, the methodology aims at supporting scalability, performance, and consistency, as needed by next-generation web applications
A resource-frugal probabilistic dictionary and applications in bioinformatics
No full textInternational audienceIndexing massive data sets is extremely expensive for large scale problems. In many fields, huge amounts of data are currently generated, however extracting meaningful information from voluminous data sets, such as computing similarity between elements, is far from being trivial. It remains nonetheless a fundamental need. This work proposes a probabilistic data structure based on a minimal perfect hash function for indexing large sets of keys. Our structure out-compete the hash table for construction, query times and for memory usage, in the case of the indexation of a static set. To illustrate the impact of algorithms performances, we provide two applications based on similarity computation between collections of sequences, and for which this calculation is an expensive but required operation. In particular, we show a practical case in which other bioinformatics tools fail to scale up the tested data set or provide lower recall quality results
Universal limits of substitution-closed permutation classes
No full text73 pages, 17 figuresInternational audienceWe consider uniform random permutations in proper substitution-closed classes and study their limiting behavior in the sense of permutons. The limit depends on the generating series of the simple permutations in the class. Under a mild sufficient condition, the limit is an elementary one-parameter deformation of the limit of uniform separable permutations, previously identified as the Brownian separable permuton. This limiting object is therefore in some sense universal. We identify two other regimes with different limiting objects. The first one is degenerate; the second one is nontrivial and related to stable trees. These results are obtained thanks to a characterization of the convergence of random permutons through the convergence of their expected pattern densities. The limit of expected pattern densities is then computed by using the substitution tree encoding of permutations and performing singularity analysis on the tree series
Towards a Minimal Stabilizer ZX-calculus
No full text13+15 pagesInternational audienceThe stabilizer ZX-calculus is a rigorous graphical language for reasoning about quantum mechanics. The language is sound and complete: one can transform a stabilizer ZX-diagram into another one using the graphical rewrite rules if and only if these two diagrams represent the same quantum evolution or quantum state. We previously showed that the stabilizer ZX-calculus can be simplified by reducing the number of rewrite rules, without losing the property of completeness [Backens, Perdrix & Wang, EPTCS 236:1--20, 2017]. Here, we show that most of the remaining rules of the language are indeed necessary. We do however leave as an open question the necessity of two rules. These include, surprisingly, the bialgebra rule, which is an axiomatisation of complementarity, the cornerstone of the ZX-calculus. Furthermore, we show that a weaker ambient category -- a braided autonomous category instead of the usual compact closed category -- is sufficient to recover the meta rule 'only connectivity matters', even without assuming any symmetries of the generators
Polychronous automata and their use for formal validation of AADL models
No full textInternational audienceThis paper investigates how state diagrams can be best represented in the polychronous model of computation (MoC) and proposes to use this model for code validation of behavior specifications in AADL. In this relational MoC, the basic objects are signals, which are related through dataflow equations. Signals are associated with logical clocks, which provide the capability to describe systems in which components obey to multiple clock rates. We propose a model of finite-state automata, called polychronous automata, which is based on clock relations. A specificity of this model is that an automaton is submitted to clock constraints. This allows one to specify a wide range of control-related configurations, either reactive, or restrictive with respect to their control environment. A semantic model is defined for these polychronous automata, that relies on a Boolean algebra of clocks. Based on a previously defined modeling of AADL software architectures using the polychronous MoC, this model of polychronous automata is used as a formal model for the AADL Behavior Annex. This is illustrated with a case study which specifies an adaptive cruise control system
A sub-Riemannian Santaló formula with applications to isoperimetric inequalities and first Dirichlet eigenvalue of hypoelliptic operators
No full textInternational audienceIn this paper we prove a sub-Riemannian version of the classical Santal\'o formula: a result in integral geometry that describes the intrinsic Liouville measure on the unit cotangent bundle in terms of the geodesic flow. Our construction works under quite general assumptions, satisfied by any sub-Riemannian structure associated with a Riemannian foliation with totally geodesic leaves (e.g.\ CR and QC manifolds with symmetries), any Carnot group, and some non-equiregular structures such as the Martinet one. A key ingredient is a ``reduction procedure'' that allows to consider only a simple subset of sub-Riemann\-ian geodesics.As an application, we derive isoperimetric-type and (-)Hardy-type inequalities for a compact domain with piecewise boundary, and a universal lower bound for the first Dirichlet eigenvalue of the sub-Laplacian,\begin{equation}\lambda_1(M) \geq \frac{k \pi^2}{L^2},\end{equation}in terms of the rank of the distribution and the length of the longest reduced sub-Riemannian geodesic contained in . All our results are sharp for the sub-Riemannian structures on the hemispheres of the complex and quaternionic Hopf fibrations:\begin{equation}\mathbb{S}^1\hookrightarrow \mathbb{S}^{2d+1} \xrightarrow{p} \mathbb{CP}^d, \qquad \mathbb{S}^3\hookrightarrow \mathbb{S}^{4d+3} \xrightarrow{p} \mathbb{HP}^d, \qquad d \geq 1,\end{equation}where the sub-Laplacian is the standard hypoelliptic operator of CR and QC geometries, and or , respectively
Mechanical Synthesis of Sorting Algorithms for Binary Trees by Logic and Combinatorial Techniques
No full textInternational audienceWe develop logic and combinatorial methods for automating the generation of sorting algorithms for binary trees, starting from input-output specifications and producing conditional rewrite rules. The main approach consists in proving (constructively) the existence of an appropriate output from every input. The proof may fail if some necessary sub–algorithms are lacking. Then, their specifications are suggested and their synthesis is performed by the same principles. Our main goal is to avoid the possibly prohibitive cost of pure resolution proofs by using a natural–style proving in which domain-specific strategies and inference steps lead to a significant increase of efficiency. In addition to classical techniques for natural–style proving, we introduce novel ones (priority of certain types of assumptions, transformation of elementary goals into conditions, special criteria for decomposition of the goal and of the assumptions), as well as methods based on the properties of domain-specific relations and functions. In particular, we use combinatorial techniques in order to generate possible witnesses, which in certain cases lead to the discovery of new induction principles. From the proof, the algorithm is extracted by transforming inductive proof steps into recursions, and case-based proof steps into conditionals. The approach is demonstrated in parallel using the Theorema system, by developing the theory , implementing the prover, and performing the proofs of the necessary properties and synthesis conjectures. It is also validated in the Coq system, which allows to compare the facilities of the two systems from the point of view of our application
Modeling Variability in the Video Domain: Language and Experience Report
No full textInternational audience[Context] In an industrial project, we addressed the challenge of developing a software-based video generator such that consumers and providers of video processing algorithms can benchmark them on a wide range of video variants. [Objective] This article aims to report on our positive experience in modeling, controlling, and implementing software variability in the video domain. [Method] We describe how we have designed and developed a variability modeling language, called VM, resulting from the close collaboration with industrial partners during two years. We expose the specific requirements and advanced variability constructs we developed and used to characterize and derive variations of video sequences. [Results] The results of our experiments and industrial experience show that our solution is effective to model complex variability information and supports the synthesis of hundreds of realistic video variants. [Conclusions] From the software language perspective, we learned that basic variability mechanisms are useful but not enough; attributes and multi-features are of prior importance; meta-information and specific constructs are relevant for scalable and purposeful reasoning over variability models. From the video domain and software perspective, we report on the practical benefits of a variability approach. With more automation and control, practitioners can now envision benchmarking video algorithms over large, diverse, controlled, yet realistic datasets (videos that mimic real recorded videos) – something impossible at the beginning of the project