OpenRaiser/Intern-Atlas huggingface dataset:
Insertion Sort is O(n log n)
Venue: arXiv cs.DS 2004
Year: 2004

Traditional Insertion Sort runs in O(n^2) time because each insertion takes O(n) time. When people run Insertion Sort in the physical world, they leave gaps between items to accelerate insertions. Gaps help in computers as well. This paper shows that Gapped Insertion Sort has insertion times of O(log n) with high probability, yielding a total running time of O(n log n) with high probability.
Zero-error communication over networks
Venue: arXiv cs.IT 2004
Year: 2004

Zero-Error communication investigates communication without any error. By defining channels without probabilities, results from Elias can be used to completely characterize which channel can simulate which other channels. We introduce the ambiguity of a channel, which completely characterizes the possibility in principle of a channel to simulate any other channel. In the second part we will look at networks of players connected by channels, while some players may be corrupted. We will show how the ambiguity of a virtual channel connecting two arbitrary players can be calculated. This means that we can exactly specify what kind of zero-error communication is possible between two players in any network of players connected by channels.
Improved error bounds for the erasure/list scheme: the binary and spherical cases
Venue: arXiv cs.IT 2004
Year: 2004

We derive improved bounds on the error and erasure rate for spherical codes and for binary linear codes under Forney's erasure/list decoding scheme and prove some related results.
An agent-based intelligent environmental monitoring system
Venue: arXiv cs.MA 2004
Year: 2004

Fairly rapid environmental changes call for continuous surveillance and on-line decision making. There are two main areas where IT technologies can be valuable. In this paper we present a multi-agent system for monitoring and assessing air-quality attributes, which uses data coming from a meteorological station. A community of software agents is assigned to monitor and validate measurements coming from several sensors, to assess air-quality, and, finally, to fire alarms to appropriate recipients, when needed. Data mining techniques have been used for adding data-driven, customized intelligence into agents. The architecture of the developed system, its domain ontology, and typical agent interactions are presented. Finally, the deployment of a real-world test case is demonstrated.
Scheduling with Fuzzy Methods
Venue: arXiv cs.OH 2004
Year: 2004

Nowadays, manufacturing industries -- driven by fierce competition and rising customer requirements -- are forced to produce a broader range of individual products of rising quality at the same (or preferably lower) cost. Meeting these demands implies an even more complex production process and thus also an appropriately increasing request to its scheduling. Aggravatingly, vagueness of scheduling parameters -- such as times and conditions -- are often inherent in the production process. In addition, the search for an optimal schedule normally leads to very difficult problems (NP-hard problems in the complexity theoretical sense), which cannot be solved effciently. With the intent to minimize these problems, the introduced heuristic method combines standard scheduling methods with fuzzy methods to get a nearly optimal schedule within an appropriate time considering vagueness adequately.
Generalized Evolutionary Algorithm based on Tsallis Statistics
Venue: arXiv cs.AI 2004
Year: 2004

