OpenRaiser/Intern-Atlas huggingface dataset:
Discrete Price Updates Yield Fast Convergence in Ongoing Markets with Finite Warehouses
Venue: arXiv cs.GT 2010
Year: 2010

This paper shows that in suitable markets, even with out-of-equilibrium trade allowed, a simple price update rule leads to rapid convergence toward the equilibrium. In particular, this paper considers a Fisher market repeated over an unbounded number of time steps, with the addition of finite sized warehouses to enable non-equilibrium trade. The main result is that suitable tatonnement style price updates lead to convergence in a significant subset of markets satisfying the Weak Gross Substitutes property. Throughout this process the warehouse are always able to store or meet demand imbalances (the needed capacity depends on the initial imbalances). Finally, our price update rule is robust in a variety of regards: 1. The updates for each good depend only on information about that good (its current price, its excess demand since its last update) and occur asynchronously from updates to other prices. 2. The process is resilient to error in the excess demand data. 3. Likewise, the process is resilient to discreteness, i.e. a limit to divisibility, both of goods and money.
Integrating digital human modeling into virtual environment for ergonomic oriented design
Venue: arXiv cs.RO 2010
Year: 2010

Virtual human simulation integrated into virtual reality applications is mainly used for virtual representation of the user in virtual environment or for interactions between the user and the virtual avatar for cognitive tasks. In this paper, in order to prevent musculoskeletal disorders, the integration of virtual human simulation and VR application is presented to facilitate physical ergonomic evaluation, especially for physical fatigue evaluation of a given population. Immersive working environments are created to avoid expensive physical mock-up in conventional evaluation methods. Peripheral motion capture systems are used to capture natural movements and then to simulate the physical operations in virtual human simulation. Physical aspects of human's movement are then analyzed to determine the effort level of each key joint using inverse kinematics. The physical fatigue level of each joint is further analyzed by integrating a fatigue and recovery model on the basis of physical task parameters. All the process has been realized based on VRHIT platform and a case study is presented to demonstrate the function of the physical fatigue for a given population and its usefulness for worker selection.
A Simple Correctness Proof for Magic Transformation
Venue: arXiv cs.LO 2010
Year: 2010

The paper presents a simple and concise proof of correctness of the magic transformation. We believe it may provide a useful example of formal reasoning about logic programs. The correctness property concerns the declarative semantics. The proof, however, refers to the operational semantics (LD-resolution) of the source programs. Its conciseness is due to applying a suitable proof method.
Passively Mobile Communicating Machines that Use Restricted Space
Venue: arXiv cs.CC 2010
Year: 2010

We propose a new theoretical model for passively mobile Wireless Sensor Networks, called PM, standing for Passively mobile Machines. The main modification w.r.t. the Population Protocol model is that agents now, instead of being automata, are Turing Machines. We provide general definitions for unbounded memories, but we are mainly interested in computations upper-bounded by plausible space limitations. However, we prove that our results hold for more general cases. We focus on complete communication graphs and define the complexity classes PMSPACE(f(n)) parametrically, consisting of all predicates that are stably computable by some PM protocol that uses O(f(n)) memory on each agent. We provide a protocol that generates unique ids from scratch only by using O(log n) memory, and use it to provide an exact characterization for the classes PMSPACE(f(n)) when f(n)=Ω(log n): they are precisely the classes of all symmetric predicates in NSPACE(nf(n)). In this way, we provide a space hierarchy for the PM model when the memory bounds are Ω(log n). Finally, we explore the computability of the PM model when the protocols use o(loglog n) space per machine and prove that SEMILINEAR=PMSPACE(f(n)) when f(n)=o(loglog n), where SEMILINEAR denotes the class of the semilinear predicates. In fact, we prove that this bound acts as a threshold, so that SEMILINEAR is a proper subset of PMSPACE(f(n)) when f(n)=O(loglog n).
UCMExporter: Supporting Scenario Transformations from Use Case Maps
Venue: arXiv cs.SE 2010
Year: 2010

The Use Case Maps (UCM) scenario notation is applicable to many requirements engineering activities. However, other scenario notations, such as Message Sequence Charts (MSC) and UML Sequence Diagrams (SD), have shown to be better suited for detailed design. In order to use the notation that is best appropriate for each phase in an efficient manner, a mechanism has to be devised to automatically transfer the knowledge acquired during the requirements analysis phase (using UCM) to the design phase (using MSC or SD). This paper introduces UCMEXPORTER, a new tool that implements such a mechanism and reduces the gap between high-level requirements and detailed design. UCMEXPORTER automatically transforms individual UCM scenarios to UML Sequence Diagrams, MSC scenarios, and even TTCN-3 test skeletons. We highlight the current capabilities of the tool as well as architectural solutions addressing the main challenges faced during such transformation, including the handling of concurrent scenario paths, the generation of customized messages, and tool interoperability.
On the Implementation of GNU Prolog
Venue: arXiv cs.PL 2010
Year: 2010

