OpenRaiser/Intern-Atlas huggingface dataset:
Proving Correctness and Completeness of Normal Programs - a Declarative Approach
Venue: arXiv cs.LO 2005
Year: 2005

We advocate a declarative approach to proving properties of logic programs. Total correctness can be separated into correctness, completeness and clean termination; the latter includes non-floundering. Only clean termination depends on the operational semantics, in particular on the selection rule. We show how to deal with correctness and completeness in a declarative way, treating programs only from the logical point of view. Specifications used in this approach are interpretations (or theories). We point out that specifications for correctness may differ from those for completeness, as usually there are answers which are neither considered erroneous nor required to be computed. We present proof methods for correctness and completeness for definite programs and generalize them to normal programs. For normal programs we use the 3-valued completion semantics; this is a standard semantics corresponding to negation as finite failure. The proof methods employ solely the classical 2-valued logic. We use a 2-valued characterization of the 3-valued completion semantics which may be of separate interest. The presented methods are compared with an approach based on operational semantics. We also employ the ideas of this work to generalize a known method of proving termination of normal programs.
Improved Approximation Algorithms for Geometric Set Cover
Venue: arXiv cs.CG 2005
Year: 2005

Given a collection S of subsets of some set U, and M a subset of U, the set cover problem is to find the smallest subcollection C of S such that M is a subset of the union of the sets in C. While the general problem is NP-hard to solve, even approximately, here we consider some geometric special cases, where usually U = R^d. Extending prior results, we show that approximation algorithms with provable performance exist, under a certain general condition: that for a random subset R of S and function f(), there is a decomposition of the portion of U not covered by R into an expected f(|R|) regions, each region of a particular simple form. We show that under this condition, a cover of size O(f(|C|)) can be found. Our proof involves the generalization of shallow cuttings to more general geometric situations. We obtain constant-factor approximation algorithms for covering by unit cubes in R^3, for guarding a one-dimensional terrain, and for covering by similar-sized fat triangles in R^2. We also obtain improved approximation guarantees for fat triangles, of arbitrary size, and for a class of fat objects.
Relational Algebra as non-Distributive Lattice
Venue: arXiv cs.DB 2005
Year: 2005

We reduce the set of classic relational algebra operators to two binary operations: natural join and generalized union. We further demonstrate that this set of operators is relationally complete and honors lattice axioms.
Estimation of the Number of Sources in Unbalanced Arrays via Information Theoretic Criteria
Venue: arXiv cs.IT 2005
Year: 2005

Estimating the number of sources impinging on an array of sensors is a well known and well investigated problem. A common approach for solving this problem is to use an information theoretic criterion, such as Minimum Description Length (MDL) or the Akaike Information Criterion (AIC). The MDL estimator is known to be a consistent estimator, robust against deviations from the Gaussian assumption, and non-robust against deviations from the point source and/or temporally or spatially white additive noise assumptions. Over the years several alternative estimation algorithms have been proposed and tested. Usually, these algorithms are shown, using computer simulations, to have improved performance over the MDL estimator, and to be robust against deviations from the assumed spatial model. Nevertheless, these robust algorithms have high computational complexity, requiring several multi-dimensional searches. In this paper, motivated by real life problems, a systematic approach toward the problem of robust estimation of the number of sources using information theoretic criteria is taken. An MDL type estimator that is robust against deviation from assumption of equal noise level across the array is studied. The consistency of this estimator, even when deviations from the equal noise level assumption occur, is proven. A novel low-complexity implementation method avoiding the need for multi-dimensional searches is presented as well, making this estimator a favorable choice for practical applications.
A Non-Cooperative Power Control Game for Multi-Carrier CDMA Systems
Venue: arXiv cs.IT 2005
Year: 2005

