OpenRaiser/Intern-Atlas huggingface dataset:
Decomposing Non-Redundant Sharing by Complementation
Venue: arXiv cs.PL 2001
Year: 2001

Complementation, the inverse of the reduced product operation, is a technique for systematically finding minimal decompositions of abstract domains. File' and Ranzato advanced the state of the art by introducing a simple method for computing a complement. As an application, they considered the extraction by complementation of the pair-sharing domain PS from the Jacobs and Langen's set-sharing domain SH. However, since the result of this operation was still SH, they concluded that PS was too abstract for this. Here, we show that the source of this result lies not with PS but with SH and, more precisely, with the redundant information contained in SH with respect to ground-dependencies and pair-sharing. In fact, a proper decomposition is obtained if the non-redundant version of SH, PSD, is substituted for SH. To establish the results for PSD, we define a general schema for subdomains of SH that includes PSD and Def as special cases. This sheds new light on the structure of PSD and exposes a natural though unexpected connection between Def and PSD. Moreover, we substantiate the claim that complementation alone is not sufficient to obtain truly minimal decompositions of domains. The right solution to this problem is to first remove redundancies by computing the quotient of the domain with respect to the observable behavior, and only then decompose it by complementation.
Optimal Constructions of Hybrid Algorithms
Venue: arXiv cs.DM 2001
Year: 2001

We study on-line strategies for solving problems with hybrid algorithms. There is a problem Q and w basic algorithms for solving Q. For some lambda <= w, we have a computer with lambda disjoint memory areas, each of which can be used to run a basic algorithm and store its intermediate results. In the worst case, only one basic algorithm can solve Q in finite time, and all the other basic algorithms run forever without solving Q. To solve Q with a hybrid algorithm constructed from the basic algorithms, we run a basic algorithm for some time, then switch to another, and continue this process until Q is solved. The goal is to solve Q in the least amount of time. Using competitive ratios to measure the efficiency of a hybrid algorithm, we construct an optimal deterministic hybrid algorithm and an efficient randomized hybrid algorithm. This resolves an open question on searching with multiple robots posed by Baeza-Yates, Culberson and Rawlins. We also prove that our randomized algorithm is optimal for lambda = 1, settling a conjecture of Kao, Reif and Tate.
Computational Geometry Column 41
Venue: arXiv cs.CG 2001
Year: 2001

The recent result that n congruent balls in R^d have at most 4 distinct geometric permutations is described.
A Scientific Data Management System for Irregular Applications
Venue: arXiv cs.DC 2001
Year: 2001

Many scientific applications are I/O intensive and generate or access large data sets, spanning hundreds or thousands of "files." Management, storage, efficient access, and analysis of this data present an extremely challenging task. We have developed a software system, called Scientific Data Manager (SDM), that uses a combination of parallel file I/O and database support for high-performance scientific data management. SDM provides a high-level API to the user and internally, uses a parallel file system to store real data and a database to store application-related metadata. In this paper, we describe how we designed and implemented SDM to support irregular applications. SDM can efficiently handle the reading and writing of data in an irregular mesh as well as the distribution of index values. We describe the SDM user interface and how we implemented it to achieve high performance. SDM makes extensive use of MPI-IO's noncontiguous collective I/O functions. SDM also uses the concept of a history file to optimize the cost of the index distribution using the metadata stored in the database. We present performance results with two irregular applications, a CFD code called FUN3D and a Rayleigh-Taylor instability code, on the SGI Origin2000 at Argonne National Laboratory.
Taking Primitive Optimality Theory Beyond the Finite State
Venue: arXiv cs.CL 2001
Year: 2001

