OpenRaiser/Intern-Atlas huggingface dataset:
Hardware-Oriented Group Solutions for Hard Problems
Venue: arXiv cs.CC 2004
Year: 2004

Group and individual solutions are considered for hard problems such as satisfiability problem. Time-space trade-off in a structured active memory provides means to achieve lower time complexity for solutions of these problems.
Efficient Algorithms for Large-Scale Topology Discovery
Venue: arXiv cs.NI 2004
Year: 2004

There is a growing interest in discovery of internet topology at the interface level. A new generation of highly distributed measurement systems is currently being deployed. Unfortunately, the research community has not examined the problem of how to perform such measurements efficiently and in a network-friendly manner. In this paper we make two contributions toward that end. First, we show that standard topology discovery methods (e.g., skitter) are quite inefficient, repeatedly probing the same interfaces. This is a concern, because when scaled up, such methods will generate so much traffic that they will begin to resemble DDoS attacks. We measure two kinds of redundancy in probing (intra- and inter-monitor) and show that both kinds are important. We show that straightforward approaches to addressing these two kinds of redundancy must take opposite tacks, and are thus fundamentally in conflict. Our second contribution is to propose and evaluate Doubletree, an algorithm that reduces both types of redundancy simultaneously on routers and end systems. The key ideas are to exploit the tree-like structure of routes to and from a single point in order to guide when to stop probing, and to probe each path by starting near its midpoint. Our results show that Doubletree can reduce both types of measurement load on the network dramatically, while permitting discovery of nearly the same set of nodes and links. We then show how to enable efficient communication between monitors through the use of Bloom filters.
Intelligent search strategies based on adaptive Constraint Handling Rules
Venue: arXiv cs.AI 2004
Year: 2004

The most advanced implementation of adaptive constraint processing with Constraint Handling Rules (CHR) allows the application of intelligent search strategies to solve Constraint Satisfaction Problems (CSP). This presentation compares an improved version of conflict-directed backjumping and two variants of dynamic backtracking with respect to chronological backtracking on some of the AIM instances which are a benchmark set of random 3-SAT problems. A CHR implementation of a Boolean constraint solver combined with these different search strategies in Java is thus being compared with a CHR implementation of the same Boolean constraint solver combined with chronological backtracking in SICStus Prolog. This comparison shows that the addition of ``intelligence'' to the search process may reduce the number of search steps dramatically. Furthermore, the runtime of their Java implementations is in most cases faster than the implementations of chronological backtracking. More specifically, conflict-directed backjumping is even faster than the SICStus Prolog implementation of chronological backtracking, although our Java implementation of CHR lacks the optimisations made in the SICStus Prolog system. To appear in Theory and Practice of Logic Programming (TPLP).
Dynamic Modelling and Adaptive Traction Control for Mobile Robots
Venue: arXiv cs.RO 2004
Year: 2004

Mobile robots have received a great deal of research in recent years. A significant amount of research has been published in many aspects related to mobile robots. Most of the research is devoted to design and develop some control techniques for robot motion and path planning. A large number of researchers have used kinematic models to develop motion control strategy for mobile robots. Their argument and assumption that these models are valid if the robot has low speed, low acceleration and light load. However, dynamic modelling of mobile robots is very important as they are designed to travel at higher speed and perform heavy duty work. This paper presents and discusses a new approach to develop a dynamic model and control strategy for wheeled mobile robot which I modelled as a rigid body that roles on two wheels and a castor. The motion control strategy consists of two levels. The first level is dealing with the dynamic of the system and denoted as Low level controller. The second level is developed to take care of path planning and trajectory generation.
Using Wireless Sensor Networks to Narrow the Gap between Low-Level Information and Context-Awareness
Venue: arXiv cs.NI 2004
Year: 2004

Wireless sensor networks are finally becoming a reality. In this paper, we present a scalable architecture for using wireless sensor networks in combination with wireless Ethernet networks to provide a complete end-to-end solution to narrow the gap between the low-level information and context awareness. We developed and implemented a complete proximity detector in order to give a wearable computer, such as a PDA, location context. Since location is only one element of contextawareness, we pursued utilizing photo sensors and temperature sensors in learning as much as possible about the environment. We used the TinyOS RF Motes as our test bed WSN (Wireless Sensor Network), 802.11 compatible hardware as our wireless Ethernet network, and conventional PCs and wired 802.3 networks to build the upper levels of the architecture.
An Empirical Analysis of Internet Protocol Version 6 (IPv6)
Venue: arXiv cs.NI 2004
Year: 2004

