OpenRaiser/Intern-Atlas huggingface dataset:
Radix Sorting With No Extra Space
Venue: arXiv cs.DS 2007
Year: 2007

It is well known that n integers in the range [1,n^c] can be sorted in O(n) time in the RAM model using radix sorting. More generally, integers in any range [1,U] can be sorted in O(n sqrt{loglog n}) time. However, these algorithms use O(n) words of extra memory. Is this necessary? We present a simple, stable, integer sorting algorithm for words of size O(log n), which works in O(n) time and uses only O(1) words of extra memory on a RAM model. This is the integer sorting case most useful in practice. We extend this result with same bounds to the case when the keys are read-only, which is of theoretical interest. Another interesting question is the case of arbitrary c. Here we present a black-box transformation from any RAM sorting algorithm to a sorting algorithm which uses only O(1) extra space and has the same running time. This settles the complexity of in-place sorting in terms of the complexity of sorting.
Theory of Finite or Infinite Trees Revisited
Venue: arXiv cs.LO 2007
Year: 2007

We present in this paper a first-order axiomatization of an extended theory $T$ of finite or infinite trees, built on a signature containing an infinite set of function symbols and a relation $\fini(t)$ which enables to distinguish between finite or infinite trees. We show that $T$ has at least one model and prove its completeness by giving not only a decision procedure, but a full first-order constraint solver which gives clear and explicit solutions for any first-order constraint satisfaction problem in $T$. The solver is given in the form of 16 rewriting rules which transform any first-order constraint $ϕ$ into an equivalent disjunction $ϕ$ of simple formulas such that $ϕ$ is either the formula $\true$ or the formula $\false$ or a formula having at least one free variable, being equivalent neither to $\true$ nor to $\false$ and where the solutions of the free variables are expressed in a clear and explicit way. The correctness of our rules implies the completeness of $T$. We also describe an implementation of our algorithm in CHR (Constraint Handling Rules) and compare the performance with an implementation in C++ and that of a recent decision procedure for decomposable theories.
Another view of the Gaussian algorithm
Venue: arXiv cs.DS 2007
Year: 2007

We introduce here a rewrite system in the group of unimodular matrices, \emph{i.e.}, matrices with integer entries and with determinant equal to $\pm 1$. We use this rewrite system to precisely characterize the mechanism of the Gaussian algorithm, that finds shortest vectors in a two--dimensional lattice given by any basis. Putting together the algorithmic of lattice reduction and the rewrite system theory, we propose a new worst--case analysis of the Gaussian algorithm. There is already an optimal worst--case bound for some variant of the Gaussian algorithm due to Vallée \cite {ValGaussRevisit}. She used essentially geometric considerations. Our analysis generalizes her result to the case of the usual Gaussian algorithm. An interesting point in our work is its possible (but not easy) generalization to the same problem in higher dimensions, in order to exhibit a tight upper-bound for the number of iterations of LLL--like reduction algorithms in the worst case. Moreover, our method seems to work for analyzing other families of algorithms. As an illustration, the analysis of sorting algorithms are briefly developed in the last section of the paper.
Semantic Information Retrieval from Distributed Heterogeneous Data Sources
Venue: arXiv cs.DB 2007
Year: 2007

Information retrieval from distributed heterogeneous data sources remains a challenging issue. As the number of data sources increases more intelligent retrieval techniques, focusing on information content and semantics, are required. Currently ontologies are being widely used for managing semantic knowledge, especially in the field of bioinformatics. In this paper we describe an ontology assisted system that allows users to query distributed heterogeneous data sources by hiding details like location, information structure, access pattern and semantic structure of the data. Our goal is to provide an integrated view on biomedical information sources for the Health-e-Child project with the aim to overcome the lack of sufficient semantic-based reformulation techniques for querying distributed data sources. In particular, this paper examines the problem of query reformulation across biomedical data sources, based on merged ontologies and the underlying heterogeneous descriptions of the respective data sources.
Experiences of Engineering Grid-Based Medical Software
Venue: arXiv cs.DC 2007
Year: 2007