Primitive Optimality Theory (OTP) (Eisner, 1997a; Albro, 1998), a computational model of Optimality Theory (Prince and Smolensky, 1993), employs a finite state machine to represent the set of active candidates at each stage of an Optimality Theoretic derivation, as well as weighted finite state machines to represent the constraints themselves. For some purposes, however, it would be convenient if the set of candidates were limited by some set of criteria capable of being described only in a higher-level grammar formalism, such as a Context Free Grammar, a Context Sensitive Grammar, or a Multiple Context Free Grammar (Seki et al., 1991). Examples include reduplication and phrasal stress models. Here we introduce a mechanism for OTP-like Optimality Theory in which the constraints remain weighted finite state machines, but sets of candidates are represented by higher-level grammars. In particular, we use multiple context-free grammars to model reduplication in the manner of Correspondence Theory (McCarthy and Prince, 1995), and develop an extended version of the Earley Algorithm (Earley, 1970) to apply the constraints to a reduplicating candidate set.
Construction of an algorithm in parallel for the Fast Fourier Transform
Venue: arXiv cs.DC 2001
Year: 2001

It has been designed,built and executed a code for the Fast Fourier Transform (FFT),compiled and executed in a cluster of 2^n computers under the operating system MacOS and using the routines MacMPI. As practical application,the code has been used to obtain the transformed from an astronomic imagen,to execute a filter on its and with a transformed inverse to recover the image with the variates given by the filter.The computers arrangement are installed in the Observatorio Astronomico National in Colombia under the name OAN Cluster and in this has been executed several applications.
Source-Filter Decomposition of Harmonic Sounds
Venue: arXiv cs.SD 2001
Year: 2001

This paper describes a method for decomposing steady-state instrument data into excitation and formant filter components. The input data, taken from several series of recordings of acoustical instruments is analyzed in the frequency domain, and for each series a model is built, which most accurately represents the data as a source-filter system. The source part is taken to be a harmonic excitation system with frequency-invariant magnitudes, and the filter part is considered to be responsible for all spectral inhomogenieties. This method has been applied to the SHARC database of steady state instrument data to create source-filter models for a large number of acoustical instruments. Subsequent use of such models can have a wide variety of applications, including improvements to wavetable and physical modeling synthesis, high quality pitch shifting, and creation of "hybrid" instrument timbres.
Two-parameter Model of Word Length "Language - Genre"
Venue: arXiv cs.CL 2001
Year: 2001

A two-parameter model of word length measured by the number of syllables comprising it is proposed. The first parameter is dependent on language type, the second one - on text genre and reflects the degree of completion of synergetic processes of language optimization.
Notes on computing peaks in k-levels and parametric spanning trees
Venue: arXiv cs.CG 2001
Year: 2001

We give an algorithm to compute all the local peaks in the $k$-level of an arrangement of $n$ lines in $O(n \log n) + \tilde{O}((kn)^{2/3})$ time. We can also find $τ$ largest peaks in $O(n \log ^2 n) + \tilde{O}((τn)^{2/3})$ time. Moreover, we consider the longest edge in a parametric minimum spanning tree (in other words, a bottleneck edge for connectivity), and give an algorithm to compute the parameter value (within a given interval) maximizing/minimizing the length of the longest edge in MST. The time complexity is $\tilde{O}(n^{8/7}k^{1/7} + n k^{1/3})$
Event Indexing Systems for Efficient Selection and Analysis of HERA Data
Venue: arXiv cs.DB 2001
Year: 2001

The design and implementation of two software systems introduced to improve the efficiency of offline analysis of event data taken with the ZEUS Detector at the HERA electron-proton collider at DESY are presented. Two different approaches were made, one using a set of event directories and the other using a tag database based on a commercial object-oriented database management system. These are described and compared. Both systems provide quick direct access to individual collision events in a sequential data store of several terabytes, and they both considerably improve the event analysis efficiency. In particular the tag database provides a very flexible selection mechanism and can dramatically reduce the computing time needed to extract small subsamples from the total event sample. Gains as large as a factor 20 have been obtained.
Potholes on the Royal Road
Venue: arXiv cs.NE 2001
Year: 2001