GNU Prolog is a general-purpose implementation of the Prolog language, which distinguishes itself from most other systems by being, above all else, a native-code compiler which produces standalone executables which don't rely on any byte-code emulator or meta-interpreter. Other aspects which stand out include the explicit organization of the Prolog system as a multipass compiler, where intermediate representations are materialized, in Unix compiler tradition. GNU Prolog also includes an extensible and high-performance finite domain constraint solver, integrated with the Prolog language but implemented using independent lower-level mechanisms. This article discusses the main issues involved in designing and implementing GNU Prolog: requirements, system organization, performance and portability issues as well as its position with respect to other Prolog system implementations and the ISO standardization initiative.
A Distributed Trust and Reputation Framework for Mobile Ad Hoc Networks
Venue: arXiv cs.CR 2010
Year: 2010

In a multi-hop mobile ad hoc network (MANET), mobile nodes cooperate to form a network without using any infrastructure such as access points or base stations. The mobility of the nodes and the fundamentally limited capacity of the wireless medium, together with wireless transmission effects such as attenuation, multi-path propagation, and interference combine to create sig-nificant challenges for security in MANETs. Traditional cryptographic mecha-nisms such as authentication and encryption are not capable of handling some kinds of attacks such as packet dropping by malicious nodes in MANETs. This paper presents a mechanism for detecting malicious packet dropping attacks in MANETs. The mechanism is depends on a trust module on each node, which is based on the reputation value computed for that node by its neighbors. The reputation value of a node is computed based on its packet forwarding behavior in the network. The reputation information is gathered, stored and exchanged between the nodes, and computed under different scenario. The proposed pro-tocol has been simulated in a network simulator. The simulation results show the efficiency of its performance.
A Unified MGF-Based Capacity Analysis of Diversity Combiners over Generalized Fading Channels
Venue: arXiv cs.IT 2010
Year: 2010

Unified exact average capacity results for L-branch coherent diversity receivers including equal-gain combining (EGC) and maximal-ratio combining (MRC) are not known. This paper develops a novel generic framework for the capacity analysis of $L$-branch EGC/MRC over generalized fading channels. The framework is used to derive new results for the Gamma shadowed generalized Nakagami-m fading model which can be a suitable model for the fading environments encountered by high frequency (60 GHz and above) communications. The mathematical formalism is illustrated with some selected numerical and simulation results confirming the correctness of our newly proposed framework.
Joint space and workspace analysis of a two-DOF closed-chain manipulator
Venue: arXiv cs.RO 2010
Year: 2010

The aim of this paper is to compute of the generalized aspects, i.e. the maximal singularity-free domains in the Cartesian product of the joint space and workspace, for a planar parallel mechanism in using quadtree model and interval analysis based method. The parallel mechanisms can admit several solutions to the inverses and the direct kinematic models. These singular configurations divide the joint space and the workspace in several not connected domains. To compute this domains, the quadtree model can be made by using a discretization of the space. Unfortunately, with this method, some singular configurations cannot be detected as a single point in the joint space. The interval analysis based method allow us to assure that no singularities are not found and to reduce the computing times. This approach is tested on a simple planar parallel mechanism with two degrees of freedom.
Test of some numerical limiters for the conservative PSM scheme for 4D Drift-Kinetic simulations
Venue: arXiv cs.NA 2010
Year: 2010

The purpose of this work is simulation of magnetised plasmas in the ITER project framework. In this context, Vlasov-Poisson like models are used to simulate core turbulence in the tokamak in a toroidal geometry. This leads to heavy simulation because a 6D dimensional problem has to be solved, 3D in space and 3D in velocity. The model is reduced to a 5D gyrokinetic model, taking advantage of the particular motion of particles due to the presence of a strong magnetic field. However, accurate schemes, parallel algorithms need to be designed to bear these simulations. This paper describes a Hermite formulation of the conservative PSM scheme which is very generic and allows to implement different semi-Lagrangian schemes. We also test and propose numerical limiters which should improve the robustness of the simulations by diminishing spurious oscillations. We only consider here the 4D drift-kinetic model which is the backbone of the 5D gyrokinetic models and relevant to build a robust and accurate numerical method.
Experimental Comparison of Representation Methods and Distance Measures for Time Series Data
Venue: arXiv cs.AI 2010
Year: 2010