Objectives: Grid-based technologies are emerging as potential solutions for managing and collaborating distributed resources in the biomedical domain. Few examples exist, however, of successful implementations of Grid-enabled medical systems and even fewer have been deployed for evaluation in practice. The objective of this paper is to evaluate the use in clinical practice of a Grid-based imaging prototype and to establish directions for engineering future medical Grid developments and their subsequent deployment. Method: The MammoGrid project has deployed a prototype system for clinicians using the Grid as its information infrastructure. To assist in the specification of the system requirements (and for the first time in healthgrid applications), use-case modelling has been carried out in close collaboration with clinicians and radiologists who had no prior experience of this modelling technique. A critical qualitative and, where possible, quantitative analysis of the MammoGrid prototype is presented leading to a set of recommendations from the delivery of the first deployed Grid-based medical imaging application. Results: We report critically on the application of software engineering techniques in the specification and implementation of the MammoGrid project and show that use-case modelling is a suitable vehicle for representing medical requirements and for communicating effectively with the clinical community. This paper also discusses the practical advantages and limitations of applying the Grid to real-life clinical applications and presents the consequent lessons learned.
Resource Allocation for Wireless Fading Relay Channels: Max-Min Solution
Venue: arXiv cs.IT 2007
Year: 2007

As a basic information-theoretic model for fading relay channels, the parallel relay channel is first studied, for which lower and upper bounds on the capacity are derived. For the parallel relay channel with degraded subchannels, the capacity is established, and is further demonstrated via the Gaussian case, for which the synchronized and asynchronized capacities are obtained. The capacity achieving power allocation at the source and relay nodes among the subchannels is characterized. The fading relay channel is then studied, for which resource allocations that maximize the achievable rates are obtained for both the full-duplex and half-duplex cases. Capacities are established for fading relay channels that satisfy certain conditions.
Clusters, Graphs, and Networks for Analysing Internet-Web-Supported Communication within a Virtual Community
Venue: arXiv cs.AI 2007
Year: 2007

The proposal is to use clusters, graphs and networks as models in order to analyse the Web structure. Clusters, graphs and networks provide knowledge representation and organization. Clusters were generated by co-site analysis. The sample is a set of academic Web sites from the countries belonging to the European Union. These clusters are here revisited from the point of view of graph theory and social network analysis. This is a quantitative and structural analysis. In fact, the Internet is a computer network that connects people and organizations. Thus we may consider it to be a social network. The set of Web academic sites represents an empirical social network, and is viewed as a virtual community. The network structural properties are here analysed applying together cluster analysis, graph theory and social network analysis.
On the error exponent of variable-length block-coding schemes over finite-state Markov channels with feedback
Venue: arXiv cs.IT 2007
Year: 2007

The error exponent of Markov channels with feedback is studied in the variable-length block-coding setting. Burnashev's classic result is extended and a single letter characterization for the reliability function of finite-state Markov channels is presented, under the assumption that the channel state is causally observed both at the transmitter and at the receiver side. Tools from stochastic control theory are used in order to treat channels with intersymbol interference. In particular the convex analytical approach to Markov decision processes is adopted to handle problems with stopping time horizons arising from variable-length coding schemes.
A distributed Approach for Access and Visibility Task under Ergonomic Constraints with a Manikin in a Virtual Reality Environment
Venue: arXiv cs.RO 2007
Year: 2007

This paper presents a new method, based on a multi-agent system and on digital mock-up technology, to assess an efficient path planner for a manikin for access and visibility task under ergonomic constraints. In order to solve this problem, the human operator is integrated in the process optimization to contribute to a global perception of the environment. This operator cooperates, in real-time, with several automatic local elementary agents. The result of this work validates solutions brought by digital mock-up and that can be applied to simulate maintenance task.
Modélisation Dynamique d'un Robot Parallèle à 3-DDL : l'Orthoglide
Venue: arXiv cs.RO 2007
Year: 2007

In this article, we propose a method for calculation of the inverse and direct dynamic models of the Orthoglide, a parallel robot with threedegrees of freedom in translation. These models are calculated starting from the elements of the dynamic model of the kinematic chain structure and equations of Newton-Euler applied to the platform. These models are obtained in explicit form having an interesting physical interpretation.
An Integrated Crosscutting Concern Migration Strategy and its Application to JHotDraw
Venue: arXiv cs.SE 2007
Year: 2007

In this paper we propose a systematic strategy for migrating crosscutting concerns in existing object-oriented systems to aspect-based solutions. The proposed strategy consists of four steps: mining, exploration, documentation and refactoring of crosscutting concerns. We discuss in detail a new approach to aspect refactoring that is fully integrated with our strategy, and apply the whole strategy to an object-oriented system, namely the JHotDraw framework. The result of this migration is made available as an open-source project, which is the largest aspect refactoring available to date. We report on our experiences with conducting this case study and reflect on the success and challenges of the migration process, as well as on the feasibility of automatic aspect refactoring.
A fixed point iteration for computing the matrix logarithm
Venue: arXiv cs.NA 2007
Year: 2007

