OpenRaiser/Intern-Atlas huggingface dataset:
Moderate Growth Time Series for Dynamic Combinatorics Modelisation
Venue: arXiv cs.SC 2007
Year: 2007

Here, we present a family of time series with a simple growth constraint. This family can be the basis of a model to apply to emerging computation in business and micro-economy where global functions can be expressed from local rules. We explicit a double statistics on these series which allows to establish a one-to-one correspondence between three other ballot-like strunctures.
Collection analysis for Horn clause programs
Venue: arXiv cs.LO 2007
Year: 2007

We consider approximating data structures with collections of the items that they contain. For examples, lists, binary trees, tuples, etc, can be approximated by sets or multisets of the items within them. Such approximations can be used to provide partial correctness properties of logic programs. For example, one might wish to specify than whenever the atom $sort(t,s)$ is proved then the two lists $t$ and $s$ contain the same multiset of items (that is, $s$ is a permutation of $t$). If sorting removes duplicates, then one would like to infer that the sets of items underlying $t$ and $s$ are the same. Such results could be useful to have if they can be determined statically and automatically. We present a scheme by which such collection analysis can be structured and automated. Central to this scheme is the use of linear logic as a omputational logic underlying the logic of Horn clauses.
Focusing and Polarization in Intuitionistic Logic
Venue: arXiv cs.LO 2007
Year: 2007

A focused proof system provides a normal form to cut-free proofs that structures the application of invertible and non-invertible inference rules. The focused proof system of Andreoli for linear logic has been applied to both the proof search and the proof normalization approaches to computation. Various proof systems in literature exhibit characteristics of focusing to one degree or another. We present a new, focused proof system for intuitionistic logic, called LJF, and show how other proof systems can be mapped into the new system by inserting logical connectives that prematurely stop focusing. We also use LJF to design a focused proof system for classical logic. Our approach to the design and analysis of these systems is based on the completeness of focusing in linear logic and on the notion of polarity that appears in Girard's LC and LU proof systems.
Compositional Semantics Grounded in Commonsense Metaphysics
Venue: arXiv cs.AI 2007
Year: 2007

We argue for a compositional semantics grounded in a strongly typed ontology that reflects our commonsense view of the world and the way we talk about it in ordinary language. Assuming the existence of such a structure, we show that the semantics of various natural language phenomena may become nearly trivial.
Benefiting from Disorder: Source Coding for Unordered Data
Venue: arXiv cs.IT 2007
Year: 2007

The order of letters is not always relevant in a communication task. This paper discusses the implications of order irrelevance on source coding, presenting results in several major branches of source coding theory: lossless coding, universal lossless coding, rate-distortion, high-rate quantization, and universal lossy coding. The main conclusions demonstrate that there is a significant rate savings when order is irrelevant. In particular, lossless coding of n letters from a finite alphabet requires Theta(log n) bits and universal lossless coding requires n + o(n) bits for many countable alphabet sources. However, there are no universal schemes that can drive a strong redundancy measure to zero. Results for lossy coding include distribution-free expressions for the rate savings from order irrelevance in various high-rate quantization schemes. Rate-distortion bounds are given, and it is shown that the analogue of the Shannon lower bound is loose at all finite rates.
Continuous and randomized defensive forecasting: unified view
Venue: arXiv cs.LG 2007
Year: 2007

Defensive forecasting is a method of transforming laws of probability (stated in game-theoretic terms as strategies for Sceptic) into forecasting algorithms. There are two known varieties of defensive forecasting: "continuous", in which Sceptic's moves are assumed to depend on the forecasts in a (semi)continuous manner and which produces deterministic forecasts, and "randomized", in which the dependence of Sceptic's moves on the forecasts is arbitrary and Forecaster's moves are allowed to be randomized. This note shows that the randomized variety can be obtained from the continuous variety by smearing Sceptic's moves to make them continuous.
Key Agreement and Authentication Schemes Using Non-Commutative Semigroups
Venue: arXiv cs.CR 2007
Year: 2007