The previous decade has brought a remarkable increase of the interest in applications that deal with querying and mining of time series data. Many of the research efforts in this context have focused on introducing new representation methods for dimensionality reduction or novel similarity measures for the underlying data. In the vast majority of cases, each individual work introducing a particular method has made specific claims and, aside from the occasional theoretical justifications, provided quantitative experimental observations. However, for the most part, the comparative aspects of these experiments were too narrowly focused on demonstrating the benefits of the proposed methods over some of the previously introduced ones. In order to provide a comprehensive validation, we conducted an extensive experimental study re-implementing eight different time series representations and nine similarity measures and their variants, and testing their effectiveness on thirty-eight time series data sets from a wide variety of application domains. In this paper, we give an overview of these different techniques and present our comparative experimental findings regarding their effectiveness. In addition to providing a unified validation of some of the existing achievements, our experiments also indicate that, in some cases, certain claims in the literature may be unduly optimistic.
An Improved Algorithm for Bipartite Correlation Clustering
Venue: arXiv cs.DS 2010
Year: 2010

Bipartite Correlation clustering is the problem of generating a set of disjoint bi-cliques on a set of nodes while minimizing the symmetric difference to a bipartite input graph. The number or size of the output clusters is not constrained in any way. The best known approximation algorithm for this problem gives a factor of 11. This result and all previous ones involve solving large linear or semi-definite programs which become prohibitive even for modestly sized tasks. In this paper we present an improved factor 4 approximation algorithm to this problem using a simple combinatorial algorithm which does not require solving large convex programs. The analysis extends a method developed by Ailon, Charikar and Alantha in 2008, where a randomized pivoting algorithm was analyzed for obtaining a 3-approximation algorithm for Correlation Clustering, which is the same problem on graphs (not bipartite). The analysis for Correlation Clustering there required defining events for structures containing 3 vertices and using the probability of these events to produce a feasible solution to a dual of a certain natural LP bounding the optimal cost. It is tempting here to use sets of 4 vertices, which are the smallest structures for which contradictions arise for Bipartite Correlation Clustering. This simple idea, however, appears to be evasive. We show that, by modifying the LP, we can analyze algorithms which take into consideration subgraph structures of unbounded size. We believe our techniques are interesting in their own right, and may be used for other problems as well.
To study the phenomenon of the Moravec's Paradox
Venue: arXiv cs.AI 2010
Year: 2010

"Encoded in the large, highly evolved sensory and motor portions of the human brain is a billion years of experience about the nature of the world and how to survive in it. The deliberate process we call reasoning is, I believe, the thinnest veneer of human thought, effective only because it is supported by this much older and much powerful, though usually unconscious, sensor motor knowledge. We are all prodigious Olympians in perceptual and motor areas, so good that we make the difficult look easy. Abstract thought, though, is a new trick, perhaps less than 100 thousand years old. We have not yet mastered it. It is not all that intrinsically difficult; it just seems so when we do it."- Hans Moravec Moravec's paradox is involved with the fact that it is the seemingly easier day to day problems that are harder to implement in a machine, than the seemingly complicated logic based problems of today. The results prove that most artificially intelligent machines are as adept if not more than us at under-taking long calculations or even play chess, but their logic brings them nowhere when it comes to carrying out everyday tasks like walking, facial gesture recognition or speech recognition.
Cyclic and Quasi-Cyclic LDPC Codes on Row and Column Constrained Parity-Check Matrices and Their Trapping Sets
Venue: arXiv cs.IT 2010
Year: 2010

This paper is concerned with construction and structural analysis of both cyclic and quasi-cyclic codes, particularly LDPC codes. It consists of three parts. The first part shows that a cyclic code given by a parity-check matrix in circulant form can be decomposed into descendant cyclic and quasi-cyclic codes of various lengths and rates. Some fundamental structural properties of these descendant codes are developed, including the characterizations of the roots of the generator polynomial of a cyclic descendant code. The second part of the paper shows that cyclic and quasi-cyclic descendant LDPC codes can be derived from cyclic finite geometry LDPC codes using the results developed in first part of the paper. This enlarges the repertoire of cyclic LDPC codes. The third part of the paper analyzes the trapping sets of regular LDPC codes whose parity-check matrices satisfy a certain constraint on their rows and columns. Several classes of finite geometry and finite field cyclic and quasi-cyclic LDPC codes with large minimum weights are shown to have no harmful trapping sets with size smaller than their minimum weights. Consequently, their performance error-floors are dominated by their minimum weights.
Dynamic Capitalization and Visualization Strategy in Collaborative Knowledge Management System for EI Process
Venue: arXiv cs.AI 2010
Year: 2010