In various areas of applied numerics, the problem of calculating the logarithm of a matrix A emerges. Since series expansions of the logarithm usually do not converge well for matrices far away from the identity, the standard numerical method calculates successive square roots. In this article, a new algorithm is presented that relies on the computation of successive matrix exponentials. Convergence of the method is demonstrated for a large class of initial matrices and favorable choices of the initial matrix are discussed.
A Classification of 3R Orthogonal Manipulators by the Topology of their Workspace
Venue: arXiv cs.RO 2007
Year: 2007

A classification of a family of 3-revolute (3R) positining manipulators is established. 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 design parameters space is shown to be divided into nine domains of distinct workspace topologies, in which all manipulators have similar global kinematic properties. Each separating surface is given as an explicit expression in the DH-parameters.
Situations d'apprentissage collectives instrumentées : étude de pratiques dans l'enseignement supérieur
Venue: arXiv cs.CY 2007
Year: 2007

Currently, educational platforms propose many tools of communication, production, labour division or collective work management in order to support collective activities. But it is not guaranteed that actors (instructional designers, tutors or learner) are really using them. Our work, describe characteristics of instrumented learning situations (ICLS) in the higher education. Our intention is to determine: if ICLS are really existing; which form they take (in terms of scenario, tools, type of activity...) ; if recommendations resulting from research tasks are taken into account by instructional designers and if the instructional designer prescribed activities are really follow by learners or tutors? To answer these questions, we have made a survey about ICLS actors uses.
Inductive Definition and Domain Theoretic Properties of Fully Abstract
Venue: arXiv cs.LO 2007
Year: 2007

A construction of fully abstract typed models for PCF and PCF^+ (i.e., PCF + "parallel conditional function"), respectively, is presented. It is based on general notions of sequential computational strategies and wittingly consistent non-deterministic strategies introduced by the author in the seventies. Although these notions of strategies are old, the definition of the fully abstract models is new, in that it is given level-by-level in the finite type hierarchy. To prove full abstraction and non-dcpo domain theoretic properties of these models, a theory of computational strategies is developed. This is also an alternative and, in a sense, an analogue to the later game strategy semantics approaches of Abramsky, Jagadeesan, and Malacaria; Hyland and Ong; and Nickau. In both cases of PCF and PCF^+ there are definable universal (surjective) functionals from numerical functions to any given type, respectively, which also makes each of these models unique up to isomorphism. Although such models are non-omega-complete and therefore not continuous in the traditional terminology, they are also proved to be sequentially complete (a weakened form of omega-completeness), "naturally" continuous (with respect to existing directed "pointwise", or "natural" lubs) and also "naturally" omega-algebraic and "naturally" bounded complete -- appropriate generalisation of the ordinary notions of domain theory to the case of non-dcpos.
A Generalized Information Formula as the Bridge between Shannon and Popper
Venue: arXiv cs.IT 2007
Year: 2007

A generalized information formula related to logical probability and fuzzy set is deduced from the classical information formula. The new information measure accords with to Popper's criterion for knowledge evolution very much. In comparison with square error criterion, the information criterion does not only reflect error of a proposition, but also reflects the particularity of the event described by the proposition. It gives a proposition with less logical probability higher evaluation. The paper introduces how to select a prediction or sentence from many for forecasts and language translations according to the generalized information criterion. It also introduces the rate fidelity theory, which comes from the improvement of the rate distortion theory in the classical information theory by replacing distortion (i.e. average error) criterion with the generalized mutual information criterion, for data compression and communication efficiency. Some interesting conclusions are obtained from the rate-fidelity function in relation to image communication. It also discusses how to improve Popper's theory.
A Six Degree-Of-Freedom Haptic Device Based On The Orthoglide And A Hybrid Agile Eye
Venue: arXiv cs.RO 2007
Year: 2007

This paper is devoted to the kinematic design of a new six degree-of-freedom haptic device using two parallel mechanisms. The first one, called orthoglide, provides the translation motions and the second one, called agile eye, produces the rotational motions. These two motions are decoupled to simplify the direct and inverse kinematics, as it is needed for real-time control. To reduce the inertial load, the motors are fixed on the base and a transmission with two universal joints is used to transmit the rotational motions from the base to the end-effector. Two alternative wrists are proposed (i), the agile eye with three degrees of freedom or (ii) a hybrid wrist made by the assembly of a two-dof agile eye with a rotary motor. The last one is optimized to increase its stiffness and to decrease the number of moving parts.
An Exhaustive Study of the Workspace Topologies of all 3R Orthogonal Manipulators with Geometric Simplifications
Venue: arXiv cs.RO 2007
Year: 2007