In this work, a non-cooperative power control game for multi-carrier CDMA systems is proposed. In the proposed game, each user needs to decide how much power to transmit over each carrier to maximize its overall utility. The utility function considered here measures the number of reliable bits transmitted per joule of energy consumed. It is shown that the user's utility is maximized when the user transmits only on the carrier with the best "effective channel". The existence and uniqueness of Nash equilibrium for the proposed game are investigated and the properties of equilibrium are studied. Also, an iterative and distributed algorithm for reaching the equilibrium (if it exists) is presented. It is shown that the proposed approach results in a significant improvement in the total utility achieved at equilibrium compared to the case in which each user maximizes its utility over each carrier independently.
Capacity Regions and Optimal Power Allocation for Groupwise Multiuser Detection
Venue: arXiv cs.IT 2005
Year: 2005

In this paper, optimal power allocation and capacity regions are derived for GSIC (groupwise successive interference cancellation) systems operating in multipath fading channels, under imperfect channel estimation conditions. It is shown that the impact of channel estimation errors on the system capacity is two-fold: it affects the receivers' performance within a group of users, as well as the cancellation performance (through cancellation errors). An iterative power allocation algorithm is derived, based on which it can be shown that the total required received power is minimized when the groups are ordered according to their cancellation errors, and the first detected group has the smallest cancellation error. Performace/complexity tradeoff issues are also discussed by directly comparing the system capacity for different implementations: GSIC with linear minimum-mean-square error (LMMSE) receivers within the detection groups, GSIC with matched filter receivers, multicode LMMSE systems, and simple all matched filter receivers systems.
Multi-document Biography Summarization
Venue: arXiv cs.CL 2005
Year: 2005

In this paper we describe a biography summarization system using sentence classification and ideas from information retrieval. Although the individual techniques are not new, assembling and applying them to generate multi-document biographies is new. Our system was evaluated in DUC2004. It is among the top performers in task 5-short summaries focused by person questions.
Faults and Improvements of an Enhanced Remote User Authentication Scheme Using Smart Cards
Venue: arXiv cs.CR 2005
Year: 2005

In 2000, Hwang and Li proposed a remote user authentication scheme using smart cards to solve the problems of Lamport scheme. Later, Chan- Chang, Shen- Lin- Hwang and then Chang-Hwang pointed out some attacks on Hwang – Li’s scheme. In 2003, Shen, Lin and Hwang also proposed a modified scheme to remove these attacks. In the same year, Leung-Cheng-Fong-Chan showed that modified scheme proposed by Shen-Lin-Hwang is still insecure. In 2004, Awasthi and Lal enhanced Shen-Lin-Hwang’s scheme to overcome its security pitfalls. This paper analyses that the user U/smart card does not provide complete information for the execution and proper running of the login phase of the Awasthi- Lal’s scheme. Furthermore, this paper also modifies the Awasthi- Lal’s scheme for the proper functioning.
Context Related Derivation of Word Senses
Venue: arXiv cs.AI 2005
Year: 2005

Real applications of natural language document processing are very often confronted with domain specific lexical gaps during the analysis of documents of a new domain. This paper describes an approach for the derivation of domain specific concepts for the extension of an existing ontology. As resources we need an initial ontology and a partially processed corpus of a domain. We exploit the specific characteristic of the sublanguage in the corpus. Our approach is based on syntactical structures (noun phrases) and compound analyses to extract information required for the extension of GermaNet's lexical resources.
Some Extensions of Gallager's Method to General Sources and Channels
Venue: arXiv cs.IT 2005
Year: 2005

The Gallager bound is well known in the area of channel coding. However, most discussions about it mainly focus on its applications to memoryless channels. We show in this paper that the bounds obtained by Gallager's method are very tight even for general sources and channels that are defined in the information-spectrum theory. Our method is mainly based on the estimations of error exponents in those bounds, and by these estimations we proved the direct part of the Slepian-Wolf theorem and channel coding theorem for general sources and channels.
Performance Considerations for Gigabyte per Second Transcontinental Disk-to-Disk File Transfers
Venue: arXiv cs.DB 2005
Year: 2005