Although the current Internet Protocol known as IPv4 has served its purpose for over 20 years, its days are numbered. With IPv6 reaching a mature enough level, there is a need to evaluate the performance benefits or drawbacks that the new IPv6 protocol will have in comparison to the well established IPv4 protocol. Theoretically, the overhead between the two different protocols should be directly proportional to the difference in the packet's header size, however according to our findings, the empirical performance difference between IPv4 and IPv6, especially when the transition mechanisms are taken into consideration, is much larger than anticipated. We first examine the performance of each protocol independently. We then examined two transition mechanisms which perform the encapsulation at various points in the network: host-to-host and router-to-router (tunneling). Our experiments were conducted using two dual stack (IPv4/IPv6) routers using end nodes running both Windows 2000 and Solaris 8.0 in order to compare two different IPv6 implementations side by side. Our tests were written in C++ and utilized metrics such as latency, throughput, CPU utilization, socket creation time, socket connection time, web server simulation, and a video client/server application for TCP/UDP in IPv4/IPv6 under both Windows 2000 and Solaris 8.0. Our empirical evaluation proved that IPv6 is not yet a mature enough technology and that it is still years away from having consistent and good enough implementations, as the performance of IPv6 in many cases proved to be significantly worse than IPv4.
Runtime Reconfiguration of J2EE Applications
Venue: arXiv cs.NI 2004
Year: 2004

Runtime reconfiguration considered as "applying required changes to a running system" plays an important role for providing high availability not only of safety- and mission-critical systems, but also for commercial web-applications offering professional services. Hereby, the main concerns are maintaining the consistency of the running system during reconfiguration and minimizing its down-time caused by the reconfiguration. This paper focuses on the platform independent subsystem that realises deployment and redeployment of J2EE modules based on the new J2EE Deployment API as a part of the implementation of our proposed system architecture enabling runtime reconfiguration of component-based systems. Our "controlled runtime redeployment" comprises an extension of hot deployment and dynamic reloading, complemented by allowing for structural change
From Tensor Equations to Numerical Code -- Computer Algebra Tools for Numerical Relativity
Venue: arXiv cs.SC 2004
Year: 2004

In this paper we present our recent work in developing a computer-algebra tool for systems of partial differential equations (PDEs), termed "Kranc". Our work is motivated by the problem of finding solutions of the Einstein equations through numerical simulations. Kranc consists of Mathematica based computer-algebra packages, that facilitate the task of dealing with symbolic tensorial calculations and realize the conversion of systems of partial differential evolution equations into parallelized C or Fortran code.
Geographic Routing with Limited Information in Sensor Networks
Venue: arXiv cs.IT 2004
Year: 2004

Geographic routing with greedy relaying strategies have been widely studied as a routing scheme in sensor networks. These schemes assume that the nodes have perfect information about the location of the destination. When the distance between the source and destination is normalized to unity, the asymptotic routing delays in these schemes are $Θ(\frac{1}{M(n)}),$ where M(n) is the maximum distance traveled in a single hop (transmission range of a radio). In this paper, we consider routing scenarios where nodes have location errors (imprecise GPS), or where only coarse geographic information about the destination is available, and only a fraction of the nodes have routing information. We show that even with such imprecise or limited destination-location information, the routing delays are $Θ(\frac{1}{M(n)})$. We also consider the throughput-capacity of networks with progressive routing strategies that take packets closer to the destination in every step, but not necessarily along a straight-line. We show that the throughput-capacity with progressive routing is order-wise the same as the maximum achievable throughput-capacity.
Modeling the input history of programs for improved instruction-memory performance
Venue: arXiv cs.OS 2004
Year: 2004

When a program is loaded into memory for execution, the relative position of its basic blocks is crucial, since loading basic blocks that are unlikely to be executed first places them high in the instruction-memory hierarchy only to be dislodged as the execution goes on. In this paper we study the use of Bayesian networks as models of the input history of a program. The main point is the creation of a probabilistic model that persists as the program is run on different inputs and at each new input refines its own parameters in order to reflect the program's input history more accurately. As the model is thus tuned, it causes basic blocks to be reordered so that, upon arrival of the next input for execution, loading the basic blocks into memory automatically takes into account the input history of the program. We report on extensive experiments, whose results demonstrate the efficacy of the overall approach in progressively lowering the execution times of a program on identical inputs placed randomly in a sequence of varied inputs. We provide results on selected SPEC CINT2000 programs and also evaluate our approach as compared to the gcc level-3 optimization and to Pettis-Hansen reordering.
Pandora : une plate-forme efficace pour la construction d'applications autonomes
Venue: arXiv cs.NI 2004
Year: 2004

Autonomic computing has been proposed recently as a way to address the difficult management of applications whose complexity is constantly increasing. Autonomous applications will have to be especially flexible and be able to monitor themselves permanently. This work presents a framework, Pandora, which eases the construction of applications that satisfy this double goal. Pandora relies on an original application programming pattern - based on stackable layers and message passing - to obtain minimalist model and architecture that allows to control the overhead imposed by the full reflexivity of the framework. Besides, a prototype of the framework has been implemented in C++. A detailed performance study, together with examples of use, complement this presentation
On the High-SNR Capacity of Non-Coherent Networks
Venue: arXiv cs.IT 2004
Year: 2004

