OpenRaiser/Intern-Atlas huggingface dataset:
Making Abstract Domains Condensing
Venue: arXiv cs.PL 2002
Year: 2002

In this paper we show that reversible analysis of logic languages by abstract interpretation can be performed without loss of precision by systematically refining abstract domains. The idea is to include semantic structures into abstract domains in such a way that the refined abstract domain becomes rich enough to allow approximate bottom-up and top-down semantics to agree. These domains are known as condensing abstract domains. Substantially, an abstract domain is condensing if goal-driven and goal-independent analyses agree, namely no loss of precision is introduced by approximating queries in a goal-independent analysis. We prove that condensation is an abstract domain property and that the problem of making an abstract domain condensing boils down to the problem of making the domain complete with respect to unification. In a general abstract interpretation setting we show that when concrete domains and operations give rise to quantales, i.e. models of propositional linear logic, objects in a complete refined abstract domain can be explicitly characterized by linear logic-based formulations. This is the case for abstract domains for logic program analysis approximating computed answer substitutions where unification plays the role of multiplicative conjunction in a quantale of idempotent substitutions. Condensing abstract domains can therefore be systematically derived by minimally extending any, generally non-condensing domain, by a simple domain refinement operator.
Querying Databases of Annotated Speech
Venue: arXiv cs.CL 2002
Year: 2002