Moving data from CERN to Pasadena at a gigabyte per second using the next generation Internet requires good networking and good disk IO. Ten Gbps Ethernet and OC192 links are in place, so now it is simply a matter of programming. This report describes our preliminary work and measurements in configuring the disk subsystem for this effort. Using 24 SATA disks at each endpoint we are able to locally read and write an NTFS volume is striped across 24 disks at 1.2 GBps. A 32-disk stripe delivers 1.7 GBps. Experiments on higher performance and higher-capacity systems deliver up to 3.5 GBps.
On the asymptotic behavior of some Algorithms
Venue: arXiv cs.DS 2005
Year: 2005

A simple approach is presented to study the asymptotic behavior of some algorithms with an underlying tree structure. It is shown that some asymptotic oscillating behaviors can be precisely analyzed without resorting to complex analysis techniques as it is usually done in this context. A new explicit representation of periodic functions involved is obtained at the same time.
Population Sizing for Genetic Programming Based Upon Decision Making
Venue: arXiv cs.AI 2005
Year: 2005

This paper derives a population sizing relationship for genetic programming (GP). Following the population-sizing derivation for genetic algorithms in Goldberg, Deb, and Clark (1992), it considers building block decision making as a key facet. The analysis yields a GP-unique relationship because it has to account for bloat and for the fact that GP solutions often use subsolution multiple times. The population-sizing relationship depends upon tree size, solution complexity, problem difficulty and building block expression probability. The relationship is used to analyze and empirically investigate population sizing for three model GP problems named ORDER, ON-OFF and LOUD. These problems exhibit bloat to differing extents and differ in whether their solutions require the use of a building block multiple times.
Markets are Dead, Long Live Markets
Venue: arXiv cs.OS 2005
Year: 2005

Researchers have long proposed using economic approaches to resource allocation in computer systems. However, few of these proposals became operational, let alone commercial. Questions persist about the economic approach regarding its assumptions, value, applicability, and relevance to system design. The goal of this paper is to answer these questions. We find that market-based resource allocation is useful, and more importantly, that mechanism design and system design should be integrated to produce systems that are both economically and computationally efficient.
Near Maximum-Likelihood Performance of Some New Cyclic Codes Constructed in the Finite-Field Transform Domain
Venue: arXiv cs.IT 2005
Year: 2005

It is shown that some well-known and some new cyclic codes with orthogonal parity-check equations can be constructed in the finite-field transform domain. It is also shown that, for some binary linear cyclic codes, the performance of the iterative decoder can be improved by substituting some of the dual code codewords in the parity-check matrix with other dual code codewords formed from linear combinations. This technique can bring the performance of a code closer to its maximum-likelihood performance, which can be derived from the erroneous decoded codeword whose euclidean distance with the respect to the received block is smaller than that of the correct codeword. For (63,37), (93,47) and (105,53) cyclic codes, the maximum-likelihood performance is realised with this technique.
Efficient Parallel Simulations of Asynchronous Cellular Arrays
Venue: arXiv cs.DC 2005
Year: 2005

A definition for a class of asynchronous cellular arrays is proposed. An example of such asynchrony would be independent Poisson arrivals of cell iterations. The Ising model in the continuous time formulation of Glauber falls into this class. Also proposed are efficient parallel algorithms for simulating these asynchronous cellular arrays. In the algorithms, one or several cells are assigned to a processing element (PE), local times for different PEs can be different. Although the standard serial algorithm by Metropolis, Rosenbluth, Rosenbluth, Teller, and Teller can simulate such arrays, it is usually believed to be without an efficient parallel counterpart. However, the proposed parallel algorithms contradict this belief proving to be both efficient and able to perform the same task as the standard algorithm. The results of experiments with the new algorithms are encouraging: the speed-up is greater than 16 using 25 PEs on a shared memory MIMD bus computer, and greater than 1900 using 2**14 PEs on a SIMD computer. The algorithm by Bortz, Kalos, and Lebowitz can be incorporated in the proposed parallel algorithms, further contributing to speed-up. [In this paper I invented the update-cites-of-local-time-minima parallel simulation scheme. Now the scheme is becoming popular. Many misprints of the original 1987 Complex Systems publication are corrected here.-B.L.]
Decomposable Problems, Niching, and Scalability of Multiobjective Estimation of Distribution Algorithms
Venue: arXiv cs.NE 2005
Year: 2005