It is still unclear how an evolutionary algorithm (EA) searches a fitness landscape, and on what fitness landscapes a particular EA will do well. The validity of the building-block hypothesis, a major tenet of traditional genetic algorithm theory, remains controversial despite its continued use to justify claims about EAs. This paper outlines a research program to begin to answer some of these open questions, by extending the work done in the royal road project. The short-term goal is to find a simple class of functions which the simple genetic algorithm optimizes better than other optimization methods, such as hillclimbers. A dialectical heuristic for searching for such a class is introduced. As an example of using the heuristic, the simple genetic algorithm is compared with a set of hillclimbers on a simple subset of the hyperplane-defined functions, the pothole functions.
Tracing a Faint Fingerprint of the Invisible Hand?
Venue: arXiv cs.CE 2001
Year: 2001

Any economic agent constituting the monetary economy maintains the activity of monetary flow equilibration for fulfilling the condition of monetary flow continuity in the record, except at the central bank. At the same time, monetary flow equilibration at one economic agent constantly induces at other agents in the economy further flow disequilibrium to be eliminated subsequently. We propose the rate of monetary flow disequilibration as a figure measuring the progressive movement of the economy. The rate of disequilibration was read out of both the Japanese and the United States monetary economy recorded over the last fifty years.
Coaxing Confidences from an Old Friend: Probabilistic Classifications from Transformation Rule Lists
Venue: arXiv cs.CL 2001
Year: 2001

Transformation-based learning has been successfully employed to solve many natural language processing problems. It has many positive features, but one drawback is that it does not provide estimates of class membership probabilities. In this paper, we present a novel method for obtaining class membership probabilities from a transformation-based rule list classifier. Three experiments are presented which measure the modeling accuracy and cross-entropy of the probabilistic classifier on unseen data and the degree to which the output probabilities from the classifier can be used to estimate confidences in its classification decisions. The results of these experiments show that, for the task of text chunking, the estimates produced by this technique are more informative than those generated by a state-of-the-art decision tree.
Correction of Errors in a Modality Corpus Used for Machine Translation by Using Machine-learning Method
Venue: arXiv cs.CL 2001
Year: 2001

We performed corpus correction on a modality corpus for machine translation by using such machine-learning methods as the maximum-entropy method. We thus constructed a high-quality modality corpus based on corpus correction. We compared several kinds of methods for corpus correction in our experiments and developed a good method for corpus correction.
Component Programming and Interoperability in Constraint Solver Design
Venue: arXiv cs.PL 2001
Year: 2001

Prolog was once the main host for implementing constraint solvers. It seems that it is no longer so. To be useful, constraint solvers have to be integrable into industrial applications written in imperative or object-oriented languages; to be efficient, they have to interact with other solvers. To meet these requirements, many solvers are now implemented in the form of extensible object-oriented libraries. Following Pfister and Szyperski, we argue that ``objects are not enough,'' and we propose to design solvers as component-oriented libraries. We illustrate our approach by the description of the architecture of a prototype, and we assess its strong points and weaknesses.
Dijkstra's Self-Stabilizing Algorithm in Unsupportive Environments
Venue: arXiv cs.DC 2001
Year: 2001

The first self-stabilizing algorithm [Dij73] assumed the existence of a central daemon, that activates one processor at time to change state as a function of its own state and the state of a neighbor. Subsequent research has reconsidered this algorithm without the assumption of a central daemon, and under different forms of communication, such as the model of link registers. In all of these investigations, one common feature is the atomicity of communication, whether by shared variables or read/write registers. This paper weakens the atomicity assumptions for the communication model, proposing versions of [Dij73] that tolerate various weaker forms of atomicity. First, a solution for the case of regular registers is presented. Then the case of safe registers is considered, with both negative and positive results presented. The paper also presents an implementation of [Dij73] based on registers that have probabilistically correct behavior, which requires a notion of weak stabilization.
Generating a 3D Simulation of a Car Accident from a Written Description in Natural Language: the CarSim System
Venue: arXiv cs.CL 2001
Year: 2001