Annotated speech corpora are databases consisting of signal data along with time-aligned symbolic `transcriptions'. Such databases are typically multidimensional, heterogeneous and dynamic. These properties present a number of tough challenges for representation and query. The temporal nature of the data adds an additional layer of complexity. This paper presents and harmonises two independent efforts to model annotated speech databases, one at Macquarie University and one at the University of Pennsylvania. Various query languages are described, along with illustrative applications to a variety of analytical problems. The research reported here forms a part of several ongoing projects to develop platform-independent open-source tools for creating, browsing, searching, querying and transforming linguistic databases, and to disseminate large linguistic databases over the internet.
Integrating selectional preferences in WordNet
Venue: arXiv cs.CL 2002
Year: 2002

Selectional preference learning methods have usually focused on word-to-class relations, e.g., a verb selects as its subject a given nominal class. This paper extends previous statistical models to class-to-class preferences, and presents a model that learns selectional preferences for classes of verbs, together with an algorithm to integrate the learned preferences in WordNet. The theoretical motivation is twofold: different senses of a verb may have different preferences, and classes of verbs may share preferences. On the practical side, class-to-class selectional preferences can be learned from untagged corpora (the same as word-to-class), they provide selectional preferences for less frequent word senses via inheritance, and more important, they allow for easy integration in WordNet. The model is trained on subject-verb and object-verb relationships extracted from a small corpus disambiguated with WordNet senses. Examples are provided illustrating that the theoretical motivations are well founded, and showing that the approach is feasible. Experimental results on a word sense disambiguation task are also provided.
Decision Lists for English and Basque
Venue: arXiv cs.CL 2002
Year: 2002

In this paper we describe the systems we developed for the English (lexical and all-words) and Basque tasks. They were all supervised systems based on Yarowsky's Decision Lists. We used Semcor for training in the English all-words task. We defined different feature sets for each language. For Basque, in order to extract all the information from the text, we defined features that have not been used before in the literature, using a morphological analyzer. We also implemented systems that selected automatically good features and were able to obtain a prefixed precision (85%) at the cost of coverage. The systems that used all the features were identified as BCU-ehu-dlist-all and the systems that selected some features as BCU-ehu-dlist-best.
Belief Revision and Rational Inference
Venue: arXiv cs.AI 2002
Year: 2002

The (extended) AGM postulates for belief revision seem to deal with the revision of a given theory K by an arbitrary formula, but not to constrain the revisions of two different theories by the same formula. A new postulate is proposed and compared with other similar postulates that have been proposed in the literature. The AGM revisions that satisfy this new postulate stand in one-to-one correspondence with the rational, consistency-preserving relations. This correspondence is described explicitly. Two viewpoints on iterative revisions are distinguished and discussed.
Semantic Properties for Lightweight Specification in Knowledgeable Development Environments
Venue: arXiv cs.SE 2002
Year: 2002

Semantic properties are domain-specific specification constructs used to augment an existing language with richer semantics. These properties are taken advantage of in system analysis, design, implementation, testing, and maintenance through the use of documentation and source-code transformation tools. Semantic properties are themselves specified at two levels: loosely with precise natural language, and formally within the problem domain. The refinement relationships between these specification levels, as well as between a semantic property's use and its realization in program code via tools, is specified with a new formal method for reuse called kind theory.
Memory-Based Shallow Parsing
Venue: arXiv cs.CL 2002
Year: 2002

We present memory-based learning approaches to shallow parsing and apply these to five tasks: base noun phrase identification, arbitrary base phrase recognition, clause detection, noun phrase parsing and full parsing. We use feature selection techniques and system combination methods for improving the performance of the memory-based learner. Our approach is evaluated on standard data sets and the results are compared with that of other systems. This reveals that our approach works well for base phrase identification while its application towards recognizing embedded structures leaves some room for improvement.
Trading Agents for Roaming Users
Venue: arXiv cs.CE 2002
Year: 2002

Some roaming users need services to manipulate autonomous processes. Trading agents running on agent trade servers are used as a case in point. We present a solution that provides the agent owners with means to upkeeping their desktop environment, and maintaining their agent trade server processes, via a briefcase service.
A Polynomial Description of the Rijndael Advanced Encryption Standard
Venue: arXiv cs.CR 2002
Year: 2002

The paper gives a polynomial description of the Rijndael Advanced Encryption Standard recently adopted by the National Institute of Standards and Technology. Special attention is given to the structure of the S-Box.
The prospects for mathematical logic in the twenty-first century
Venue: arXiv cs.LO 2002
Year: 2002

The four authors present their speculations about the future developments of mathematical logic in the twenty-first century. The areas of recursion theory, proof theory and logic for computer science, model theory, and set theory are discussed independently.
On Strongly Connected Digraphs with Bounded Cycle Length
Venue: arXiv cs.DS 2002
Year: 2002

The MEG (minimum equivalent graph) problem is, given a directed graph, to find a small subset of the edges that maintains all reachability relations between nodes. The problem is NP-hard. This paper gives a proof that, for graphs where each directed cycle has at most three edges, the MEG problem is equivalent to maximum bipartite matching, and therefore solvable in polynomial time. This leads to an improvement in the performance guarantee of the previously best approximation algorithm for the general problem in ``Approximating the Minimum Equivalent Digraph'' (1995).
From Alife Agents to a Kingdom of N Queens
Venue: arXiv cs.AI 2002
Year: 2002

This paper presents a new approach to solving N-queen problems, which involves a model of distributed autonomous agents with artificial life (ALife) and a method of representing N-queen constraints in an agent environment. The distributed agents locally interact with their living environment, i.e., a chessboard, and execute their reactive behaviors by applying their behavioral rules for randomized motion, least-conflict position searching, and cooperating with other agents etc. The agent-based N-queen problem solving system evolves through selection and contest according to the rule of Survival of the Fittest, in which some agents will die or be eaten if their moving strategies are less efficient than others. The experimental results have shown that this system is capable of solving large-scale N-queen problems. This paper also provides a model of ALife agents for solving general CSPs.
Performance evaluation of the GridFTP within the NorduGrid project
Venue: arXiv cs.DC 2002
Year: 2002

This report presents results of the tests measuring the performance of multi-threaded file transfers, using the GridFTP implementation of the Globus project over the NorduGrid network resources. Point to point WAN tests, carried out between the sites of Copenhagen, Lund, Oslo and Uppsala, are described. It was found that multiple threaded download via the high performance GridFTP protocol can significantly improve file transfer performance, and can serve as a reliable data
Bootstrapping Structure into Language: Alignment-Based Learning
Venue: arXiv cs.LG 2002
Year: 2002

This thesis introduces a new unsupervised learning framework, called Alignment-Based Learning, which is based on the alignment of sentences and Harris's (1951) notion of substitutability. Instances of the framework can be applied to an untagged, unstructured corpus of natural language sentences, resulting in a labelled, bracketed version of that corpus. Firstly, the framework aligns all sentences in the corpus in pairs, resulting in a partition of the sentences consisting of parts of the sentences that are equal in both sentences and parts that are unequal. Unequal parts of sentences can be seen as being substitutable for each other, since substituting one unequal part for the other results in another valid sentence. The unequal parts of the sentences are thus considered to be possible (possibly overlapping) constituents, called hypotheses. Secondly, the selection learning phase considers all hypotheses found by the alignment learning phase and selects the best of these. The hypotheses are selected based on the order in which they were found, or based on a probabilistic function. The framework can be extended with a grammar extraction phase. This extended framework is called parseABL. Instead of returning a structured version of the unstructured input corpus, like the ABL system, this system also returns a stochastic context-free or tree substitution grammar. Different instances of the framework have been tested on the English ATIS corpus, the Dutch OVIS corpus and the Wall Street Journal corpus. One of the interesting results, apart from the encouraging numerical results, is that all instances can (and do) learn recursive structures.
Monads for natural language semantics
Venue: arXiv cs.CL 2002
Year: 2002

Accounts of semantic phenomena often involve extending types of meanings and revising composition rules at the same time. The concept of monads allows many such accounts -- for intensionality, variable binding, quantification and focus -- to be stated uniformly and compositionally.
Lecture Notes on Evasiveness of Graph Properties
Venue: arXiv cs.CC 2002
Year: 2002

This report presents notes from the first eight lectures of the class Many Models of Complexity taught by Laszlo Lovasz at Princeton University in the fall of 1990. The topic is evasiveness of graph properties: given a graph property, how many edges of the graph an algorithm must check in the worst case before it knows whether the property holds.
On-Line End-to-End Congestion Control
Venue: arXiv cs.DS 2002
Year: 2002

Congestion control in the current Internet is accomplished mainly by TCP/IP. To understand the macroscopic network behavior that results from TCP/IP and similar end-to-end protocols, one main analytic technique is to show that the the protocol maximizes some global objective function of the network traffic. Here we analyze a particular end-to-end, MIMD (multiplicative-increase, multiplicative-decrease) protocol. We show that if all users of the network use the protocol, and all connections last for at least logarithmically many rounds, then the total weighted throughput (value of all packets received) is near the maximum possible. Our analysis includes round-trip-times, and (in contrast to most previous analyses) gives explicit convergence rates, allows connections to start and stop, and allows capacities to change.
Randomized Rounding without Solving the Linear Program
Venue: arXiv cs.DS 2002
Year: 2002

Randomized rounding is a standard method, based on the probabilistic method, for designing combinatorial approximation algorithms. In Raghavan's seminal paper introducing the method (1988), he writes: "The time taken to solve the linear program relaxations of the integer programs dominates the net running time theoretically (and, most likely, in practice as well)." This paper explores how this bottleneck can be avoided for randomized rounding algorithms for packing and covering problems (linear programs, or mixed integer linear programs, having no negative coefficients). The resulting algorithms are greedy algorithms, and are faster and simpler to implement than standard randomized-rounding algorithms. This approach can also be used to understand Lagrangian-relaxation algorithms for packing/covering linear programs: such algorithms can be viewed as as (derandomized) randomized-rounding schemes.
Competitive Paging Algorithms
Venue: arXiv cs.DS 2002
Year: 2002

The paging problem is that of deciding which pages to keep in a memory of k pages in order to minimize the number of page faults. This paper introduces the marking algorithm, a simple randomized on-line algorithm for the paging problem, and gives a proof that its performance guarantee (competitive ratio) is O(log k). In contrast, no deterministic on-line algorithm can have a performance guarantee better than k.
Faster Parametric Shortest Path and Minimum Balance Algorithms
Venue: arXiv cs.DS 2002
Year: 2002

The parametric shortest path problem is to find the shortest paths in graph where the edge costs are of the form w_ij+lambda where each w_ij is constant and lambda is a parameter that varies. The problem is to find shortest path trees for every possible value of lambda. The minimum-balance problem is to find a ``weighting'' of the vertices so that adjusting the edge costs by the vertex weights yields a graph in which, for every cut, the minimum weight of any edge crossing the cut in one direction equals the minimum weight of any edge crossing the cut in the other direction. The paper presents fast algorithms for both problems. The algorithms run in O(nm+n^2 log n) time. The paper also describes empirical studies of the algorithms on random graphs, suggesting that the expected time for finding a minimum-mean cycle (an important special case of both problems) is O(n log(n) + m).
Practical Strategies for Integrating a Conversation Analyst in an Iterative Design Process
Venue: arXiv cs.HC 2002
Year: 2002

We present a case study of an iterative design process that includes a conversation analyst. We discuss potential benefits of conversation analysis for design, and we describe our strategies for integrating the conversation analyst in the design process. Since the analyst on our team had no previous exposure to design or engineering, and none of the other members of our team had any experience with conversation analysis, we needed to build a foundation for our interaction. One of our key strategies was to pair the conversation analyst with a designer in a highly interactive collaboration. Our tactics have been effective on our project, leading to valuable results that we believe we could not have obtained using another method. We hope that this paper can serve as a practical guide to those interested in establishing a productive and efficient working relationship between a conversation analyst and the other members of a design team.
Connectives in Quantum and other Cumulative Logics
Venue: arXiv cs.AI 2002
Year: 2002

Cumulative logics are studied in an abstract setting, i.e., without connectives, very much in the spirit of Makinson's early work. A powerful representation theorem characterizes those logics by choice functions that satisfy a weakening of Sen's property alpha, in the spirit of the author's "Nonmonotonic Logics and Semantics" (JLC). The representation results obtained are surprisingly smooth: in the completeness part the choice function may be defined on any set of worlds, not only definable sets and no definability-preservation property is required in the soundness part. For abstract cumulative logics, proper conjunction and negation may be defined. Contrary to the situation studied in "Nonmonotonic Logics and Semantics" no proper disjunction seems to be definable in general. The cumulative relations of KLM that satisfy some weakening of the consistency preservation property all define cumulative logics with a proper negation. Quantum Logics, as defined by Engesser and Gabbay are such cumulative logics but the negation defined by orthogonal complement does not provide a proper negation.
Neural Net Model for Featured Word Extraction
Venue: arXiv cs.NE 2002
Year: 2002

Search engines perform the task of retrieving information related to the user-supplied query words. This task has two parts; one is finding "featured words" which describe an article best and the other is finding a match among these words to user-defined search terms. There are two main independent approaches to achieve this task. The first one, using the concepts of semantics, has been implemented partially. For more details see another paper of Marko et al., 2002. The second approach is reported in this paper. It is a theoretical model based on using Neural Network (NN). Instead of using keywords or reading from the first few lines from papers/articles, the present model gives emphasis on extracting "featured words" from an article. Obviously we propose to exclude prepositions, articles and so on, that is, English words like "of, the, are, so, therefore, " etc. from such a list. A neural model is taken with its nodes pre-assigned energies. Whenever a match is found with featured words and userdefined search words, the node is fired and jumps to a higher energy. This firing continues until the model attains a steady energy level and total energy is now calculated. Clearly, higher match will generate higher energy; so on the basis of total energy, a ranking is done to the article indicating degree of relevance to the user's interest. Another important feature of the proposed model is incorporating a semantic module to refine the search words; like finding association among search words, etc. In this manner, information retrieval can be improved markedly.
Simultaneous Embedding of a Planar Graph and Its Dual on the Grid
Venue: arXiv cs.CG 2002
Year: 2002

Traditional representations of graphs and their duals suggest the requirement that the dual vertices be placed inside their corresponding primal faces, and the edges of the dual graph cross only their corresponding primal edges. We consider the problem of simultaneously embedding a planar graph and its dual into a small integer grid such that the edges are drawn as straight-line segments and the only crossings are between primal-dual pairs of edges. We provide a linear-time algorithm that simultaneously embeds a 3-connected planar graph and its dual on a (2n-2) by (2n-2) integer grid, where n is the total number of vertices in the graph and its dual. Furthermore our embedding algorithm satisfies the two natural requirements mentioned above.
Multidimensional Network Monitoring for Intrusion Detection
Venue: arXiv cs.CR 2002
Year: 2002

An approach for real-time network monitoring in terms of numerical time-dependant functions of protocol parameters is suggested. Applying complex systems theory for information f{l}ow analysis of networks, the information traffic is described as a trajectory in multi-dimensional parameter-time space with about 10-12 dimensions. The network traffic description is synthesized by applying methods of theoretical physics and complex systems theory, to provide a robust approach for network monitoring that detects known intrusions, and supports developing real systems for detection of unknown intrusions. The methods of data analysis and pattern recognition presented are the basis of a technology study for an automatic intrusion detection system that detects the attack in the reconnaissance stage.
Hidden Markov model segmentation of hydrological and enviromental time series
Venue: arXiv cs.CE 2002
Year: 2002

Motivated by Hubert's segmentation procedure we discuss the application of hidden Markov models (HMM) to the segmentation of hydrological and enviromental time series. We use a HMM algorithm which segments time series of several hundred terms in a few seconds and is computationally feasible for even longer time series. The segmentation algorithm computes the Maximum Likelihood segmentation by use of an expectation / maximization iteration. We rigorously prove algorithm convergence and use numerical experiments, involving temperature and river discharge time series, to show that the algorithm usually converges to the globally optimal segmentation. The relation of the proposed algorithm to Hubert's segmentation procedure is also discussed.
MPICH-G2: A Grid-Enabled Implementation of the Message Passing Interface
Venue: arXiv cs.DC 2002
Year: 2002

Application development for distributed computing "Grids" can benefit from tools that variously hide or enable application-level management of critical aspects of the heterogeneous environment. As part of an investigation of these issues, we have developed MPICH-G2, a Grid-enabled implementation of the Message Passing Interface (MPI) that allows a user to run MPI programs across multiple computers, at the same or different sites, using the same commands that would be used on a parallel computer. This library extends the Argonne MPICH implementation of MPI to use services provided by the Globus Toolkit for authentication, authorization, resource allocation, executable staging, and I/O, as well as for process creation, monitoring, and control. Various performance-critical operations, including startup and collective operations, are configured to exploit network topology information. The library also exploits MPI constructs for performance management; for example, the MPI communicator construct is used for application-level discovery of, and adaptation to, both network topology and network quality-of-service mechanisms. We describe the MPICH-G2 design and implementation, present performance results, and review application experiences, including record-setting distributed simulations.