We give a new two-pass authentication scheme, whichis a generalisation of an authentication scheme of Sibert-Dehornoy-Girault based on the Diffie-Hellman conjugacy problem. Compared to the above scheme, for some parameters it is more efficient with respect to multiplications. We sketch a proof that our authentication scheme is secure. We give a new key agreement protocols.
Discrete Denoising with Shifts
Venue: arXiv cs.IT 2007
Year: 2007

We introduce S-DUDE, a new algorithm for denoising DMC-corrupted data. The algorithm, which generalizes the recently introduced DUDE (Discrete Universal DEnoiser) of Weissman et al., aims to compete with a genie that has access, in addition to the noisy data, also to the underlying clean data, and can choose to switch, up to $m$ times, between sliding window denoisers in a way that minimizes the overall loss. When the underlying data form an individual sequence, we show that the S-DUDE performs essentially as well as this genie, provided that $m$ is sub-linear in the size of the data. When the clean data is emitted by a piecewise stationary process, we show that the S-DUDE achieves the optimum distribution-dependent performance, provided that the same sub-linearity condition is imposed on the number of switches. To further substantiate the universal optimality of the S-DUDE, we show that when the number of switches is allowed to grow linearly with the size of the data, \emph{any} (sequence of) scheme(s) fails to compete in the above senses. Using dynamic programming, we derive an efficient implementation of the S-DUDE, which has complexity (time and memory) growing only linearly with the data size and the number of switches $m$. Preliminary experimental results are presented, suggesting that S-DUDE has the capacity to significantly improve on the performance attained by the original DUDE in applications where the nature of the data abruptly changes in time (or space), as is often the case in practice.
An Experimental Investigation of Secure Communication With Chaos Masking
Venue: arXiv cs.CR 2007
Year: 2007

The most exciting recent development in nonlinear dynamics is realization that chaos can be useful. One application involves "Secure Communication". Two piecewise linear systems with switching nonlinearities have been taken as chaos generators. In the present work the phenomenon of secure communication with chaos masking has been investigated experimentally. In this investigation chaos which is generated from two chaos generators is masked with the massage signal to be transmitted, thus makes communication is more secure.
Aggregation Languages for Moving Object and Places of Interest Data
Venue: arXiv cs.DB 2007
Year: 2007

We address aggregate queries over GIS data and moving object data, where non-spatial data are stored in a data warehouse. We propose a formal data model and query language to express complex aggregate queries. Next, we study the compression of trajectory data, produced by moving objects, using the notions of stops and moves. We show that stops and moves are expressible in our query language and we consider a fragment of this language, consisting of regular expressions to talk about temporally ordered sequences of stops and moves. This fragment can be used to efficiently express data mining and pattern matching tasks over trajectory data.
Fast evaluation of union-intersection expressions
Venue: arXiv cs.DS 2007
Year: 2007

We show how to represent sets in a linear space data structure such that expressions involving unions and intersections of sets can be computed in a worst-case efficient way. This problem has applications in e.g. information retrieval and database systems. We mainly consider the RAM model of computation, and sets of machine words, but also state our results in the I/O model. On a RAM with word size $w$, a special case of our result is that the intersection of $m$ (preprocessed) sets, containing $n$ elements in total, can be computed in expected time $O(n (\log w)^2 / w + km)$, where $k$ is the number of elements in the intersection. If the first of the two terms dominates, this is a factor $w^{1-o(1)}$ faster than the standard solution of merging sorted lists. We show a cell probe lower bound of time $Ω(n/(w m \log m)+ (1-\tfrac{\log k}{w}) k)$, meaning that our upper bound is nearly optimal for small $m$. Our algorithm uses a novel combination of approximate set representations and word-level parallelism.
Architecture Optimization of a 3-DOF Translational Parallel Mechanism for Machining Applications, the Orthoglide
Venue: arXiv cs.RO 2007
Year: 2007