This paper describes a prototype system to visualize and animate 3D scenes from car accident reports, written in French. The problem of generating such a 3D simulation can be divided into two subtasks: the linguistic analysis and the virtual scene generation. As a means of communication between these two modules, we first designed a template formalism to represent a written accident report. The CarSim system first processes written reports, gathers relevant information, and converts it into a formal description. Then, it creates the corresponding 3D scene and animates the vehicles.
Constraint Propagation in Presence of Arrays
Venue: arXiv cs.PL 2001
Year: 2001

We describe the use of array expressions as constraints, which represents a consequent generalisation of the "element" constraint. Constraint propagation for array constraints is studied theoretically, and for a set of domain reduction rules the local consistency they enforce, arc-consistency, is proved. An efficient algorithm is described that encapsulates the rule set and so inherits the capability to enforce arc-consistency from the rules.
Market-Based Reinforcement Learning in Partially Observable Worlds
Venue: arXiv cs.AI 2001
Year: 2001

Unlike traditional reinforcement learning (RL), market-based RL is in principle applicable to worlds described by partially observable Markov Decision Processes (POMDPs), where an agent needs to learn short-term memories of relevant previous events in order to execute optimal actions. Most previous work, however, has focused on reactive settings (MDPs) instead of POMDPs. Here we reimplement a recent approach to market-based RL and for the first time evaluate it in a toy POMDP setting.
Coloring k-colorable graphs using relatively small palettes
Venue: arXiv cs.DS 2001
Year: 2001

We obtain the following new coloring results: * A 3-colorable graph on $n$ vertices with maximum degree~$Δ$ can be colored, in polynomial time, using $O((Δ\logΔ)^{1/3} \cdot\log{n})$ colors. This slightly improves an $O((Δ^{{1}/{3}} \log^{1/2}Δ)\cdot\log{n})$ bound given by Karger, Motwani and Sudan. More generally, $k$-colorable graphs with maximum degree $Δ$ can be colored, in polynomial time, using $O((Δ^{1-{2}/{k}}\log^{1/k}Δ) \cdot\log{n})$ colors. * A 4-colorable graph on $n$ vertices can be colored, in polynomial time, using $\Ot(n^{7/19})$ colors. This improves an $\Ot(n^{2/5})$ bound given again by Karger, Motwani and Sudan. More generally, $k$-colorable graphs on $n$ vertices can be colored, in polynomial time, using $\Ot(n^{α_k})$ colors, where $α_5=97/207$, $α_6=43/79$, $α_7=1391/2315$, $α_8=175/271$, ... The first result is obtained by a slightly more refined probabilistic analysis of the semidefinite programming based coloring algorithm of Karger, Motwani and Sudan. The second result is obtained by combining the coloring algorithm of Karger, Motwani and Sudan, the combinatorial coloring algorithms of Blum and an extension of a technique of Alon and Kahale (which is based on the Karger, Motwani and Sudan algorithm) for finding relatively large independent sets in graphs that are guaranteed to have very large independent sets. The extension of the Alon and Kahale result may be of independent interest.
The OLAC Metadata Set and Controlled Vocabularies
Venue: arXiv cs.CL 2001
Year: 2001

As language data and associated technologies proliferate and as the language resources community rapidly expands, it has become difficult to locate and reuse existing resources. Are there any lexical resources for such-and-such a language? What tool can work with transcripts in this particular format? What is a good format to use for linguistic data of this type? Questions like these dominate many mailing lists, since web search engines are an unreliable way to find language resources. This paper describes a new digital infrastructure for language resource discovery, based on the Open Archives Initiative, and called OLAC -- the Open Language Archives Community. The OLAC Metadata Set and the associated controlled vocabularies facilitate consistent description and focussed searching. We report progress on the metadata set and controlled vocabularies, describing current issues and soliciting input from the language resources community.
Lectures on Reduce and Maple at UAM I - Mexico
Venue: arXiv cs.SC 2001
Year: 2001