We obtain the first term in the high signal-to-noise ratio (SNR) expansion of the capacity of fading networks where the transmitters and receivers--while fully cognizant of the fading \emph{law}--have no access to the fading \emph{realization}. This term is an integer multiple of $\log \log \textnormal{SNR}$ with the coefficient having a simple combinatorial characterization.
EURYDICE : A platform for unified access to documents
Venue: arXiv cs.DL 2004
Year: 2004

In this paper we present Eurydice, a platform dedicated to provide a unified gateway to documents. Its basic functionalities about collecting documents have been designed based on a long experience about the management of scientific documentation among large and demanding academic communities such as IMAG and INRIA. Besides the basic problem of accessing documents - which was of course the original and main motivation of the project - a great effort has been dedicated to the development of management functionalities which could help institutions to control, analyse the current situation about the use of the documentation, and finally to set a better ground for a documentation policy. Finally a great emphasis - and corresponding technical investment - has been put on the protection of property and reproduction rights both from the users' intitution side and from the editors' side.
Jordan Normal and Rational Normal Form Algorithms
Venue: arXiv cs.SC 2004
Year: 2004

In this paper, we present a determinist Jordan normal form algorithms based on the Fadeev formula: \[(λ\cdot I-A) \cdot B(λ)=P(λ) \cdot I\] where $B(λ)$ is $(λ\cdot I-A)$'s comatrix and $P(λ)$ is $A$'s characteristic polynomial. This rational Jordan normal form algorithm differs from usual algorithms since it is not based on the Frobenius/Smith normal form but rather on the idea already remarked in Gantmacher that the non-zero column vectors of $B(λ_0)$ are eigenvectors of $A$ associated to $λ_0$ for any root $λ_0$ of the characteristical polynomial. The complexity of the algorithm is $O(n^4)$ field operations if we know the factorization of the characteristic polynomial (or $O(n^5 \ln(n))$ operations for a matrix of integers of fixed size). This algorithm has been implemented using the Maple and Giac/Xcas computer algebra systems.
Toward a Human-Centered Uml for Risk Analysis
Venue: arXiv cs.OH 2004
Year: 2004

Safety is now a major concern in many complex systems such as medical robots. A way to control the complexity of such systems is to manage risk. The first and important step of this activity is risk analysis. During risk analysis, two main studies concerning human factors must be integrated: task analysis and human error analysis. This multidisciplinary analysis often leads to a work sharing between several stakeholders who use their own languages and techniques. This often produces consistency errors and understanding difficulties between them. Hence, this paper proposes to treat the risk analysis on the common expression language UML (Unified Modeling Language) and to handle human factors concepts for task analysis and human error analysis based on the features of this language. The approach is applied to the development of a medical robot for teleechography.
Human-Level Performance on Word Analogy Questions by Latent Relational Analysis
Venue: arXiv cs.CL 2004
Year: 2004

This paper introduces Latent Relational Analysis (LRA), a method for measuring relational similarity. LRA has potential applications in many areas, including information extraction, word sense disambiguation, machine translation, and information retrieval. Relational similarity is correspondence between relations, in contrast with attributional similarity, which is correspondence between attributes. When two words have a high degree of attributional similarity, we call them synonyms. When two pairs of words have a high degree of relational similarity, we say that their relations are analogous. For example, the word pair mason/stone is analogous to the pair carpenter/wood. Past work on semantic similarity measures has mainly been concerned with attributional similarity. Recently the Vector Space Model (VSM) of information retrieval has been adapted to the task of measuring relational similarity, achieving a score of 47% on a collection of 374 college-level multiple-choice word analogy questions. In the VSM approach, the relation between a pair of words is characterized by a vector of frequencies of predefined patterns in a large corpus. LRA extends the VSM approach in three ways: (1) the patterns are derived automatically from the corpus (they are not predefined), (2) the Singular Value Decomposition (SVD) is used to smooth the frequency data (it is also used this way in Latent Semantic Analysis), and (3) automatically generated synonyms are used to explore reformulations of the word pairs. LRA achieves 56% on the 374 analogy questions, statistically equivalent to the average human score of 57%. On the related problem of classifying noun-modifier relations, LRA achieves similar gains over the VSM, while using a smaller corpus.
The methods of support of the requirements of the Russian standards at development of a CAD of industrial objects
Venue: arXiv cs.CE 2004
Year: 2004