This paper addresses the architecture optimization of a 3-DOF translational parallel mechanism designed for machining applications. The design optimization is conducted on the basis of a prescribed Cartesian workspace with prescribed kinetostatic performances. The resulting machine, the Orthoglide, features three fixed parallel linear joints which are mounted orthogonally and a mobile platform which moves in the Cartesian x-y-z space with fixed orientation. The interesting features of the Orthoglide are a regular Cartesian workspace shape, uniform performances in all directions and good compactness. A small-scale prototype of the Orthoglide under development is presented at the end of this paper.
Gaze as a Supplementary Modality for Interacting with Ambient Intelligence Environments
Venue: arXiv cs.HC 2007
Year: 2007

We present our current research on the implementation of gaze as an efficient and usable pointing modality supplementary to speech, for interacting with augmented objects in our daily environment or large displays, especially immersive virtual reality environments, such as reality centres and caves. We are also addressing issues relating to the use of gaze as the main interaction input modality. We have designed and developed two operational user interfaces: one for providing motor-disabled users with easy gaze-based access to map applications and graphical software; the other for iteratively testing and improving the usability of gaze-contingent displays.
Formally Verified Argument Reduction with a Fused-Multiply-Add
Venue: arXiv cs.MS 2007
Year: 2007

Cody & Waite argument reduction technique works perfectly for reasonably large arguments but as the input grows there are no bit left to approximate the constant with enough accuracy. Under mild assumptions, we show that the result computed with a fused-multiply-add provides a fully accurate result for many possible values of the input with a constant almost accurate to the full working precision. We also present an algorithm for a fully accurate second reduction step to reach double full accuracy (all the significand bits of two numbers are significant) even in the worst cases of argument reduction. Our work recalls the common algorithms and presents proofs of correctness. All the proofs are formally verified using the Coq automatic proof checker.
Design Strategies for the Geometric Synthesis of Orthoglide-type Mechanisms
Venue: arXiv cs.RO 2007
Year: 2007

The paper addresses the geometric synthesis of Orthoglide-type mechanism, a family of 3-DOF parallel manipulators for rapid machining applications, which combine advantages of both serial mechanisms and parallel kinematic architectures. These manipulators possess quasi-isotropic kinematic performances and are made up of three actuated fixed prismatic joints, which are mutually orthogonal and connected to a mobile platform via three parallelogram chains. The platform moves in the Cartesian space with fixed orientation, similar to conventional XYZ-machine. Three strategies have been proposed to define the Orthoglide geometric parameters (manipulator link lengths and actuated joint limits) as functions of a cubic workspace size and dextrous properties expressed by bounds on the velocity transmission factors, manipulability or the Jacobian condition number. Low inertia and intrinsic stiffness have been set as additional design goals expressed by the minimal link length requirement. For each design strategy, analytical expressions for computing the Orthoglide parameters are proposed. It is showed that the proposed strategies yield Pareto-optimal solutions, which differ by the kinematic performances outside the prescribed Cartesian cube (but within the workspace bounded by the actuated joint limits). The proposed technique is illustrated with numerical examples for the Orthoglide prototype design.
An Exhaustive Study of the Workspaces Tolopogies of all 3R Orthogonal Manipulators with Geometric Simplifications
Venue: arXiv cs.RO 2007
Year: 2007

This paper proposes a classification of three-revolute orthogonal manipulators that have at least one of their DH parameters equal to zero. This classification is based on the topology of their workspace. The workspace is characterized in a half-cross section by the singular curves. The workspace topology is defined by the number of cusps and nodes that appear on these singular curves. The manipulators are classified into different types with similar kinematic properties. Each type is evaluated according to interesting kinematic properties such as, whether the workspace is fully reachable with four inverse kinematic solutions or not, the existence of voids, and the feasibility of continuous trajectories in the workspace. It is found that several orthogonal manipulators have a "well-connected" workspace, that is, their workspace is fully accessible with four inverse kinematic solutions and any continuous trajectory is feasible. This result is of interest for the design of alternative manipulator geometries.
Secure Transmission with Multiple Antennas: The MISOME Wiretap Channel
Venue: arXiv cs.IT 2007
Year: 2007