The paper analyzes the scalability of multiobjective estimation of distribution algorithms (MOEDAs) on a class of boundedly-difficult additively-separable multiobjective optimization problems. The paper illustrates that even if the linkage is correctly identified, massive multimodality of the search problems can easily overwhelm the nicher and lead to exponential scale-up. Facetwise models are subsequently used to propose a growth rate of the number of differing substructures between the two objectives to avoid the niching method from being overwhelmed and lead to polynomial scalability of MOEDAs.
A Geographic Directed Preferential Internet Topology Model
Venue: arXiv cs.NI 2005
Year: 2005

The goal of this work is to model the peering arrangements between Autonomous Systems (ASes). Most existing models of the AS-graph assume an undirected graph. However, peering arrangements are mostly asymmetric Customer-Provider arrangements, which are better modeled as directed edges. Furthermore, it is well known that the AS-graph, and in particular its clustering structure, is influenced by geography. We introduce a new model that describes the AS-graph as a directed graph, with an edge going from the customer to the provider, but also models symmetric peer-to-peer arrangements, and takes geography into account. We are able to mathematically analyze its power-law exponent and number of leaves. Beyond the analysis we have implemented our model as a synthetic network generator we call GdTang. Experimentation with GdTang shows that the networks it produces are more realistic than those generated by other network generators, in terms of its power-law exponent, fractions of customer-provider and symmetric peering arrangements, and the size of its dense core. We believe that our model is the first to manifest realistic regional dense cores that have a clear geographic flavor. Our synthetic networks also exhibit path inflation effects that are similar to those observed in the real AS graph.
The Lattice of Machine Invariant Sets and Subword Complexity
Venue: arXiv cs.CR 2005
Year: 2005

We investigate the lattice of machine invariant classes. This is an infinite completely distributive lattice but it is not a Boolean lattice. We show the subword complexity and the growth function create machine invariant classes. So the lattice would serve as a measure of words cryptographic quality if we like to identify new stream ciphers suitable for widespread adoption.
Highly Scalable Algorithms for Robust String Barcoding
Venue: arXiv cs.DS 2005
Year: 2005

String barcoding is a recently introduced technique for genomic-based identification of microorganisms. In this paper we describe the engineering of highly scalable algorithms for robust string barcoding. Our methods enable distinguisher selection based on whole genomic sequences of hundreds of microorganisms of up to bacterial size on a well-equipped workstation, and can be easily parallelized to further extend the applicability range to thousands of bacterial size genomes. Experimental results on both randomly generated and NCBI genomic data show that whole-genome based selection results in a number of distinguishers nearly matching the information theoretic lower bounds for the problem.
On the Complexity of Real Functions
Venue: arXiv cs.CC 2005
Year: 2005

We develop a notion of computability and complexity of functions over the reals, which seems to be very natural when one tries to determine just how "difficult" a certain function is. This notion can be viewed as an extension of both BSS computability [Blum, Cucker, Shub, Smale 1998], and bit computability in the tradition of computable analysis [Weihrauch 2000] as it relies on the latter but allows some discontinuities and multiple values.
Tables, Memorized Semirings and Applications
Venue: arXiv cs.MA 2005
Year: 2005

We define and construct a new data structure, the tables, this structure generalizes the (finite) $k$-sets sets of Eilenberg \cite{Ei}, it is versatile (one can vary the letters, the words and the coefficients). We derive from this structure a new semiring (with several semiring structures) which can be applied to the needs of automatic processing multi-agents behaviour problems. The purpose of this account/paper is to present also the basic elements of this new structures from a combinatorial point of view. These structures present a bunch of properties. They will be endowed with several laws namely : Sum, Hadamard product, Cauchy product, Fuzzy operations (min, max, complemented product) Two groups of applications are presented. The first group is linked to the process of "forgetting" information in the tables. The second, linked to multi-agent systems, is announced by showing a methodology to manage emergent organization from individual behaviour models.
Graphs and colorings for answer set programming
Venue: arXiv cs.AI 2005
Year: 2005