These lectures give a brief introduction to the Computer Algebra systems Reduce and Maple. The aim is to provide a systematic survey of most important commands and concepts. In particular, this includes a discussion of simplification schemes and the handling of simplification and substitution rules (e.g., a Lie Algebra is implemented in Reduce by means of simplification rules). Another emphasis is on the different implementations of tensor calculi and the exterior calculus by Reduce and Maple and their application in Gravitation theory and Differential Geometry. I held the lectures at the Universidad Autonoma Metropolitana-Iztapalapa, Departamento de Fisica, Mexico, in November 1999.
Historical Dynamics of Lexical System as Random Walk Process
Venue: arXiv cs.CL 2001
Year: 2001

It is offered to consider word meanings changes in diachrony as semicontinuous random walk with reflecting and swallowing screens. The basic characteristics of word life cycle are defined. Verification of the model has been realized on the data of Russian words distribution on various age periods.
One More Revolution to Make: Free Scientific Publishing
Venue: arXiv cs.GL 2001
Year: 2001

Computer scientists are in the position to create new, free high-quality journals. So what would it take?
Logic, Individuals and Concepts
Venue: arXiv cs.LO 2001
Year: 2001

This extended abstract gives a brief outline of the connections between the descriptions and variable concepts. Thus, the notion of a concept is extended to include both the syntax and semantics features. The evaluation map in use is parameterized by a kind of computational environment, the index, giving rise to indexed concepts. The concepts are inhabited into language by the descriptions from the higher order logic. In general the idea of object-as-functor should assist the designer to outline a programming tool in conceptual shell style.
Modeling informational novelty in a conversational system with a hybrid statistical and grammar-based approach to natural language generation
Venue: arXiv cs.CL 2001
Year: 2001

We present a hybrid statistical and grammar-based system for surface natural language generation (NLG) that uses grammar rules, conditions on using those grammar rules, and corpus statistics to determine the word order. We also describe how this surface NLG module is implemented in a prototype conversational system, and how it attempts to model informational novelty by varying the word order. Using a combination of rules and statistical information, the conversational system expresses the novel information differently than the given information, based on the run-time dialog state. We also discuss our plans for evaluating the generation strategy.
On some optimization problems for star-free graphs
Venue: arXiv cs.CC 2001
Year: 2001

It is shown that in star-free graphs the maximum independent set problem, the minimum dominating set problem and the minimum independent dominating set problem are approximable up to constant factor by any maximal independent set.
A Seamless Integration of Association Rule Mining with Database Systems
Venue: arXiv cs.DB 2001
Year: 2001

The need for Knowledge and Data Discovery Management Systems (KDDMS) that support ad hoc data mining queries has been long recognized. A significant amount of research has gone into building tightly coupled systems that integrate association rule mining with database systems. In this paper, we describe a seamless integration scheme for database queries and association rule discovery using a common query optimizer for both. Query trees of expressions in an extended algebra are used for internal representation in the optimizer. The algebraic representation is flexible enough to deal with constrained association rule queries and other variations of association rule specifications. We propose modularization to simplify the query tree for complex tasks in data mining. It paves the way for making use of existing algorithms for constructing query plans in the optimization process. How the integration scheme we present will facilitate greater user control over the data mining process is also discussed. The work described in this paper forms part of a larger project for fully integrating data mining with database management.
A Blueprint for Building Serverless Applications on the Net
Venue: arXiv cs.DC 2001
Year: 2001

A peer-to-peer application architecture is proposed that has the potential to eliminate the back-end servers for hosting services on the Internet. The proposed application architecture has been modeled as a distributed system for delivering an Internet service. The service thus created, though chaotic and fraught with uncertainties, would be highly scalable and capable of achieving unprecedented levels of robustness and viability with the increase in the number of the users. The core issues relating to the architecture, such as service discovery, distributed application architecture components, and inter-application communications, have been analysed. It is shown that the communications for the coordination of various functions, among the cooperating instances of the application, may be optimised using a divide-and-conquer strategy. Finally, the areas where future work needs to be directed have been identified.
The Logic Programming Paradigm and Prolog
Venue: arXiv cs.PL 2001
Year: 2001

This is a tutorial on logic programming and Prolog appropriate for a course on programming languages for students familiar with imperative programming.