The role of multiple antennas for secure communication is investigated within the framework of Wyner's wiretap channel. We characterize the secrecy capacity in terms of generalized eigenvalues when the sender and eavesdropper have multiple antennas, the intended receiver has a single antenna, and the channel matrices are fixed and known to all the terminals, and show that a beamforming strategy is capacity-achieving. In addition, we show that in the high signal-to-noise (SNR) ratio regime the penalty for not knowing eavesdropper's channel is small--a simple ``secure space-time code'' that can be thought of as masked beamforming and radiates power isotropically attains near-optimal performance. In the limit of large number of antennas, we obtain a realization-independent characterization of the secrecy capacity as a function of the number $β$: the number of eavesdropper antennas per sender antenna. We show that the eavesdropper is comparatively ineffective when $β<1$, but that for $β\ge2$ the eavesdropper can drive the secrecy capacity to zero, thereby blocking secure communication to the intended receiver. Extensions to ergodic fading channels are also provided.
On The Limitations of The Naive Lattice Decoding
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, the inherent drawbacks of the naive lattice decoding for MIMO fading systems is investigated. We show that using the naive lattice decoding for MIMO systems has considerable deficiencies in terms of the rate-diversity trade-off. Unlike the case of maximum-likelihood decoding, in this case, even the perfect lattice space-time codes which have the non-vanishing determinant property can not achieve the optimal rate-diversity trade-off. Indeed, we show that in the case of naive lattice decoding, when we fix the underlying lattice, all the codes based on full-rate lattices have the same rate-diversity trade-off as V-BLAST. Also, we drive a lower bound on the symbol error probability of the naive lattice decoding for the fixed-rate MIMO systems (with equal numbers of receive and transmit antennas). This bound shows that asymptotically, the naive lattice decoding has an unbounded loss in terms of the required SNR, compared to the maximum likelihood decoding.
Solution of moving-boundary problems by the spectral element method
Venue: arXiv cs.CE 2007
Year: 2007

This paper describes a novel numerical model aiming at solving moving-boundary problems such as free-surface flows or fluid-structure interaction. This model uses a moving-grid technique to solve the Navier--Stokes equations expressed in the arbitrary Lagrangian--Eulerian kinematics. The discretization in space is based on the spectral element method. The coupling of the fluid equations and the moving-grid equations is essentially done through the conditions on the moving boundaries. Two- and three-dimensional simulations are presented: translation and rotation of a cylinder in a fluid, and large-amplitude sloshing in a rectangular tank. The accuracy and robustness of the present numerical model is studied and discussed.
Relationship between clustering and algorithmic phase transitions in the random k-XORSAT model and its NP-complete extensions
Venue: arXiv cs.CC 2007
Year: 2007

We study the performances of stochastic heuristic search algorithms on Uniquely Extendible Constraint Satisfaction Problems with random inputs. We show that, for any heuristic preserving the Poissonian nature of the underlying instance, the (heuristic-dependent) largest ratio $α_a$ of constraints per variables for which a search algorithm is likely to find solutions is smaller than the critical ratio $α_d$ above which solutions are clustered and highly correlated. In addition we show that the clustering ratio can be reached when the number k of variables per constraints goes to infinity by the so-called Generalized Unit Clause heuristic.
An Integrated Simulation System for Human Factors Study
Venue: arXiv cs.HC 2007
Year: 2007

It has been reported that virtual reality can be a useful tool for ergonomics study. The proposed integrated simulation system aims at measuring operator's performance in an interactive way for 2D control panel design. By incorporating some sophisticated virtual reality hardware/software, the system allows natural human-system and/or human-human interaction in a simulated virtual environment; enables dynamic objective measurement of human performance; and evaluates the quality of the system design in human factors perspective based on the measurement. It can also be for operation training for some 2D control panels.
Designing a Virtual Manikin Animation Framework Aimed at Virtual Prototyping
Venue: arXiv cs.RO 2007
Year: 2007