We investigate the usage of rule dependency graphs and their colorings for characterizing and computing answer sets of logic programs. This approach provides us with insights into the interplay between rules when inducing answer sets. We start with different characterizations of answer sets in terms of totally colored dependency graphs that differ in graph-theoretical aspects. We then develop a series of operational characterizations of answer sets in terms of operators on partial colorings. In analogy to the notion of a derivation in proof theory, our operational characterizations are expressed as (non-deterministically formed) sequences of colorings, turning an uncolored graph into a totally colored one. In this way, we obtain an operational framework in which different combinations of operators result in different formal properties. Among others, we identify the basic strategy employed by the noMoRe system and justify its algorithmic approach. Furthermore, we distinguish operations corresponding to Fitting's operator as well as to well-founded semantics. (To appear in Theory and Practice of Logic Programming (TPLP))
The Self-Organization of Speech Sounds
Venue: arXiv cs.LG 2005
Year: 2005

The speech code is a vehicle of language: it defines a set of forms used by a community to carry information. Such a code is necessary to support the linguistic interactions that allow humans to communicate. How then may a speech code be formed prior to the existence of linguistic interactions? Moreover, the human speech code is discrete and compositional, shared by all the individuals of a community but different across communities, and phoneme inventories are characterized by statistical regularities. How can a speech code with these properties form? We try to approach these questions in the paper, using the "methodology of the artificial". We build a society of artificial agents, and detail a mechanism that shows the formation of a discrete speech code without pre-supposing the existence of linguistic capacities or of coordinated interactions. The mechanism is based on a low-level model of sensory-motor interactions. We show that the integration of certain very simple and non language-specific neural devices leads to the formation of a speech code that has properties similar to the human speech code. This result relies on the self-organizing properties of a generic coupling between perception and production within agents, and on the interactions between agents. The artificial system helps us to develop better intuitions on how speech might have appeared, by showing how self-organization might have helped natural selection to find speech.
Towards a Systematic Account of Different Semantics for Logic Programs
Venue: arXiv cs.AI 2005
Year: 2005

In [Hitzler and Wendt 2002, 2005], a new methodology has been proposed which allows to derive uniform characterizations of different declarative semantics for logic programs with negation. One result from this work is that the well-founded semantics can formally be understood as a stratified version of the Fitting (or Kripke-Kleene) semantics. The constructions leading to this result, however, show a certain asymmetry which is not readily understood. We will study this situation here with the result that we will obtain a coherent picture of relations between different semantics for normal logic programs.
Approximation of dynamical systems using S-systems theory : application to biological systems
Venue: arXiv cs.SC 2005
Year: 2005

In this paper we propose a new symbolic-numeric algorithm to find positive equilibria of a n-dimensional dynamical system. This algorithm implies a symbolic manipulation of ODE in order to give a local approximation of differential equations with power-law dynamics (S-systems). A numerical calculus is then needed to converge towards an equilibrium, giving at the same time a S-system approximating the initial system around this equilibrium. This algorithm is applied to a real biological example in 14 dimensions which is a subsystem of a metabolic pathway in Arabidopsis Thaliana.
Weighted Automata in Text and Speech Processing
Venue: arXiv cs.CL 2005
Year: 2005

Finite-state automata are a very effective tool in natural language processing. However, in a variety of applications and especially in speech precessing, it is necessary to consider more general machines in which arcs are assigned weights or costs. We briefly describe some of the main theoretical and algorithmic aspects of these machines. In particular, we describe an efficient composition algorithm for weighted transducers, and give examples illustrating the value of determinization and minimization algorithms for weighted automata.