This paper analyses the workspace of the three-revolute orthogonal manipulators that have at least one of their DH parameters equal to zero. These manipulators are classified into different groups with similar kinematic properties. The classification criteria are based on the topology of the workspace. Each group is evaluated according to interesting kinematic properties such as the size of the workspace subregion reachable with four inverse kinematic solutions, the existence and the size of voids, and the size of the regions of feasible paths in the workspace.
Practical Approach to Knowledge-based Question Answering with Natural Language Understanding and Advanced Reasoning
Venue: arXiv cs.CL 2007
Year: 2007

This research hypothesized that a practical approach in the form of a solution framework known as Natural Language Understanding and Reasoning for Intelligence (NaLURI), which combines full-discourse natural language understanding, powerful representation formalism capable of exploiting ontological information and reasoning approach with advanced features, will solve the following problems without compromising practicality factors: 1) restriction on the nature of question and response, and 2) limitation to scale across domains and to real-life natural language text.
The effect of fading, channel inversion, and threshold scheduling on ad hoc networks
Venue: arXiv cs.IT 2007
Year: 2007

This paper addresses three issues in the field of ad hoc network capacity: the impact of i)channel fading, ii) channel inversion power control, and iii) threshold-based scheduling on capacity. Channel inversion and threshold scheduling may be viewed as simple ways to exploit channel state information (CSI) without requiring cooperation across transmitters. We use the transmission capacity (TC) as our metric, defined as the maximum spatial intensity of successful simultaneous transmissions subject to a constraint on the outage probability (OP). By assuming the nodes are located on the infinite plane according to a Poisson process, we are able to employ tools from stochastic geometry to obtain asymptotically tight bounds on the distribution of the signal-to-interference (SIR) level, yielding in turn tight bounds on the OP (relative to a given SIR threshold) and the TC. We demonstrate that in the absence of CSI, fading can significantly reduce the TC and somewhat surprisingly, channel inversion only makes matters worse. We develop a threshold-based transmission rule where transmitters are active only if the channel to their receiver is acceptably strong, obtain expressions for the optimal threshold, and show that this simple, fully distributed scheme can significantly reduce the effect of fading.
Use of a $d$-Constraint During LDPC Decoding in a Bliss Scheme
Venue: arXiv cs.IT 2007
Year: 2007

Bliss schemes of a run length limited (RLL) codec in combination with an LDPC codec, generate LDPC parity bits over a systematic sequence of RLL channel bits that are inherently redundant as they satisfy e.g. a $d=1$ minimum run length constraint. That is the subsequences consisting of runs of length $d=1$, viz. $...010...$ and $...101...$, cannot occur. We propose to use this redundancy during LDPC decoding in a Bliss scheme by introducing additional $d$-constraint nodes in the factor graph used by the LDPC decoder. The messages sent from these new nodes to the variable or codeword bit nodes exert a ``force'' on the resulting soft-bit vector coming out of the LDPC decoding that give it a tendency to comply with the $d$-constraints. This way, we can significantly reduce the probability of decoding error.
Closed form solutions for symmetric water filling games
Venue: arXiv cs.NI 2007
Year: 2007

We study power control in optimization and game frameworks. In the optimization framework there is a single decision maker who assigns network resources and in the game framework users share the network resources according to Nash equilibrium. The solution of these problems is based on so-called water-filling technique, which in turn uses bisection method for solution of non-linear equations for Lagrange multiplies. Here we provide a closed form solution to the water-filling problem, which allows us to solve it in a finite number of operations. Also, we produce a closed form solution for the Nash equilibrium in symmetric Gaussian interference game with an arbitrary number of users. Even though the game is symmetric, there is an intrinsic hierarchical structure induced by the quantity of the resources available to the users. We use this hierarchical structure to perform a successive reduction of the game. In addition, to its mathematical beauty, the explicit solution allows one to study limiting cases when the crosstalk coefficient is either small or large. We provide an alternative simple proof of the convergence of the Iterative Water Filling Algorithm. Furthermore, it turns out that the convergence of Iterative Water Filling Algorithm slows down when the crosstalk coefficient is large. Using the closed form solution, we can avoid this problem. Finally, we compare the non-cooperative approach with the cooperative approach and show that the non-cooperative approach results in a more fair resource distribution.
Four-Group Decodable Space-Time Block Codes
Venue: arXiv cs.IT 2007
Year: 2007

Two new rate-one full-diversity space-time block codes (STBC) are proposed. They are characterized by the \emph{lowest decoding complexity} among the known rate-one STBC, arising due to the complete separability of the transmitted symbols into four groups for maximum likelihood detection. The first and the second codes are delay-optimal if the number of transmit antennas is a power of 2 and even, respectively. The exact pair-wise error probability is derived to allow for the performance optimization of the two codes. Compared with existing low-decoding complexity STBC, the two new codes offer several advantages such as higher code rate, lower encoding/decoding delay and complexity, lower peak-to-average power ratio, and better performance.