Knowledge is attributed to human whose problem-solving behavior is subjective and complex. In today's knowledge economy, the need to manage knowledge produced by a community of actors cannot be overemphasized. This is due to the fact that actors possess some level of tacit knowledge which is generally difficult to articulate. Problem-solving requires searching and sharing of knowledge among a group of actors in a particular context. Knowledge expressed within the context of a problem resolution must be capitalized for future reuse. In this paper, an approach that permits dynamic capitalization of relevant and reliable actors' knowledge in solving decision problem following Economic Intelligence process is proposed. Knowledge annotation method and temporal attributes are used for handling the complexity in the communication among actors and in contextualizing expressed knowledge. A prototype is built to demonstrate the functionalities of a collaborative Knowledge Management system based on this approach. It is tested with sample cases and the result showed that dynamic capitalization leads to knowledge validation hence increasing reliability of captured knowledge for reuse. The system can be adapted to various domains
Data Conflict Resolution Using Trust Mappings
Venue: arXiv cs.DB 2010
Year: 2010

In massively collaborative projects such as scientific or community databases, users often need to agree or disagree on the content of individual data items. On the other hand, trust relationships often exist between users, allowing them to accept or reject other users' beliefs by default. As those trust relationships become complex, however, it becomes difficult to define and compute a consistent snapshot of the conflicting information. Previous solutions to a related problem, the update reconciliation problem, are dependent on the order in which the updates are processed and, therefore, do not guarantee a globally consistent snapshot. This paper proposes the first principled solution to the automatic conflict resolution problem in a community database. Our semantics is based on the certain tuples of all stable models of a logic program. While evaluating stable models in general is well known to be hard, even for very simple logic programs, we show that the conflict resolution problem admits a PTIME solution. To the best of our knowledge, ours is the first PTIME algorithm that allows conflict resolution in a principled way. We further discuss extensions to negative beliefs and prove that some of these extensions are hard. This work is done in the context of the BeliefDB project at the University of Washington, which focuses on the efficient management of conflicts in community databases.
Descriptive-complexity based distance for fuzzy sets
Venue: arXiv cs.AI 2010
Year: 2010

A new distance function dist(A,B) for fuzzy sets A and B is introduced. It is based on the descriptive complexity, i.e., the number of bits (on average) that are needed to describe an element in the symmetric difference of the two sets. The distance gives the amount of additional information needed to describe any one of the two sets given the other. We prove its mathematical properties and perform pattern clustering on data based on this distance.
List-decoding of binary Goppa codes up to the binary Johnson bound
Venue: arXiv cs.IT 2010
Year: 2010

We study the list-decoding problem of alternant codes, with the notable case of classical Goppa codes. The major consideration here is to take into account the size of the alphabet, which shows great influence on the list-decoding radius. This amounts to compare the \emph{generic} Johnson bound to the \emph{$q$-ary} Johnson bound. This difference is important when $q$ is very small. Essentially, the most favourable case is $q=2$, for which the decoding radius is greatly improved, notably when the relative minimum distance gets close to 1/2. Even though the announced result, which is the list-decoding radius of binary Goppa codes, is new, it can be rather easily made up from previous sources (V. Guruswami, R. M. Roth and I. Tal, R .M. Roth), which may be a little bit unknown, and in which the case of binary Goppa codes has apparently not been thought at. Only D. J. Bernstein treats the case of binary Goppa codes in a preprint. References are given in the introduction. We propose an autonomous treatment and also a complexity analysis of the studied algorithm, which is quadratic in the blocklength $n$, when decoding at some distance of the relative maximum decoding radius, and in $O(n^7)$ when reaching the maximum radius.
Instantaneous, non-squeezed, noise-based logic
Venue: arXiv cs.OH 2010
Year: 2010

Noise-based logic, by utilizing its multidimensional logic hyperspace, has significant potential for low-power parallel operations in beyond-Moore-chips. However universal gates for Boolean logic thus far had to rely on either time averaging to distinguish signals from each other or, alternatively, on squeezed logic signals, where the logic-high was represented by a random process and the logic-low was a zero signal. A major setback is that squeezed logic variables are unable to work in the hyperspace, because the logic-low zero value sets the hyperspace product vector to zero. This paper proposes Boolean universal logic gates that alleviate such shortcomings. They are able to work with non-squeezed logic values where both the high and low values are encoded into nonzero, bipolar, independent random telegraph waves. Non-squeezed universal Boolean logic gates for spike-based brain logic are also shown. The advantages vs. disadvantages of the two logic types are compared.
On the polynomial depth of various sets of random strings
Venue: arXiv cs.CC 2010
Year: 2010

This paper proposes new notions of polynomial depth (called monotone poly depth), based on a polynomial version of monotone Kolmogorov complexity. We show that monotone poly depth satisfies all desirable properties of depth notions i.e., both trivial and random sequences are not monotone poly deep, monotone poly depth satisfies the slow growth law i.e., no simple process can transform a non deep sequence into a deep one, and monotone poly deep sequences exist (unconditionally). We give two natural examples of deep sets, by showing that both the set of Levin-random strings and the set of Kolmogorov random strings are monotone poly deep.