The methods of support of the requirements of the Russian standards in a CAD of industrial objects are explained, which were implemented in the CAD system TechnoCAD GlassX with an own graphics core and own structures of data storage. It is rotined, that the binding of storage structures and program code of a CAD to the requirements of standards enable not only to fulfil these requirements in project documentation, but also to increase a degree of compactness of storage of drawings both on the disk and in the RAM
The informatization of design works at industry firm during its renovation
Venue: arXiv cs.CE 2004
Year: 2004

The characteristic of design works on firm at its renovation and of the common directions of their informatization is given. The implantation of a CAD is selected as the key direction, and the requirements to a complex CAD-system are stated. The methods of such a CAD-system development are featured, and the connectedness of this development with the process of integration of information space of design department of the firm is characterized. The experience of development and implantation of a complex CAD of renovation of firms TechnoCAD GlassX lies in a basis of this reviewing
Reverse Engineering Ontology to Conceptual Data Models
Venue: arXiv cs.DC 2004
Year: 2004

Ontologies facilitate the integration of heterogeneous data sources by resolving semantic heterogeneity between them. This research aims to study the possibility of generating a domain conceptual model from a given ontology with the vision to grow this generated conceptual data model into a global conceptual model integrating a number of existing data and information sources. Based on ontologically derived semantics of the BWW model, rules are identified that map elements of the ontology language (DAML+OIL) to domain conceptual model elements. This mapping is demonstrated using TAMBIS ontology. A significant corollary of this study is that it is possible to generate a domain conceptual model from a given ontology subject to validation that needs to be performed by the domain specialist before evolving this model into a global conceptual model.
Tycoon: an Implementation of a Distributed, Market-based Resource Allocation System
Venue: arXiv cs.DC 2004
Year: 2004

Distributed clusters like the Grid and PlanetLab enable the same statistical multiplexing efficiency gains for computing as the Internet provides for networking. One major challenge is allocating resources in an economically efficient and low-latency way. A common solution is proportional share, where users each get resources in proportion to their pre-defined weight. However, this does not allow users to differentiate the value of their jobs. This leads to economic inefficiency. In contrast, systems that require reservations impose a high latency (typically minutes to hours) to acquire resources. We present Tycoon, a market based distributed resource allocation system based on proportional share. The key advantages of Tycoon are that it allows users to differentiate the value of their jobs, its resource acquisition latency is limited only by communication delays, and it imposes no manual bidding overhead on users. We present experimental results using a prototype implementation of our design.
The approximability of three-valued MAX CSP
Venue: arXiv cs.CC 2004
Year: 2004

In the maximum constraint satisfaction problem (Max CSP), one is given a finite collection of (possibly weighted) constraints on overlapping sets of variables, and the goal is to assign values from a given domain to the variables so as to maximize the number (or the total weight, for the weighted case) of satisfied constraints. This problem is NP-hard in general, and, therefore, it is natural to study how restricting the allowed types of constraints affects the approximability of the problem. It is known that every Boolean (that is, two-valued) Max CSP problem with a finite set of allowed constraint types is either solvable exactly in polynomial time or else APX-complete (and hence can have no polynomial time approximation scheme unless P=NP. It has been an open problem for several years whether this result can be extended to non-Boolean Max CSP, which is much more difficult to analyze than the Boolean case. In this paper, we make the first step in this direction by establishing this result for Max CSP over a three-element domain. Moreover, we present a simple description of all polynomial-time solvable cases of our problem. This description uses the well-known algebraic combinatorial property of supermodularity. We also show that every hard three-valued Max CSP problem contains, in a certain specified sense, one of the two basic hard Max CSP problems which are the Maximum k-colourable subgraph problems for k=2,3.
TulaFale: A Security Tool for Web Services
Venue: arXiv cs.CR 2004
Year: 2004

Web services security specifications are typically expressed as a mixture of XML schemas, example messages, and narrative explanations. We propose a new specification language for writing complementary machine-checkable descriptions of SOAP-based security protocols and their properties. Our TulaFale language is based on the pi calculus (for writing collections of SOAP processors running in parallel), plus XML syntax (to express SOAP messaging), logical predicates (to construct and filter SOAP messages), and correspondence assertions (to specify authentication goals of protocols). Our implementation compiles TulaFale into the applied pi calculus, and then runs Blanchet's resolution-based protocol verifier. Hence, we can automatically verify authentication properties of SOAP protocols.
How to achieve various gait patterns from single nominal
Venue: arXiv cs.RO 2004
Year: 2004

In this paper is presented an approach to achieving on-line modification of nominal biped gait without recomputing entire dynamics when steady motion is performed. Straight, dynamically balanced walk was used as a nominal gait, and applied modifications were speed-up and slow-down walk and turning left and right. It is shown that the disturbances caused by these modifications jeopardize dynamic stability, but they can be simply compensated to enable walk continuation.