In the industry, numerous commercial packages provide tools to introduce, and analyse human behaviour in the product's environment (for maintenance, ergonomics...), thanks to Virtual Humans. We will focus on control. Thanks to algorithms newly introduced in recent research papers, we think we can provide an implementation, which even widens, and simplifies the animation capacities of virtual manikins. In order to do so, we are going to express the industrial expectations as for Virtual Humans, without considering feasibility (not to bias the issue). The second part will show that no commercial application provides the tools that perfectly meet the needs. Thus we propose a new animation framework that better answers the problem. Our contribution is the integration - driven by need ~ of available new scientific techniques to animate Virtual Humans, in a new control scheme that better answers industrial expectations.
A Greedy Randomized Adaptive Search Procedure for Technicians and Interventions Scheduling for Telecommunications
Venue: arXiv cs.DM 2007
Year: 2007

The subject of the 5th challenge proposed by the French Society of Operations Research and Decision Analysis (ROADEF) consists in scheduling technicians and interventions for telecommunications (http://www.g-scop.inpg.fr/ChallengeROADEF2007/ or http://www.roadef.org/). We detail the algorithm we proposed for this challenge which is a Greedy Randomized Adaptative Search Procedure (GRASP). Computational results led us to the 1st position in the Junior category and to the 4th position in All category of the Challenge ROADEF 2007.
Computational performance of a parallelized high-order spectral and mortar element toolbox
Venue: arXiv cs.DC 2007
Year: 2007

In this paper, a comprehensive performance review of a MPI-based high-order spectral and mortar element method C++ toolbox is presented. The focus is put on the performance evaluation of several aspects with a particular emphasis on the parallel efficiency. The performance evaluation is analyzed and compared to predictions given by a heuristic model, the so-called Gamma model. A tailor-made CFD computation benchmark case is introduced and used to carry out this review, stressing the particular interest for commodity clusters. Conclusions are drawn from this extensive series of analyses and modeling leading to specific recommendations concerning such toolbox development and parallel implementation.
A Sudoku Game for People with Motor Impairments
Venue: arXiv cs.HC 2007
Year: 2007

Computer games are motivating and beneficial in learning different educational skills. Most people use their fingers, hands, and arms when using a computer game. However, for people with motor disabilities this task can be a barrier. We present a new Sudoku game for people whose motion is impaired, called Sudoku 4ALL. With this special interface a person can control the game with the voice or with a single switch. Our research aims to cautiously search for issues that might be appropriate for computational support and to build enabling technologies that increase individuals' functional independence in a game environment.
Enumerating the Nash equilibria of rank 1-games
Venue: arXiv cs.GT 2007
Year: 2007

A bimatrix game $(A,B)$ is called a game of rank $k$ if the rank of the matrix $A+B$ is at most $k$. We consider the problem of enumerating the Nash equilibria in (non-degenerate) games of rank 1. In particular, we show that even for games of rank 1 not all equilibria can be reached by a Lemke-Howson path and present a parametric simplex-type algorithm for enumerating all Nash equilibria of a non-degenerate game of rank 1.
Experiments with small helicopter automated landings at unusual attitudes
Venue: arXiv cs.RO 2007
Year: 2007

This paper describes a set of experiments involving small helicopters landing automated landing at unusual attitudes. By leveraging the increased agility of small air vehicles, we show that it is possible to automatically land a small helicopter on surfaces pitched at angles up to 60 degrees. Such maneuvers require considerable agility from the vehicle and its avionics system, and they pose significant technical and safety challenges. Our work builds upon previous activities in human-inspired, high-agility flight for small rotorcraft. However, it was not possible to leverage manual flight test data to extract landing maneuvers due to stringent attitude and position control requirements. Availability of low-cost, local navigation systems requiring no on-board instrumentation has proven particularly important for these experiments to be successful.