Generalized evolutionary algorithm based on Tsallis canonical distribution is proposed. The algorithm uses Tsallis generalized canonical distribution to weigh the configurations for `selection' instead of Gibbs-Boltzmann distribution. Our simulation results show that for an appropriate choice of non-extensive index that is offered by Tsallis statistics, evolutionary algorithms based on this generalization outperform algorithms based on Gibbs-Boltzmann distribution.
A Hyper-Arc Consistency Algorithm for the Soft Alldifferent Constraint
Venue: arXiv cs.PL 2004
Year: 2004

This paper presents an algorithm that achieves hyper-arc consistency for the soft alldifferent constraint. To this end, we prove and exploit the equivalence with a minimum-cost flow problem. Consistency of the constraint can be checked in O(nm) time, and hyper-arc consistency is achieved in O(m) time, where n is the number of variables involved and m is the sum of the cardinalities of the domains. It improves a previous method that did not ensure hyper-arc consistency.
Performance Analysis of the Globus Toolkit Monitoring and Discovery Service, MDS2
Venue: arXiv cs.DC 2004
Year: 2004

Monitoring and information services form a key component of a distributed system, or Grid. A quantitative study of such services can aid in understanding the performance limitations, advise in the deployment of the monitoring system, and help evaluate future development work. To this end, we examined the performance of the Globus Toolkit(reg. trdmrk) Monitoring and Discovery Service (MDS2) by instrumenting its main services using NetLogger. Our study shows a strong advantage to caching or prefetching the data, as well as the need to have primary components at well-connected sites.
Why Two Sexes?
Venue: arXiv cs.NE 2004
Year: 2004

Evolutionary role of the separation into two sexes from a cyberneticist's point of view. [I translated this 1965 article from Russian "Nauka i Zhizn" (Science and Life) in 1988. In a popular form, the article puts forward several useful ideas not all of which even today are necessarily well known or widely accepted. Boris Lubachevsky, bdl@bell-labs.com ]
Typestate Checking and Regular Graph Constraints
Venue: arXiv cs.PL 2004
Year: 2004

We introduce regular graph constraints and explore their decidability properties. The motivation for regular graph constraints is 1) type checking of changing types of objects in the presence of linked data structures, 2) shape analysis techniques, and 3) generalization of similar constraints over trees and grids. We define a subclass of graphs called heaps as an abstraction of the data structures that a program constructs during its execution. We prove that determining the validity of implication for regular graph constraints over the class of heaps is undecidable. We show undecidability by exhibiting a characterization of certain "corresponder graphs" in terms of presence and absence of homomorphisms to a finite number of fixed graphs. The undecidability of implication of regular graph constraints implies that there is no algorithm that will verify that procedure preconditions are met or that the invariants are maintained when these properties are expressed in any specification language at least as expressive as regular graph constraints.
On Role Logic
Venue: arXiv cs.PL 2004
Year: 2004

We present role logic, a notation for describing properties of relational structures in shape analysis, databases, and knowledge bases. We construct role logic using the ideas of de Bruijn's notation for lambda calculus, an encoding of first-order logic in lambda calculus, and a simple rule for implicit arguments of unary and binary predicates. The unrestricted version of role logic has the expressive power of first-order logic with transitive closure. Using a syntactic restriction on role logic formulas, we identify a natural fragment RL^2 of role logic. We show that the RL^2 fragment has the same expressive power as two-variable logic with counting C^2 and is therefore decidable. We present a translation of an imperative language into the decidable fragment RL^2, which allows compositional verification of programs that manipulate relational structures. In addition, we show how RL^2 encodes boolean shape analysis constraints and an expressive description logic.
Collaborative Storage Management In Sensor Networks
Venue: arXiv cs.NI 2004
Year: 2004

In this paper, we consider a class of sensor networks where the data is not required in real-time by an observer; for example, a sensor network monitoring a scientific phenomenon for later play back and analysis. In such networks, the data must be stored in the network. Thus, in addition to battery power, storage is a primary resource: the useful lifetime of the network is constrained by its ability to store the generated data samples. We explore the use of collaborative storage technique to efficiently manage data in storage constrained sensor networks. The proposed collaborative storage technique takes advantage of spatial correlation among the data collected by nearby sensors to significantly reduce the size of the data near the data sources. We show that the proposed approach provides significant savings in the size of the stored data vs. local buffering, allowing the network to run for a longer time without running out of storage space and reducing the amount of data that will eventually be relayed to the observer. In addition, collaborative storage performs load balancing of the available storage space if data generation rates are not uniform across sensors (as would be the case in an event driven sensor network), or if the available storage varies across the network.
Optimizing compilation of constraint handling rules in HAL
Venue: arXiv cs.PL 2004
Year: 2004

In this paper we discuss the optimizing compilation of Constraint Handling Rules (CHRs). CHRs are a multi-headed committed choice constraint language, commonly applied for writing incremental constraint solvers. CHRs are usually implemented as a language extension that compiles to the underlying language. In this paper we show how we can use different kinds of information in the compilation of CHRs in order to obtain access efficiency, and a better translation of the CHR rules into the underlying language, which in this case is HAL. The kinds of information used include the types, modes, determinism, functional dependencies and symmetries of the CHR constraints. We also show how to analyze CHR programs to determine this information about functional dependencies, symmetries and other kinds of information supporting optimizations.
CHR Grammars
Venue: arXiv cs.CL 2004
Year: 2004

A grammar formalism based upon CHR is proposed analogously to the way Definite Clause Grammars are defined and implemented on top of Prolog. These grammars execute as robust bottom-up parsers with an inherent treatment of ambiguity and a high flexibility to model various linguistic phenomena. The formalism extends previous logic programming based grammars with a form of context-sensitive rules and the possibility to include extra-grammatical hypotheses in both head and body of grammar rules. Among the applications are straightforward implementations of Assumption Grammars and abduction under integrity constraints for language analysis. CHR grammars appear as a powerful tool for specification and implementation of language processors and may be proposed as a new standard for bottom-up grammars in logic programming. To appear in Theory and Practice of Logic Programming (TPLP), 2005
Calculus on Graphs
Venue: arXiv cs.DM 2004
Year: 2004

The purpose of this paper is to develop a "calculus" on graphs that allows graph theory to have new connections to analysis. For example, our framework gives rise to many new partial differential equations on graphs, most notably a new (Laplacian based) wave equation; this wave equation gives rise to a partial improvement on the Chung-Faber-Manteuffel diameter/eigenvalue bound in graph theory, and the Chung-Grigoryan-Yau and (in a certain case) Bobkov-Ledoux distance/eigenvalue bounds in analysis. Our framework also allows most techniques for the non-linear p-Laplacian in analysis to be easily carried over to graph theory.
Medians and Beyond: New Aggregation Techniques for Sensor Networks
Venue: arXiv cs.DC 2004
Year: 2004

Wireless sensor networks offer the potential to span and monitor large geographical areas inexpensively. Sensors, however, have significant power constraint (battery life), making communication very expensive. Another important issue in the context of sensor-based information systems is that individual sensor readings are inherently unreliable. In order to address these two aspects, sensor database systems like TinyDB and Cougar enable in-network data aggregation to reduce the communication cost and improve reliability. The existing data aggregation techniques, however, are limited to relatively simple types of queries such as SUM, COUNT, AVG, and MIN/MAX. In this paper we propose a data aggregation scheme that significantly extends the class of queries that can be answered using sensor networks. These queries include (approximate) quantiles, such as the median, the most frequent data values, such as the consensus value, a histogram of the data distribution, as well as range queries. In our scheme, each sensor aggregates the data it has received from other sensors into a fixed (user specified) size message. We provide strict theoretical guarantees on the approximation quality of the queries in terms of the message size. We evaluate the performance of our aggregation scheme by simulation and demonstrate its accuracy, scalability and low resource utilization for highly variable input data sets.
Fractal geometry of literature: first attempt to Shakespeare's works
Venue: arXiv cs.CL 2004
Year: 2004

It was demonstrated that there is a geometrical order in the structure of literature. Fractal geometry as a modern mathematical approach and a new geometrical viewpoint on natural objects including both processes and structures was employed for analysis of literature. As the first study, the works of William Shakespeare were chosen as the most important items in western literature. By counting the number of letters applied in a manuscript, it is possible to study the whole manuscript statistically. A novel method based on basic assumption of fractal geometry was proposed for the calculation of fractal dimensions of the literature. The results were compared with Zipf's law. Zipf's law was successfully used for letters instead of words. Two new concepts namely Zipf's dimension and Zipf's order were also introduced. It was found that changes of both fractal dimension and Zipf's dimension are similar and dependent on the manuscript length. Interestingly, direct plotting the data obtained in semi-logarithmic and logarithmic forms also led to a power-law.
The Arithmetical Complexity of Dimension and Randomness
Venue: arXiv cs.LO 2004
Year: 2004

Constructive dimension and constructive strong dimension are effectivizations of the Hausdorff and packing dimensions, respectively. Each infinite binary sequence A is assigned a dimension dim(A) in [0,1] and a strong dimension Dim(A) in [0,1]. Let DIM^alpha and DIMstr^alpha be the classes of all sequences of dimension alpha and of strong dimension alpha, respectively. We show that DIM^0 is properly Pi^0_2, and that for all Delta^0_2-computable alpha in (0,1], DIM^alpha is properly Pi^0_3. To classify the strong dimension classes, we use a more powerful effective Borel hierarchy where a co-enumerable predicate is used rather than a enumerable predicate in the definition of the Sigma^0_1 level. For all Delta^0_2-computable alpha in [0,1), we show that DIMstr^alpha is properly in the Pi^0_3 level of this hierarchy. We show that DIMstr^1 is properly in the Pi^0_2 level of this hierarchy. We also prove that the class of Schnorr random sequences and the class of computably random sequences are properly Pi^0_3.
Providing Authentic Long-term Archival Access to Complex Relational Data
Venue: arXiv cs.DL 2004
Year: 2004

We discuss long-term preservation of and access to relational databases. The focus is on national archives and science data archives which have to ingest and integrate data from a broad spectrum of vendor-specific relational database management systems (RDBMS). Furthermore, we present our solution SIARD which analyzes and extracts data and data logic from almost any RDBMS. It enables, to a reasonable level of authenticity, complete detachment of databases from their vendor-specific environment. The user can add archival descriptive metadata according to a customizable schema. A SIARD database archive integrates data, data logic, technical metadata, and archival descriptive information in one archival information package, independent of any specific software and hardware, based upon plain text files and the standardized languages SQL and XML. For usage purposes, a SIARD archive can be reloaded into any current or future RDBMS which supports standard SQL. In addition, SIARD contains a client that enables 'on demand' reload of archives into a target RDBMS, and multi-user remote access for querying and browsing the data together with its technical and descriptive metadata in one graphical user interface.
Automatic Generation of CHR Constraint Solvers
Venue: arXiv cs.LO 2004
Year: 2004

In this paper, we present a framework for automatic generation of CHR solvers given the logical specification of the constraints. This approach takes advantage of the power of tabled resolution for constraint logic programming, in order to check the validity of the rules. Compared to previous works where different methods for automatic generation of constraint solvers have been proposed, our approach enables the generation of more expressive rules (even recursive and splitting rules) that can be used directly as CHR solvers.
Desynchronization and Speedup in an Asynchronous Conservative Parallel Update Protocol
Venue: arXiv cs.DC 2004
Year: 2004

In a state-update protocol for a system of $L$ asynchronous parallel processes that communicate only with nearest neighbors, global desynchronization in operation times can be deduced from kinetic roughening of the corresponding virtual-time horizon (VTH). The utilization of the parallel processing environment can be deduced by analyzing the microscopic structure of the VTH. We give an overview of how the methods of non-equilibrium surface growth (physics of complex systems) can be applied to uncover some properties of state update algorithms used in distributed parallel discrete-event simulations (PDES). In particular, we focus on the asynchronous conservative PDES algorithm in a ring communication topology. The time evolution of its VTH is simulated numerically as asynchronous cellular automaton whose update rule corresponds to the update rule followed by this algorithm. We give theoretical estimates of the performance as a function of $L$ and the load per processor, i.e., approximate formulas for the mean speedup and for the desynchronization. It is established that, for a given simulation size, there is a theoretical upper bound for the desynchronization and a theoretical non-zero lower bound for the utilization. The new approach to performance studies, outlined in this chapter, is particularly useful in the search for the design of a new-generation of algorithms that would efficiently carry out an autonomous or tunable synchronization.
A new architecture for making highly scalable applications
Venue: arXiv cs.HC 2004
Year: 2004

An application is a logical image of the world on a computer. A scalable application is an application that allows one to update that logical image at run time. To put it in operational terms: an application is scalable if a client can change between time T1 and time T2 - the logic of the application as expressed by language L; - the structure and volume of the stored knowledge; - the user interface of the application; while clients working with the application at time T1 will work with the changed application at time T2 without performing any special action between T1 and T2. In order to realize such a scalable application a new architecture has been developed that fully orbits around language. In order to verify the soundness of that architecture a program has been build. Both architecture and program are called CommunSENS. The main purpose of this paper is: - to list the relevant elements of the architecture; - to give a visual presentation of how the program and its image of the world look like; - to give a visual presentation of how the image can be updated. Some relevant philosophical and practical backgrounds are included in the appendixes.
An ALC(D)-based combination of temporal constraints and spatial constraints suitable for continuous (spatial) change
Venue: arXiv cs.AI 2004
Year: 2004

We present a family of spatio-temporal theories suitable for continuous spatial change in general, and for continuous motion of spatial scenes in particular. The family is obtained by spatio-temporalising the well-known ALC(D) family of Description Logics (DLs) with a concrete domain D, as follows, where TCSPs denotes "Temporal Constraint Satisfaction Problems", a well-known constraint-based framework: (1) temporalisation of the roles, so that they consist of TCSP constraints (specifically, of an adaptation of TCSP constraints to interval variables); and (2) spatialisation of the concrete domain D: the concrete domain is now $D_x$, and is generated by a spatial Relation Algebra (RA) $x$, in the style of the Region-Connection Calculus RCC8. We assume durative truth (i.e., holding during a durative interval). We also assume the homogeneity property (if a truth holds during a given interval, it holds during all of its subintervals). Among other things, these assumptions raise the "conflicting" problem of overlapping truths, which the work solves with the use of a specific partition of the 13 atomic relations of Allen's interval algebra.
Diffusive Load Balancing of Loosely-Synchronous Parallel Programs over Peer-to-Peer Networks
Venue: arXiv cs.DC 2004
Year: 2004

The use of under-utilized Internet resources is widely recognized as a viable form of high performance computing. Sustained processing power of roughly 40T FLOPS using 4 million volunteered Internet hosts has been reported for embarrassingly parallel problems. At the same time, peer-to-peer (P2P) file sharing networks, with more than 50 million participants, have demonstrated the capacity for scale in distributed systems. This paper contributes a study of load balancing techniques for a general class of loosely-synchronous parallel algorithms when executed over a P2P network. We show that decentralized, diffusive load balancing can be effective at balancing load and is facilitated by the dynamic properties of P2P. While a moderate degree of dynamicity can benefit load balancing, significant dynamicity hinders the parallel program performance due to the need for increased load migration. To the best of our knowledge this study provides new insight into the performance of loosely-synchronous parallel programs over the Internet.
Nondeterministic Linear Logic
Venue: arXiv cs.LO 2004
Year: 2004

In this paper, we introduce Linear Logic with a nondeterministic facility, which has a self-dual additive connective. In the system the proof net technology is available in a natural way. The important point is that nondeterminism in the system is expressed by the process of normalization, not by proof search. Moreover we can incorporate the system into Light Linear Logic and Elementary Linear Logic developed by J.-Y.Girard recently: Nondeterministic Light Linear Logic and Nondeterministic Elementary Linear Logic are defined in a very natural way.