title: On the predictability of Rainfall in Kerala- An application of ABF Neural Network

abstract: Rainfall in Kerala State, the southern part of Indian Peninsula in particular is caused by the two monsoons and the two cyclones every year. In general, climate and rainfall are highly nonlinear phenomena in nature giving rise to what is known as the `butterfly effect'. We however attempt to train an ABF neural network on the time series rainfall data and show for the first time that in spite of the fluctuations resulting from the nonlinearity in the system, the trends in the rainfall pattern in this corner of the globe have remained unaffected over the past 87 years from 1893 to 1980. We also successfully filter out the chaotic part of the system and illustrate that its effects are marginal over long term predictions.


title: Non-convex cost functionals in boosting algorithms and methods for panel selection

abstract: In this document we propose a new improvement for boosting techniques as proposed in Friedman '99 by the use of non-convex cost functional. The idea is to introduce a correlation term to better deal with forecasting of additive time series. The problem is discussed in a theoretical way to prove the existence of minimizing sequence, and in a numerical way to propose a new "ArgMin" algorithm. The model has been used to perform the touristic presence forecast for the winter season 1999/2000 in Trentino (italian Alps).


title: A Scientific Data Management System for Irregular Applications

abstract: 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.


title: Components and Interfaces of a Process Management System for Parallel Programs

abstract: Parallel jobs are different from sequential jobs and require a different type of process management. We present here a process management system for parallel programs such as those written using MPI. A primary goal of the system, which we call MPD (for multipurpose daemon), is to be scalable. By this we mean that startup of interactive parallel jobs comprising thousands of processes is quick, that signals can be quickly delivered to processes, and that stdin, stdout, and stderr are managed intuitively. Our primary target is parallel machines made up of clusters of SMPs, but the system is also useful in more tightly integrated environments. We describe how MPD enables much faster startup and better runtime management of parallel jobs. We show how close control of stdio can support the easy implementation of a number of convenient system utilities, even a parallel debugger. We describe a simple but general interface that can be used to separate any process manager from a parallel library, which we use to keep MPD separate from MPICH.


title: An effective Procedure for Speeding up Algorithms

abstract: The provably asymptotically fastest algorithm within a factor of 5 for formally described problems will be constructed. The main idea is to enumerate all programs provably equivalent to the original problem by enumerating all proofs. The algorithm could be interpreted as a generalization and improvement of Levin search, which is, within a multiplicative constant, the fastest algorithm for inverting functions. Blum's speed-up theorem is avoided by taking into account only programs for which a correctness proof exists. Furthermore, it is shown that the fastest program that computes a certain function is also one of the shortest programs provably computing this function. To quantify this statement, the definition of Kolmogorov complexity is extended, and two new natural measures for the complexity of a function are defined.


title: Easy and Hard Constraint Ranking in OT: Algorithms and Complexity

abstract: We consider the problem of ranking a set of OT constraints in a manner consistent with data. We speed up Tesar and Smolensky's RCD algorithm to be linear on the number of constraints. This finds a ranking so each attested form x_i beats or ties a particular competitor y_i. We also generalize RCD so each x_i beats or ties all possible competitors. Alas, this more realistic version of learning has no polynomial algorithm unless P=NP! Indeed, not even generation does. So one cannot improve qualitatively upon brute force: Merely checking that a single (given) ranking is consistent with given forms is coNP-complete if the surface forms are fully observed and Delta_2^p-complete if not. Indeed, OT generation is OptP-complete. As for ranking, determining whether any consistent ranking exists is coNP-hard (but in Delta_2^p) if the forms are fully observed, and Sigma_2^p-complete if not. Finally, we show that generation and ranking are easier in derivational theories: in P, and NP-complete.


title: Multi-Syllable Phonotactic Modelling

abstract: This paper describes a novel approach to constructing phonotactic models. The underlying theoretical approach to phonological description is the multisyllable approach in which multiple syllable classes are defined that reflect phonotactically idiosyncratic syllable subcategories. A new finite-state formalism, OFS Modelling, is used as a tool for encoding, automatically constructing and generalising phonotactic descriptions. Language-independent prototype models are constructed which are instantiated on the basis of data sets of phonological strings, and generalised with a clustering algorithm. The resulting approach enables the automatic construction of phonotactic models that encode arbitrarily close approximations of a language's set of attested phonological forms. The approach is applied to the construction of multi-syllable word-level phonotactic models for German, English and Dutch.


title: Taking Primitive Optimality Theory Beyond the Finite State

abstract: 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.


title: Finite-State Phonology: Proceedings of the 5th Workshop of the ACL Special Interest Group in Computational Phonology (SIGPHON)

abstract: Home page of the workshop proceedings, with pointers to the individually archived papers. Includes front matter from the printed version of the proceedings.


title: Factored Notation for Interval I/O

abstract: This note addresses the input and output of intervals in the sense of interval arithmetic and interval constraints. The most obvious, and so far most widely used notation, for intervals has drawbacks that we remedy with a new notation that we propose to call factored notation. It is more compact and allows one to find a good trade-off between interval width and ease of reading. We describe how such a trade-off can be based on the information yield (in the sense of information theory) of the last decimal shown.


title: P-Immune Sets with Holes Lack Self-Reducibility Properties

abstract: No P-immune set having exponential gaps is positive-Turing self-reducible.


title: An Effective Fixpoint Semantics for Linear Logic Programs

abstract: In this paper we investigate the theoretical foundation of a new bottom-up semantics for linear logic programs, and more precisely for the fragment of LinLog that consists of the language LO enriched with the constant 1. We use constraints to symbolically and finitely represent possibly infinite collections of provable goals. We define a fixpoint semantics based on a new operator in the style of Tp working over constraints. An application of the fixpoint operator can be computed algorithmically. As sufficient conditions for termination, we show that the fixpoint computation is guaranteed to converge for propositional LO. To our knowledge, this is the first attempt to define an effective fixpoint semantics for linear logic programs. As an application of our framework, we also present a formal investigation of the relations between LO and Disjunctive Logic Programming. Using an approach based on abstract interpretation, we show that DLP fixpoint semantics can be viewed as an abstraction of our semantics for LO. We prove that the resulting abstraction is correct and complete for an interesting class of LO programs encoding Petri Nets.


title: Mathematical Model of Word Length on the Basis of the Cebanov-Fucks Distribution with Uniform Parameter Distribution

abstract: The data on 13 typologically different languages have been processed using a two-parameter word length model, based on 1-displaced uniform Poisson distribution. Statistical dependencies of the 2nd parameter on the 1st one are revealed for the German texts and genre of letters.


title: Gene Expression Programming: a New Adaptive Algorithm for Solving Problems

abstract: Gene expression programming, a genotype/phenotype genetic algorithm (linear and ramified), is presented here for the first time as a new technique for the creation of computer programs. Gene expression programming uses character linear chromosomes composed of genes structurally organized in a head and a tail. The chromosomes function as a genome and are subjected to modification by means of mutation, transposition, root transposition, gene transposition, gene recombination, and one- and two-point recombination. The chromosomes encode expression trees which are the object of selection. The creation of these separate entities (genome and expression tree) with distinct functions allows the algorithm to perform with high efficiency that greatly surpasses existing adaptive techniques. The suite of problems chosen to illustrate the power and versatility of gene expression programming includes symbolic regression, sequence induction with and without constant creation, block stacking, cellular automata rules for the density-classification problem, and two problems of boolean concept learning: the 11-multiplexer and the GP rule problem.


title: Communities of Practice: Going Virtual

abstract: With the current trends towards downsizing, outsourcing and globalisation, modern organisations are reducing the numbers of people they employ. In addition, organisations now have to cope with the increasing internationalisation of business forcing collaboration and knowledge sharing across time and distance simultaneously. There is a need for new ways of thinking about how knowledge is shared in distributed groups. In this paper we explore a relatively new approach to knowledge sharing using Lave and Wenger's (1991) theory of Communities of Practice (CoPs). We investigate whether CoPs might translate to a geographically distributed international environment through a case study that explores the functioning of a CoP across national boundaries.


title: Computer based Information Systems and Managers' Work

abstract: This paper identifies three categories of model: the Technology Impact Model; the Social Impact Model and the Integrationist Model, which imply different views of the "impact" of Information Technology on work organisation. These models are used to structure data from case studies conducted by the authors to explore the implications of the use of computer-based information systems for managers' work. The paper argues that the "impact" of information systems is not a single stable and predictable outcome but a non-linear ongoing process that changes and evolves over time. It also argues that the actions of individuals and groups within an organisation are not wholly determined by outside forces: people can and do react to, and shape, systems in different ways. In this sense, the "impact" of computer-based information systems on managers' work reflects decisions made by managers themselves about how the technology is used.


title: Soundness, Idempotence and Commutativity of Set-Sharing

abstract: It is important that practical data-flow analyzers are backed by reliably proven theoretical results. Abstract interpretation provides a sound mathematical framework and necessary generic properties for an abstract domain to be well-defined and sound with respect to the concrete semantics. In logic programming, the abstract domain Sharing is a standard choice for sharing analysis for both practical work and further theoretical study. In spite of this, we found that there were no satisfactory proofs for the key properties of commutativity and idempotence that are essential for Sharing to be well-defined and that published statements of the soundness of Sharing assume the occurs-check. This paper provides a generalization of the abstraction function for Sharing that can be applied to any language, with or without the occurs-check. Results for soundness, idempotence and commutativity for abstract unification using this abstraction function are proven.


title: Construction of an algorithm in parallel for the Fast Fourier Transform

abstract: 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.


title: Quantitative Neural Network Model of the Tip-of-the-Tongue Phenomenon Based on Synthesized Memory-Psycholinguistic-Metacognitive Approach

abstract: A new three-stage computer artificial neural network model of the tip-of-the-tongue phenomenon is proposed. Each word's node is build from some interconnected learned auto-associative two-layer neural networks each of which represents separate word's semantic, lexical, or phonological components. The model synthesizes memory, psycholinguistic, and metamemory approaches, bridges speech errors and naming chronometry research traditions, and can explain quantitatively many tip-of-the-tongue effects.


title: Learning Policies with External Memory

abstract: In order for an agent to perform well in partially observable domains, it is usually necessary for actions to depend on the history of observations. In this paper, we explore a {\it stigmergic} approach, in which the agent's actions include the ability to set and clear bits in an external memory, and the external memory is included as part of the input to the agent. In this case, we need to learn a reactive policy in a highly non-Markovian domain. We explore two algorithms: SARSA(\lambda), which has had empirical success in partially observable domains, and VAPS, a new algorithm due to Baird and Moore, with convergence guarantees in partially observable domains. We compare the performance of these two algorithms on benchmark problems.


title: Rapid Application Evolution and Integration Through Document Metamorphosis

abstract: The Harland document management system implements a data model in which document (object) structure can be altered by mixin-style multiple inheritance at any time. This kind of structural fluidity has long been supported by knowledge-base management systems, but its use has primarily been in support of reasoning and inference. In this paper, we report our experiences building and supporting several non-trivial applications on top of this data model. Based on these experiences, we argue that structural fluidity is convenient for data-intensive applications other than knowledge-base management. Specifically, we suggest that this flexible data model is a natural fit for the decoupled programming methodology that arises naturally when using enterprise component frameworks.


title: Source-Filter Decomposition of Harmonic Sounds

abstract: 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.


title: Flexible Software Framework for Modal Synthesis

abstract: Modal synthesis is an important area of physical modeling whose exploration in the past has been held back by a large number of control parameters, the scarcity of general-purpose design tools and the difficulty of obtaining the computational power required for real-time synthesis. This paper presents an overview of a flexible software framework facilitating the design and control of instruments based on modal synthesis. The framework is designed as a hierarchy of polymorphic synthesis objects, representing modal structures of various complexity. As a method of generalizing all interactions among the elements of a modal system, an abstract notion of {\it energy} is introduced, and a set of energy transfer functions is provided. Such abstraction leads to a design where the dynamics of interactions can be largely separated from the specifics of particular modal structures, yielding an easily configurable and expandable system. A real-time version of the framework has been implemented as a set of C++ classes along with an integrating shell and a GUI, and is currently being used to design and play modal instruments, as well as to survey fundamental properties of various modal algorithms.


title: Two-parameter Model of Word Length "Language - Genre"

abstract: 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.


title: The Limits of Horn Logic Programs

abstract: Given a sequence $\{\Pi_n\}$ of Horn logic programs, the limit $\Pi$ of $\{\Pi_n\}$ is the set of the clauses such that every clause in $\Pi$ belongs to almost every $\Pi_n$ and every clause in infinitely many $\Pi_n$'s belongs to $\Pi$ also. The limit program $\Pi$ is still Horn but may be infinite. In this paper, we consider if the least Herbrand model of the limit of a given Horn logic program sequence $\{\Pi_n\}$ equals the limit of the least Herbrand models of each logic program $\Pi_n$. It is proved that this property is not true in general but holds if Horn logic programs satisfy an assumption which can be syntactically checked and be satisfied by a class of Horn logic programs. Thus, under this assumption we can approach the least Herbrand model of the limit $\Pi$ by the sequence of the least Herbrand models of each finite program $\Pi_n$. We also prove that if a finite Horn logic program satisfies this assumption, then the least Herbrand model of this program is recursive. Finally, by use of the concept of stability from dynamical systems, we prove that this assumption is exactly a sufficient condition to guarantee the stability of fixed points for Horn logic programs.


title: Toward an architecture for quantum programming

abstract: It is becoming increasingly clear that, if a useful device for quantum computation will ever be built, it will be embodied by a classical computing machine with control over a truly quantum subsystem, this apparatus performing a mixture of classical and quantum computation. This paper investigates a possible approach to the problem of programming such machines: a template high level quantum language is presented which complements a generic general purpose classical language with a set of quantum primitives. The underlying scheme involves a run-time environment which calculates the byte-code for the quantum operations and pipes it to a quantum device controller or to a simulator. This language can compactly express existing quantum algorithms and reduce them to sequences of elementary operations; it also easily lends itself to automatic, hardware independent, circuit simplification. A publicly available preliminary implementation of the proposed ideas has been realized using the C++ language.


title: Magical Number Seven Plus or Minus Two: Syntactic Structure Recognition in Japanese and English Sentences

abstract: George A. Miller said that human beings have only seven chunks in short-term memory, plus or minus two. We counted the number of bunsetsus (phrases) whose modifiees are undetermined in each step of an analysis of the dependency structure of Japanese sentences, and which therefore must be stored in short-term memory. The number was roughly less than nine, the upper bound of seven plus or minus two. We also obtained similar results with English sentences under the assumption that human beings recognize a series of words, such as a noun phrase (NP), as a unit. This indicates that if we assume that the human cognitive units in Japanese and English are bunsetsu and NP respectively, analysis will support Miller's $7 \pm 2$ theory.


title: A Machine-Learning Approach to Estimating the Referential Properties of Japanese Noun Phrases

abstract: The referential properties of noun phrases in the Japanese language, which has no articles, are useful for article generation in Japanese-English machine translation and for anaphora resolution in Japanese noun phrases. They are generally classified as generic noun phrases, definite noun phrases, and indefinite noun phrases. In the previous work, referential properties were estimated by developing rules that used clue words. If two or more rules were in conflict with each other, the category having the maximum total score given by the rules was selected as the desired category. The score given by each rule was established by hand, so the manpower cost was high. In this work, we automatically adjusted these scores by using a machine-learning method and succeeded in reducing the amount of manpower needed to adjust these scores.


title: Meaning Sort - Three examples: dictionary construction, tagged corpus construction, and information presentation system

abstract: It is often useful to sort words into an order that reflects relations among their meanings as obtained by using a thesaurus. In this paper, we introduce a method of arranging words semantically by using several types of `{\sf is-a}' thesauri and a multi-dimensional thesaurus. We also describe three major applications where a meaning sort is useful and show the effectiveness of a meaning sort. Since there is no doubt that a word list in meaning-order is easier to use than a word list in some random order, a meaning sort, which can easily produce a word list in meaning-order, must be useful and effective.


title: CRL at Ntcir2

abstract: We have developed systems of two types for NTCIR2. One is an enhenced version of the system we developed for NTCIR1 and IREX. It submitted retrieval results for JJ and CC tasks. A variety of parameters were tried with the system. It used such characteristics of newspapers as locational information in the CC tasks. The system got good results for both of the tasks. The other system is a portable system which avoids free parameters as much as possible. The system submitted retrieval results for JJ, JE, EE, EJ, and CC tasks. The system automatically determined the number of top documents and the weight of the original query used in automatic-feedback retrieval. It also determined relevant terms quite robustly. For EJ and JE tasks, it used document expansion to augment the initial queries. It achieved good results, except on the CC tasks.


title: Faster-than-light effects and negative group delays in optics and electronics, and their applications

abstract: Recent manifestations of apparently faster-than-light effects confirmed our predictions that the group velocity in transparent optical media can exceed c. Special relativity is not violated by these phenomena. Moreover, in the electronic domain, the causality principle does not forbid negative group delays of analytic signals in electronic circuits, in which the peak of an output pulse leaves the exit port of a circuit before the peak of the input pulse enters the input port. Furthermore, pulse distortion for these superluminal analytic signals can be negligible in both the optical and electronic domains. Here we suggest an extension of these ideas to the microelectronic domain. The underlying principle is that negative feedback can be used to produce negative group delays. Such negative group delays can be used to cancel out the positive group delays due to transistor latency (e.g., the finite RC rise time of MOSFETS caused by their intrinsic gate capacitance), as well as the propagation delays due to the interconnects between transistors. Using this principle, it is possible to speed up computer systems.


title: Fitness Uniform Selection to Preserve Genetic Diversity

abstract: In evolutionary algorithms, the fitness of a population increases with time by mutating and recombining individuals and by a biased selection of more fit individuals. The right selection pressure is critical in ensuring sufficient optimization progress on the one hand and in preserving genetic diversity to be able to escape from local optima on the other. We propose a new selection scheme, which is uniform in the fitness values. It generates selection pressure towards sparsely populated fitness regions, not necessarily towards higher fitness, as is the case for all other selection schemes. We show that the new selection scheme can be much more effective than standard selection schemes.


title: Search in Power-Law Networks

abstract: Many communication and social networks have power-law link distributions, containing a few nodes which have a very high degree and many with low degree. The high connectivity nodes play the important role of hubs in communication and networking, a fact which can be exploited when designing efficient search algorithms. We introduce a number of local search strategies which utilize high degree nodes in power-law graphs and which have costs which scale sub-linearly with the size of the graph. We also demonstrate the utility of these strategies on the Gnutella peer-to-peer network.

categories: cs.NI cond-mat.dis-nn cond-mat.stat-mech cs.PF


title: Nice point sets can have nasty Delaunay triangulations

abstract: We consider the complexity of Delaunay triangulations of sets of points in R^3 under certain practical geometric constraints. The spread of a set of points is the ratio between the longest and shortest pairwise distances. We show that in the worst case, the Delaunay triangulation of n points in R^3 with spread D has complexity Omega(min{D^3, nD, n^2}) and O(min{D^4, n^2}). For the case D = Theta(sqrt{n}), our lower bound construction consists of a uniform sample of a smooth convex surface with bounded curvature. We also construct a family of smooth connected surfaces such that the Delaunay triangulation of any good point sample has near-quadratic complexity.


title: The Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE-Complete

abstract: It is known that the existential theory of equations in free groups is decidable. This is a famous result of Makanin. On the other hand it has been shown that the scheme of his algorithm is not primitive recursive. In this paper we present an algorithm that works in polynomial space, even in the more general setting where each variable has a rational constraint, that is, the solution has to respect a specification given by a regular word language. Our main result states that the existential theory of equations in free groups with rational constraints is PSPACE-complete. We obtain this result as a corollary of the corresponding statement about free monoids with involution.


title: On the NP-completeness of Finding an Optimal Strategy in Games with Common Payoffs

abstract: Consider a very simple class of (finite) games: after an initial move by nature, each player makes one move. Moreover, the players have common interests: at each node, all the players get the same payoff. We show that the problem of determining whether there exists a joint strategy where each player has an expected payoff of at least r is NP-complete as a function of the number of nodes in the extensive-form representation of the game.


title: Belief Revision: A Critique

abstract: We examine carefully the rationale underlying the approaches to belief change taken in the literature, and highlight what we view as methodological problems. We argue that to study belief change carefully, we must be quite explicit about the ``ontology'' or scenario underlying the belief change process. This is something that has been missing in previous work, with its focus on postulates. Our analysis shows that we must pay particular attention to two issues that have often been taken for granted: The first is how we model the agent's epistemic state. (Do we use a set of beliefs, or a richer structure, such as an ordering on worlds? And if we use a set of beliefs, in what language are these beliefs are expressed?) We show that even postulates that have been called ``beyond controversy'' are unreasonable when the agent's beliefs include beliefs about her own epistemic state as well as the external world. The second is the status of observations. (Are observations known to be true, or just believed? In the latter case, how firm is the belief?) Issues regarding the status of observations arise particularly when we consider iterated belief revision, and we must confront the possibility of revising by p and then by not-p.


title: Quantum Clock Synchronization with one qubit

abstract: The clock synchronization problem is to determine the time difference T between two spatially separated parties. We improve on I. Chuang's quantum clock synchronization algorithm and show that it is possible to obtain T to n bits of accuracy while communicating only one qubit in one direction and using an O(2^n) frequency range. We also prove a quantum lower bound of \Omega(2^n) for the product of the transmitted qubits and the range of frequencies, thus showing that our algorithm is optimal.


title: Secure, Efficient Data Transport and Replica Management for High-Performance Data-Intensive Computing

abstract: An emerging class of data-intensive applications involve the geographically dispersed extraction of complex scientific information from very large collections of measured or computed data. Such applications arise, for example, in experimental physics, where the data in question is generated by accelerators, and in simulation science, where the data is generated by supercomputers. So-called Data Grids provide essential infrastructure for such applications, much as the Internet provides essential services for applications such as e-mail and the Web. We describe here two services that we believe are fundamental to any Data Grid: reliable, high-speed transporet and replica management. Our high-speed transport service, GridFTP, extends the popular FTP protocol with new features required for Data Grid applciations, such as striping and partial file access. Our replica management service integrates a replica catalog with GridFTP transfers to provide for the creation, registration, location, and management of dataset replicas. We present the design of both services and also preliminary performance results. Our implementations exploit security and other services provided by the Globus Toolkit.


title: A Dualheap Selection Algorithm - A Call for Analysis

abstract: An algorithm is presented that efficiently solves the selection problem: finding the k-th smallest member of a set. Relevant to a divide-and-conquer strategy, the algorithm also partitions a set into small and large valued subsets. Applied recursively, this partitioning results in a sorted set. The algorithm's applicability is therefore much broader than just the selection problem. The presented algorithm is based upon R.W. Floyd's 1964 algorithm that constructs a heap from the bottom-up. Empirically, the presented algorithm's performance appears competitive with the popular quickselect algorithm, a variant of C.A.R. Hoare's 1962 quicksort algorithm. Furthermore, constructing a heap from the bottom-up is an inherently parallel process (processors can work independently and simultaneously on subheap construction), suggesting a performance advantage with parallel implementations. Given the presented algorithm's broad applicability, simplicity, serial performance, and parallel nature, further study is warranted. Specifically, worst-case analysis is an important but still unsolved problem.


title: Notes on computing peaks in k-levels and parametric spanning trees

abstract: 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 $\tau$ largest peaks in $O(n \log ^2 n) + \tilde{O}((\tau 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})$


title: The Anatomy of the Grid - Enabling Scalable Virtual Organizations

abstract: "Grid" computing has emerged as an important new field, distinguished from conventional distributed computing by its focus on large-scale resource sharing, innovative applications, and, in some cases, high-performance orientation. In this article, we define this new field. First, we review the "Grid problem," which we define as flexible, secure, coordinated resource sharing among dynamic collections of individuals, institutions, and resources-what we refer to as virtual organizations. In such settings, we encounter unique authentication, authorization, resource access, resource discovery, and other challenges. It is this class of problem that is addressed by Grid technologies. Next, we present an extensible and open Grid architecture, in which protocols, services, application programming interfaces, and software development kits are categorized according to their roles in enabling resource sharing. We describe requirements that we believe any such mechanisms must satisfy, and we discuss the central role played by the intergrid protocols that enable interoperability among different Grid systems. Finally, we discuss how Grid technologies relate to other contemporary technologies, including enterprise integration, application service provider, storage service provider, and peer-to-peer computing. We maintain that Grid concepts and technologies complement and have much to contribute to these other approaches.


title: A Decision Tree of Bigrams is an Accurate Predictor of Word Sense

abstract: This paper presents a corpus-based approach to word sense disambiguation where a decision tree assigns a sense to an ambiguous word based on the bigrams that occur nearby. This approach is evaluated using the sense-tagged corpora from the 1998 SENSEVAL word sense disambiguation exercise. It is more accurate than the average results reported for 30 of 36 words, and is more accurate than the best results for 19 of 36 words.


title: Mantaining Dynamic Matrices for Fully Dynamic Transitive Closure

abstract: In this paper we introduce a general framework for casting fully dynamic transitive closure into the problem of reevaluating polynomials over matrices. With this technique, we improve the best known bounds for fully dynamic transitive closure. In particular, we devise a deterministic algorithm for general directed graphs that achieves $O(n^2)$ amortized time for updates, while preserving unit worst-case cost for queries. In case of deletions only, our algorithm performs updates faster in O(n) amortized time. Our matrix-based approach yields an algorithm for directed acyclic graphs that breaks through the $O(n^2)$ barrier on the single-operation complexity of fully dynamic transitive closure. We can answer queries in $O(n^\epsilon)$ time and perform updates in $O(n^{\omega(1,\epsilon,1)-\epsilon}+n^{1+\epsilon})$ time, for any $\epsilon\in[0,1]$, where $\omega(1,\epsilon,1)$ is the exponent of the multiplication of an $n\times n^{\epsilon}$ matrix by an $n^{\epsilon}\times n$ matrix. The current best bounds on $\omega(1,\epsilon,1)$ imply an $O(n^{0.58})$ query time and an $O(n^{1.58})$ update time. Our subquadratic algorithm is randomized, and has one-side error.


title: Replica Selection in the Globus Data Grid

abstract: The Globus Data Grid architecture provides a scalable infrastructure for the management of storage resources and data that are distributed across Grid environments. These services are designed to support a variety of scientific applications, ranging from high-energy physics to computational genomics, that require access to large amounts of data (terabytes or even petabytes) with varied quality of service requirements. By layering on a set of core services, such as data transport, security, and replica cataloging, one can construct various higher-level services. In this paper, we discuss the design and implementation of a high-level replica selection service that uses information regarding replica location and user preferences to guide selection from among storage replica alternatives. We first present a basic replica selection service design, then show how dynamic information collected using Globus information service capabilities concerning storage system properties can help improve and optimize the selection process. We demonstrate the use of Condor's ClassAds resource description and matchmaking mechanism as an efficient tool for representing and matching storage resource capabilities and policies against application requirements.


title: Chain Programs for Writing Deterministic Metainterpreters

abstract: Many metainterpreters found in the logic programming literature are nondeterministic in the sense that the selection of program clauses is not determined. Examples are the familiar "demo" and "vanilla" metainterpreters. For some applications this nondeterminism is convenient. In some cases, however, a deterministic metainterpreter, having an explicit selection of clauses, is needed. Such cases include (1) conversion of OR parallelism into AND parallelism for "committed-choice" processors, (2) logic-based, imperative-language implementation of search strategies, and (3) simulation of bounded-resource reasoning. Deterministic metainterpreters are difficult to write because the programmer must be concerned about the set of unifiers of the children of a node in the derivation tree. We argue that it is both possible and advantageous to write these metainterpreters by reasoning in terms of object programs converted into a syntactically restricted form that we call "chain" form, where we can forget about unification, except for unit clauses. We give two transformations converting logic programs into chain form, one for "moded" programs (implicit in two existing exhaustive-traversal methods for committed-choice execution), and one for arbitrary definite programs. As illustrations of our approach we show examples of the three applications mentioned above.


title: Secure Counting: counting members of a subset without revealing their identities

abstract: Suppose there is a group of N people some of whom possess a specific property. For example, their wealth is above or below a threshold, they voted for a particular candidate, they have a certain disease, etc. The group wants to find out how many of its members posses the property -- without revealing the identities. Unless of course it turns out that all members do or do not have the attribute of interest. However, in all other cases the counting algorithm should guarantee that nobody can find out if a particular individual possesses the property unless all the other N-1 members of the group collude. The present article describes a method to solve the confidential counting problem with only 3*N-2 pairwise communications, or 2*N broadcasts (the last N-1 pairwise communications are merely to announce the result). The counting algorithm does not require any trusted third parties. All communications between parties involved can be conducted in public without compromising the security of counting.


title: Bootstrapping Structure using Similarity

abstract: In this paper a new similarity-based learning algorithm, inspired by string edit-distance (Wagner and Fischer, 1974), is applied to the problem of bootstrapping structure from scratch. The algorithm takes a corpus of unannotated sentences as input and returns a corpus of bracketed sentences. The method works on pairs of unstructured sentences or sentences partially bracketed by the algorithm that have one or more words in common. It finds parts of sentences that are interchangeable (i.e. the parts of the sentences that are different in both sentences). These parts are taken as possible constituents of the same type. While this corresponds to the basic bootstrapping step of the algorithm, further structure may be learned from comparison with other (similar) sentences. We used this method for bootstrapping structure from the flat sentences of the Penn Treebank ATIS corpus, and compared the resulting structured sentences to the structured sentences in the ATIS corpus. Similarly, the algorithm was tested on the OVIS corpus. We obtained 86.04 % non-crossing brackets precision on the ATIS corpus and 89.39 % non-crossing brackets precision on the OVIS corpus.


title: ABL: Alignment-Based Learning

abstract: This paper introduces a new type of grammar learning algorithm, inspired by string edit distance (Wagner and Fischer, 1974). The algorithm takes a corpus of flat sentences as input and returns a corpus of labelled, bracketed sentences. The method works on pairs of unstructured sentences that have one or more words in common. When two sentences are divided into parts that are the same in both sentences and parts that are different, this information is used to find parts that are interchangeable. These parts are taken as possible constituents of the same type. After this alignment learning step, the selection learning step selects the most probable constituents from all possible constituents. This method was used to bootstrap structure on the ATIS corpus (Marcus et al., 1993) and on the OVIS (Openbaar Vervoer Informatie Systeem (OVIS) stands for Public Transport Information System.) corpus (Bonnema et al., 1997). While the results are encouraging (we obtained up to 89.25 % non-crossing brackets precision), this paper will point out some of the shortcomings of our approach and will suggest possible solutions.


title: Bootstrapping Syntax and Recursion using Alignment-Based Learning

abstract: This paper introduces a new type of unsupervised learning algorithm, based on the alignment of sentences and Harris's (1951) notion of interchangeability. The algorithm is applied to an untagged, unstructured corpus of natural language sentences, resulting in a labelled, bracketed version of the corpus. Firstly, the algorithm aligns all sentences in the corpus in pairs, resulting in a partition of the sentences consisting of parts of the sentences that are similar in both sentences and parts that are dissimilar. This information is used to find (possibly overlapping) constituents. Next, the algorithm selects (non-overlapping) constituents. Several instances of the algorithm are applied to the ATIS corpus (Marcus et al., 1993) and the OVIS (Openbaar Vervoer Informatie Systeem (OVIS) stands for Public Transport Information System.) corpus (Bonnema et al., 1997). Apart from the promising numerical results, the most striking result is that even the simplest algorithm based on alignment learns recursion.


title: Event Indexing Systems for Efficient Selection and Analysis of HERA Data

abstract: 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.


title: Evaluating Recommendation Algorithms by Graph Analysis

abstract: We present a novel framework for evaluating recommendation algorithms in terms of the `jumps' that they make to connect people to artifacts. This approach emphasizes reachability via an algorithm within the implicit graph structure underlying a recommender dataset, and serves as a complement to evaluation in terms of predictive accuracy. The framework allows us to consider questions relating algorithmic parameters to properties of the datasets. For instance, given a particular algorithm `jump,' what is the average path length from a person to an artifact? Or, what choices of minimum ratings and jumps maintain a connected graph? We illustrate the approach with a common jump called the `hammock' using movie recommender datasets.


title: Type Arithmetics: Computation based on the theory of types

abstract: The present paper shows meta-programming turn programming, which is rich enough to express arbitrary arithmetic computations. We demonstrate a type system that implements Peano arithmetics, slightly generalized to negative numbers. Certain types in this system denote numerals. Arithmetic operations on such types-numerals - addition, subtraction, and even division - are expressed as type reduction rules executed by a compiler. A remarkable trait is that division by zero becomes a type error - and reported as such by a compiler.


title: Potholes on the Royal Road

abstract: 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.


title: System Support for Bandwidth Management and Content Adaptation in Internet Applications

abstract: This paper describes the implementation and evaluation of an operating system module, the Congestion Manager (CM), which provides integrated network flow management and exports a convenient programming interface that allows applications to be notified of, and adapt to, changing network conditions. We describe the API by which applications interface with the CM, and the architectural considerations that factored into the design. To evaluate the architecture and API, we describe our implementations of TCP; a streaming layered audio/video application; and an interactive audio application using the CM, and show that they achieve adaptive behavior without incurring much end-system overhead. All flows including TCP benefit from the sharing of congestion information, and applications are able to incorporate new functionality such as congestion control and adaptive behavior.


title: Shooting Over or Under the Mark: Towards a Reliable and Flexible Anticipation in the Economy

abstract: The real monetary economy is grounded upon monetary flow equilibration or the activity of actualizing monetary flow continuity at each economic agent except for the central bank. Every update of monetary flow continuity at each agent constantly causes monetary flow equilibration at the neighborhood agents. Every monetary flow equilibration as the activity of shooting the mark identified as monetary flow continuity turns out to be off the mark, and constantly generate the similar activities in sequence. Monetary flow equilibration ceaselessly reverberating in the economy performs two functions. One is to seek an organization on its own, and the other is to perturb the ongoing organization. Monetary flow equilibration as the agency of seeking and perturbing its organization also serves as a means of predicting its behavior. The likely organizational behavior could be the one that remains most robust against monetary flow equilibration as an agency of applying perturbations.


title: Tracing a Faint Fingerprint of the Invisible Hand?

abstract: 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.


title: Application of Support Vector Machine to detect an association between a disease or trait and multiple SNP variations

abstract: After the completion of human genome sequence was anounced, it is evident that interpretation of DNA sequences is an immediate task to work on. For understanding their signals, improvement of present sequence analysis tools and developing new ones become necessary. Along this current trend, we attack one of the fundamental questions, which set of SNP(single nucleotide polymorphism) variations is related to a specific disease or trait is. For, in the whole DNA sequence, it is known that people have different DNAs only at SNP locations, and moreover, the total SNPs are less than 5 millions, finding an association between SNP variations and certain disease or trait is believed to be one of the essential steps not only for genetic researches but for drug design and discovery. In this paper, we are going to present a method of detecting whether there is an association between multiple SNP variations and a trait or disease. The method exploits the Support Vector Machine which has been attracting lots of attentions recently.


title: The Gibbs Representation of 3D Rotations

abstract: This paper revisits the little-known Gibbs-Rodrigues representation of rotations in a three-dimensional space and demonstrates a set of algorithms for handling it. In this representation the rotation is itself represented as a three-dimensional vector. The vector is parallel to the axis of rotation and its three components transform covariantly on change of coordinates. The mapping from rotations to vectors is 1:1 apart from computation error. The discontinuities of the representation require special handling but are not problematic. The rotation matrix can be generated efficiently from the vector without the use of transcendental functions, and vice-versa. The representation is more efficient than Euler angles, has affinities with Hassenpflug's Argyris angles and is very closely related to the quaternion representation. While the quaternion representation avoids the discontinuities inherent in any 3-component representation, this problem is readily overcome. The present paper gives efficient algorithms for computing the set of rotations which map a given vector to another of the same length and the rotation which maps a given pair of vectors to another pair of the same length and subtended angle.


title: Local Search Techniques for Constrained Portfolio Selection Problems

abstract: We consider the problem of selecting a portfolio of assets that provides the investor a suitable balance of expected return and risk. With respect to the seminal mean-variance model of Markowitz, we consider additional constraints on the cardinality of the portfolio and on the quantity of individual shares. Such constraints better capture the real-world trading system, but make the problem more difficult to be solved with exact methods. We explore the use of local search techniques, mainly tabu search, for the portfolio selection problem. We compare and combine previous work on portfolio selection that makes use of the local search approach and we propose new algorithms that combine different neighborhood relations. In addition, we show how the use of randomization and of a simple form of adaptiveness simplifies the setting of a large number of critical parameters. Finally, we show how our techniques perform on public benchmarks.


title: Several new domain-type and boundary-type numerical discretization schemes with radial basis function

abstract: This paper is concerned with a few novel RBF-based numerical schemes discretizing partial differential equations. For boundary-type methods, we derive the indirect and direct symmetric boundary knot methods (BKM). The resulting interpolation matrix of both is always symmetric irrespective of boundary geometry and conditions. In particular, the direct BKM applies the practical physical variables rather than expansion coefficients and becomes very competitive to the boundary element method. On the other hand, based on the multiple reciprocity principle, we invent the RBF-based boundary particle method (BPM) for general inhomogeneous problems without a need using inner nodes. The direct and symmetric BPM schemes are also developed. For domain-type RBF discretization schemes, by using the Green integral we develop a new Hermite RBF scheme called as the modified Kansa method (MKM), which differs from the symmetric Hermite RBF scheme in that the MKM discretizes both governing equation and boundary conditions on the same boundary nodes. The local spline version of the MKM is named as the finite knot method (FKM). Both MKM and FKM significantly reduce calculation errors at nodes adjacent to boundary. In addition, the nonsingular high-order fundamental or general solution is strongly recommended as the RBF in the domain-type methods and dual reciprocity method approximation of particular solution relating to the BKM. It is stressed that all the above discretization methods of boundary-type and domain-type are symmetric, meshless, and integration-free. The spline-based schemes will produce desirable symmetric sparse banded interpolation matrix. In appendix, we present a Hermite scheme to eliminate edge effect on the RBF geometric modeling and imaging.


title: Dynamic Nonlocal Language Modeling via Hierarchical Topic-Based Adaptation

abstract: This paper presents a novel method of generating and applying hierarchical, dynamic topic-based language models. It proposes and evaluates new cluster generation, hierarchical smoothing and adaptive topic-probability estimation techniques. These combined models help capture long-distance lexical dependencies. Experiments on the Broadcast News corpus show significant improvement in perplexity (10.5% overall and 33.5% on target vocabulary).


title: Coaxing Confidences from an Old Friend: Probabilistic Classifications from Transformation Rule Lists

abstract: 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.


title: Disjunction and modular goal-directed proof search

abstract: This paper explores goal-directed proof search in first-order multi-modal logic. The key issue is to design a proof system that respects the modularity and locality of assumptions of many modal logics. By forcing ambiguities to be considered independently, modular disjunctions in particular can be used to construct efficiently executable specifications in reasoning tasks involving partial information that otherwise might require prohibitive search. To achieve this behavior requires prior proof-theoretic justifications of logic programming to be extended, strengthened, and combined with proof-theoretic analyses of modal deduction in a novel way.


title: Microplanning with Communicative Intentions: The SPUD System

abstract: The process of microplanning encompasses a range of problems in Natural Language Generation (NLG), such as referring expression generation, lexical choice, and aggregation, problems in which a generator must bridge underlying domain-specific representations and general linguistic representations. In this paper, we describe a uniform approach to microplanning based on declarative representations of a generator's communicative intent. These representations describe the results of NLG: communicative intent associates the concrete linguistic structure planned by the generator with inferences that show how the meaning of that structure communicates needed information about some application domain in the current discourse context. Our approach, implemented in the SPUD (sentence planning using description) microplanner, uses the lexicalized tree-adjoining grammar formalism (LTAG) to connect structure to meaning and uses modal logic programming to connect meaning to context. At the same time, communicative intent representations provide a resource for the process of NLG. Using representations of communicative intent, a generator can augment the syntax, semantics and pragmatics of an incomplete sentence simultaneously, and can assess its progress on the various problems of microplanning incrementally. The declarative formulation of communicative intent translates into a well-defined methodology for designing grammatical and conceptual resources which the generator can use to achieve desired microplanning behavior in a specified domain.


title: Correction of Errors in a Modality Corpus Used for Machine Translation by Using Machine-learning Method

abstract: 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.


title: Man [and Woman] vs. Machine: A Case Study in Base Noun Phrase Learning

abstract: A great deal of work has been done demonstrating the ability of machine learning algorithms to automatically extract linguistic knowledge from annotated corpora. Very little work has gone into quantifying the difference in ability at this task between a person and a machine. This paper is a first step in that direction.


title: Rule Writing or Annotation: Cost-efficient Resource Usage for Base Noun Phrase Chunking

abstract: This paper presents a comprehensive empirical comparison between two approaches for developing a base noun phrase chunker: human rule writing and active learning using interactive real-time human annotation. Several novel variations on active learning are investigated, and underlying cost models for cross-modal machine learning comparison are presented and explored. Results show that it is more efficient and more successful by several measures to train a system using active learning annotation rather than hand-crafted rule writing at a comparable level of human labor investment.


title: Parallel implementation of the TRANSIMS micro-simulation

abstract: This paper describes the parallel implementation of the TRANSIMS traffic micro-simulation. The parallelization method is domain decomposition, which means that each CPU of the parallel computer is responsible for a different geographical area of the simulated region. We describe how information between domains is exchanged, and how the transportation network graph is partitioned. An adaptive scheme is used to optimize load balancing. We then demonstrate how computing speeds of our parallel micro-simulations can be systematically predicted once the scenario and the computer architecture are known. This makes it possible, for example, to decide if a certain study is feasible with a certain computing budget, and how to invest that budget. The main ingredients of the prediction are knowledge about the parallel implementation of the micro-simulation, knowledge about the characteristics of the partitioning of the transportation network graph, and knowledge about the interaction of these quantities with the computer system. In particular, we investigate the differences between switched and non-switched topologies, and the effects of 10 Mbit, 100 Mbit, and Gbit Ethernet. keywords: Traffic simulation, parallel computing, transportation planning, TRANSIMS


title: A Complete WordNet1.5 to WordNet1.6 Mapping

abstract: We describe a robust approach for linking already existing lexical/semantic hierarchies. We use a constraint satisfaction algorithm (relaxation labelling) to select --among a set of candidates-- the node in a target taxonomy that bests matches each node in a source taxonomy. In this paper we present the complete mapping of the nominal, verbal, adjectival and adverbial parts of WordNet 1.5 onto WordNet 1.6.


title: Reverse Engineering from Assembler to Formal Specifications via Program Transformations

abstract: The FermaT transformation system, based on research carried out over the last sixteen years at Durham University, De Montfort University and Software Migrations Ltd., is an industrial-strength formal transformation engine with many applications in program comprehension and language migration. This paper is a case study which uses automated plus manually-directed transformations and abstractions to convert an IBM 370 Assembler code program into a very high-level abstract specification.


title: Analysis of Polymorphically Typed Logic Programs Using ACI-Unification

abstract: Analysis of (partial) groundness is an important application of abstract interpretation. There are several proposals for improving the precision of such an analysis by exploiting type information, icluding our own work with Hill and King, where we had shown how the information present in the type declarations of a program can be used to characterise the degree of instantiation of a term in a precise and yet inherently finite way. This approach worked for polymorphically typed programs as in Goedel or HAL. Here, we recast this approach following works by Codish, Lagoon and Stuckey. To formalise which properties of terms we want to characterise, we use labelling functions, which are functions that extract subterms from a term along certain paths. An abstract term collects the results of all labelling functions of a term. For the analysis, programs are executed on abstract terms instead of the concrete ones, and usual unification is replaced by unification modulo an equality theory which includes the well-known ACI-theory. Thus we generalise the works by Codish, Lagoon and Stuckey w.r.t. the type systems considered and relate the works among each other.


title: Applying Slicing Technique to Software Architectures

abstract: Software architecture is receiving increasingly attention as a critical design level for software systems. As software architecture design resources (in the form of architectural specifications) are going to be accumulated, the development of techniques and tools to support architectural understanding, testing, reengineering, maintenance, and reuse will become an important issue. This paper introduces a new form of slicing, named architectural slicing, to aid architectural understanding and reuse. In contrast to traditional slicing, architectural slicing is designed to operate on the architectural specification of a software system, rather than the source code of a program. Architectural slicing provides knowledge about the high-level structure of a software system, rather than the low-level implementation details of a program. In order to compute an architectural slice, we present the architecture information flow graph which can be used to represent information flows in a software architecture. Based on the graph, we give a two-phase algorithm to compute an architectural slice.


title: Using Dependence Analysis to Support Software Architecture Understanding

abstract: Software architecture is receiving increasingly attention as a critical design level for software systems. As software architecture design resources (in the form of architectural descriptions) are going to be accumulated, the development of techniques and tools to support architectural understanding, testing, reengineering, maintaining, and reusing will become an important issue. In this paper we introduce a new dependence analysis technique, named architectural dependence analysis to support software architecture development. In contrast to traditional dependence analysis, architectural dependence analysis is designed to operate on an architectural description of a software system, rather than the source code of a conventional program. Architectural dependence analysis provides knowledge of dependences for the high-level architecture of a software system, rather than the low-level implementation details of a conventional program.


title: On Assessing the Complexity of Software Architectures

abstract: This paper proposes some new architectural metrics which are appropriate for evaluating the architectural attributes of a software system. The main feature of our approach is to assess the complexity of a software architecture by analyzing various types of architectural dependences in the architecture.


title: Component Programming and Interoperability in Constraint Solver Design

abstract: 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.


title: Joint and conditional estimation of tagging and parsing models

abstract: This paper compares two different ways of estimating statistical language models. Many statistical NLP tagging and parsing models are estimated by maximizing the (joint) likelihood of the fully-observed training data. However, since these applications only require the conditional probability distributions, these distributions can in principle be learnt by maximizing the conditional likelihood of the training data. Perhaps somewhat surprisingly, models estimated by maximizing the joint were superior to models estimated by maximizing the conditional, even though some of the latter models intuitively had access to ``more information''.


title: Dijkstra's Self-Stabilizing Algorithm in Unsupportive Environments

abstract: 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.


title: Errata and supplements to: Orthonormal RBF Wavelet and Ridgelet-like Series and Transforms for High-Dimensional Problems

abstract: In recent years some attempts have been done to relate the RBF with wavelets in handling high dimensional multiscale problems. To the author's knowledge, however, the orthonormal and bi-orthogonal RBF wavelets are still missing in the literature. By using the nonsingular general solution and singular fundamental solution of differential operator, recently the present author, refer. 3, made some substantial headway to derive the orthonormal RBF wavelets series and transforms. The methodology can be generalized to create the RBF wavelets by means of the orthogonal convolution kernel function of various integral operators. In particular, it is stressed that the presented RBF wavelets does not apply the tensor product to handle multivariate problems at all. This note is to correct some errata in reference 3 and also to supply a few latest advances in the study of orthornormal RBF wavelet transforms.


title: The alldifferent Constraint: A Survey

abstract: The constraint of difference is known to the constraint programming community since Lauriere introduced Alice in 1978. Since then, several solving strategies have been designed for this constraint. In this paper we give both a practical overview and an abstract comparison of these different strategies.


title: Probabilistic top-down parsing and language modeling

abstract: This paper describes the functioning of a broad-coverage probabilistic top-down parser, and its application to the problem of language modeling for speech recognition. The paper first introduces key notions in language modeling and probabilistic parsing, and briefly reviews some previous approaches to using syntactic structure for language modeling. A lexicalized probabilistic top-down parser is then presented, which performs very well, in terms of both the accuracy of returned parses and the efficiency with which they are found, relative to the best broad-coverage statistical parsers. A new language model which utilizes probabilistic top-down parsing is then outlined, and empirical results show that it improves upon previous work in test corpus perplexity. Interpolation with a trigram model yields an exceptional improvement relative to the improvement observed by other models, demonstrating the degree to which the information captured by our parsing model is orthogonal to that captured by a trigram model. A small recognition experiment also demonstrates the utility of the model.


title: Optimization Over Zonotopes and Training Support Vector Machines

abstract: We make a connection between classical polytopes called zonotopes and Support Vector Machine (SVM) classifiers. We combine this connection with the ellipsoid method to give some new theoretical results on training SVMs. We also describe some special properties of soft margin C-SVMs as parameter C goes to infinity.


title: HTTP Cookies: Standards, Privacy, and Politics

abstract: How did we get from a world where cookies were something you ate and where "non-techies" were unaware of "Netscape cookies" to a world where cookies are a hot-button privacy issue for many computer users? This paper will describe how HTTP "cookies" work, and how Netscape's original specification evolved into an IETF Proposed Standard. I will also offer a personal perspective on how what began as a straightforward technical specification turned into a political flashpoint when it tried to address non-technical issues such as privacy.


title: Robust Probabilistic Predictive Syntactic Processing

abstract: This thesis presents a broad-coverage probabilistic top-down parser, and its application to the problem of language modeling for speech recognition. The parser builds fully connected derivations incrementally, in a single pass from left-to-right across the string. We argue that the parsing approach that we have adopted is well-motivated from a psycholinguistic perspective, as a model that captures probabilistic dependencies between lexical items, as part of the process of building connected syntactic structures. The basic parser and conditional probability models are presented, and empirical results are provided for its parsing accuracy on both newspaper text and spontaneous telephone conversations. Modifications to the probability model are presented that lead to improved performance. A new language model which uses the output of the parser is then defined. Perplexity and word error rate reduction are demonstrated over trigram models, even when the trigram is trained on significantly more data. Interpolation on a word-by-word basis with a trigram model yields additional improvements.


title: A Logical Framework for Convergent Infinite Computations

abstract: Classical computations can not capture the essence of infinite computations very well. This paper will focus on a class of infinite computations called convergent infinite computations}. A logic for convergent infinite computations is proposed by extending first order theories using Cauchy sequences, which has stronger expressive power than the first order logic. A class of fixed points characterizing the logical properties of the limits can be represented by means of infinite-length terms defined by Cauchy sequences. We will show that the limit of sequence of first order theories can be defined in terms of distance, similar to the $\epsilon-N$ style definition of limits in real analysis. On the basis of infinitary terms, a computation model for convergent infinite computations is proposed. Finally, the interpretations of logic programs are extended by introducing real Herbrand models of logic programs and a sufficient condition for computing a real Herbrand model of Horn logic programs using convergent infinite computation is given.


title: Solving Composed First-Order Constraints from Discrete-Time Robust Control

abstract: This paper deals with a problem from discrete-time robust control which requires the solution of constraints over the reals that contain both universal and existential quantifiers. For solving this problem we formulate it as a program in a (fictitious) constraint logic programming language with explicit quantifier notation. This allows us to clarify the special structure of the problem, and to extend an algorithm for computing approximate solution sets of first-order constraints over the reals to exploit this structure. As a result we can deal with inputs that are clearly out of reach for current symbolic solvers.


title: Multi-Channel Parallel Adaptation Theory for Rule Discovery

abstract: In this paper, we introduce a new machine learning theory based on multi-channel parallel adaptation for rule discovery. This theory is distinguished from the familiar parallel-distributed adaptation theory of neural networks in terms of channel-based convergence to the target rules. We show how to realize this theory in a learning system named CFRule. CFRule is a parallel weight-based model, but it departs from traditional neural computing in that its internal knowledge is comprehensible. Furthermore, when the model converges upon training, each channel converges to a target rule. The model adaptation rule is derived by multi-level parallel weight optimization based on gradient descent. Since, however, gradient descent only guarantees local optimization, a multi-channel regression-based optimization strategy is developed to effectively deal with this problem. Formally, we prove that the CFRule model can explicitly and precisely encode any given rule set. Also, we prove a property related to asynchronous parallel convergence, which is a critical element of the multi-channel parallel adaptation theory for rule learning. Thanks to the quantizability nature of the CFRule model, rules can be extracted completely and soundly via a threshold-based mechanism. Finally, the practical application of the theory is demonstrated in DNA promoter recognition and hepatitis prognosis prediction.


title: Generating a 3D Simulation of a Car Accident from a Written Description in Natural Language: the CarSim System

abstract: 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.


title: Constraint Propagation in Presence of Arrays

abstract: 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.


title: Market-Based Reinforcement Learning in Partially Observable Worlds

abstract: 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.


title: Toward Natural Gesture/Speech Control of a Large Display

abstract: In recent years because of the advances in computer vision research, free hand gestures have been explored as means of human-computer interaction (HCI). Together with improved speech processing technology it is an important step toward natural multimodal HCI. However, inclusion of non-predefined continuous gestures into a multimodal framework is a challenging problem. In this paper, we propose a structured approach for studying patterns of multimodal language in the context of a 2D-display control. We consider systematic analysis of gestures from observable kinematical primitives to their semantics as pertinent to a linguistic structure. Proposed semantic classification of co-verbal gestures distinguishes six categories based on their spatio-temporal deixis. We discuss evolution of a computational framework for gesture and speech integration which was used to develop an interactive testbed (iMAP). The testbed enabled elicitation of adequate, non-sequential, multimodal patterns in a narrative mode of HCI. Conducted user studies illustrate significance of accounting for the temporal alignment of gesture and speech parts in semantic mapping. Furthermore, co-occurrence analysis of gesture/speech production suggests syntactic organization of gestures at the lexical level.


title: Bounds on sample size for policy evaluation in Markov environments

abstract: Reinforcement learning means finding the optimal course of action in Markovian environments without knowledge of the environment's dynamics. Stochastic optimization algorithms used in the field rely on estimates of the value of a policy. Typically, the value of a policy is estimated from results of simulating that very policy in the environment. This approach requires a large amount of simulation as different points in the policy space are considered. In this paper, we develop value estimators that utilize data gathered when using one policy to estimate the value of using another policy, resulting in much more data-efficient algorithms. We consider the question of accumulating a sufficient experience and give PAC-style bounds.


title: When being Weak is Brave: Privacy in Recommender Systems

abstract: We explore the conflict between personalization and privacy that arises from the existence of weak ties. A weak tie is an unexpected connection that provides serendipitous recommendations. However, information about weak ties could be used in conjunction with other sources of data to uncover identities and reveal other personal information. In this article, we use a graph-theoretic model to study the benefit and risk from weak ties.


title: Coloring k-colorable graphs using relatively small palettes

abstract: We obtain the following new coloring results: * A 3-colorable graph on $n$ vertices with maximum degree~$\Delta$ can be colored, in polynomial time, using $O((\Delta \log\Delta)^{1/3} \cdot\log{n})$ colors. This slightly improves an $O((\Delta^{{1}/{3}} \log^{1/2}\Delta)\cdot\log{n})$ bound given by Karger, Motwani and Sudan. More generally, $k$-colorable graphs with maximum degree $\Delta$ can be colored, in polynomial time, using $O((\Delta^{1-{2}/{k}}\log^{1/k}\Delta) \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^{\alpha_k})$ colors, where $\alpha_5=97/207$, $\alpha_6=43/79$, $\alpha_7=1391/2315$, $\alpha_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.


title: The OLAC Metadata Set and Controlled Vocabularies

abstract: 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.


title: State Analysis and Aggregation Study for Multicast-based Micro Mobility

abstract: IP mobility addresses the problem of changing the network point-of-attachment transparently during movement. Mobile IP is the proposed standard by IETF. Several studies, however, have shown that Mobile IP has several drawbacks, such as triangle routing and poor handoff performance. Multicast-based mobility has been proposed as a promising solution to the above problems, incurring less end-to-end delays and fast smooth handoff. Nonetheless, such architecture suffers from multicast state scalability problems with the growth in number of mobile nodes. This architecture also requires ubiquitous multicast deployment and more complex security measures. To alleviate these problems, we propose an intra-domain multicast-based mobility solution. A mobility proxy allocates a multicast address for each mobile that moves to its domain. The mobile uses this multicast address within a domain for micro mobility. Also, aggregation is considered to reduce the multicast state. We conduct multicast state analysis to study the efficiency of several aggregation techniques. We use extensive simulation to evaluate our protocol's performance over a variety of real and generated topologies. We take aggregation gain as metric for our evaluation. Our simulation results show that in general leaky aggregation obtains better gains than perfect aggregation. Also, we notice that aggregation gain increases with the increase in number of visiting mobile nodes and with the decrease in number of mobility proxies within a domain.


title: Learning to Cooperate via Policy Search

abstract: Cooperative games are those in which both agents share the same payoff structure. Value-based reinforcement-learning algorithms, such as variants of Q-learning, have been applied to learning cooperative games, but they only apply when the game state is completely observable to both agents. Policy search methods are a reasonable alternative to value-based methods for partially observable environments. In this paper, we provide a gradient-based distributed policy-search method for cooperative games and compare the notion of local optimum to that of Nash equilibrium. We demonstrate the effectiveness of this method experimentally in a small, partially observable simulated soccer domain.


title: Lectures on Reduce and Maple at UAM I - Mexico

abstract: 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.


title: On the Area of Hypercube Layouts

abstract: This paper precisely analyzes the wire density and required area in standard layout styles for the hypercube. The most natural, regular layout of a hypercube of N^2 nodes in the plane, in a N x N grid arrangement, uses floor(2N/3)+1 horizontal wiring tracks for each row of nodes. (The number of tracks per row can be reduced by 1 with a less regular design.) This paper also gives a simple formula for the wire density at any cut position and a full characterization of all places where the wire density is maximized (which does not occur at the bisection).


title: Historical Dynamics of Lexical System as Random Walk Process

abstract: 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.


title: Disjunctive Logic Programs with Inheritance

abstract: The paper proposes a new knowledge representation language, called DLP<, which extends disjunctive logic programming (with strong negation) by inheritance. The addition of inheritance enhances the knowledge modeling features of the language providing a natural representation of default reasoning with exceptions. A declarative model-theoretic semantics of DLP< is provided, which is shown to generalize the Answer Set Semantics of disjunctive logic programs. The knowledge modeling features of the language are illustrated by encoding classical nonmonotonic problems in DLP<. The complexity of DLP< is analyzed, proving that inheritance does not cause any computational overhead, as reasoning in DLP< has exactly the same complexity as reasoning in disjunctive logic programming. This is confirmed by the existence of an efficient translation from DLP< to plain disjunctive logic programming. Using this translation, an advanced KR system supporting the DLP< language has been implemented on top of the DLV system and has subsequently been integrated into DLV.


title: Integrating Prosodic and Lexical Cues for Automatic Topic Segmentation

abstract: We present a probabilistic model that uses both prosodic and lexical cues for the automatic segmentation of speech into topically coherent units. We propose two methods for combining lexical and prosodic information using hidden Markov models and decision trees. Lexical information is obtained from a speech recognizer, and prosodic features are extracted automatically from speech waveforms. We evaluate our approach on the Broadcast News corpus, using the DARPA-TDT evaluation metrics. Results show that the prosodic model alone is competitive with word-based segmentation methods. Furthermore, we achieve a significant reduction in error by combining the prosodic and word-based knowledge sources.


title: Approximating the satisfiability threshold for random k-XOR-formulas

abstract: In this paper we study random linear systems with $k$ variables per equation over the finite field GF(2), or equivalently $k$-XOR-CNF formulas. In a previous paper Creignou and Daud\'e proved that the phase transition for the consistency (satisfiability) of such systems (formulas) exhibits a sharp threshold. Here we prove that the phase transition occurs as the number of equations (clauses) is proportional to the number of variables. For any $k\ge 3$ we establish first estimates for the critical ratio. For $k=3$ we get 0.93 as an upper bound, 0.89 as a lower bound, whereas experiments suggest that the critical ratio is approximately 0.92.


title: Solving Assembly Line Balancing Problems by Combining IP and CP

abstract: Assembly line balancing problems consist in partitioning the work necessary to assemble a number of products among different stations of an assembly line. We present a hybrid approach for solving such problems, which combines constraint programming and integer programming.


title: A note on radial basis function computing

abstract: This note carries three purposes involving our latest advances on the radial basis function (RBF) approach. First, we will introduce a new scheme employing the boundary knot method (BKM) to nonlinear convection-diffusion problem. It is stressed that the new scheme directly results in a linear BKM formulation of nonlinear problems by using response point-dependent RBFs, which can be solved by any linear solver. Then we only need to solve a single nonlinear algebraic equation for desirable unknown at some inner node of interest. The numerical results demonstrate high accuracy and efficiency of this nonlinear BKM strategy. Second, we extend the concepts of distance function, which include time-space and variable transformation distance functions. Finally, we demonstrate that if the nodes are symmetrically placed, the RBF coefficient matrices have either centrosymmetric or skew centrosymmetric structures. The factorization features of such matrices lead to a considerable reduction in the RBF computing effort. A simple approach is also presented to reduce the ill-conditioning of RBF interpolation matrices in general cases.


title: Soft Scheduling

abstract: Classical notions of disjunctive and cumulative scheduling are studied from the point of view of soft constraint satisfaction. Soft disjunctive scheduling is introduced as an instance of soft CSP and preferences included in this problem are applied to generate a lower bound based on existing discrete capacity resource. Timetabling problems at Purdue University and Faculty of Informatics at Masaryk University considering individual course requirements of students demonstrate practical problems which are solved via proposed methods. Implementation of general preference constraint solver is discussed and first computational results for timetabling problem are presented.


title: The Representation of Legal Contracts

abstract: The paper outlines ongoing research on logic-based tools for the analysis and representation of legal contracts of the kind frequently encountered in large-scale engineering projects and complex, long-term trading agreements. We consider both contract formation and contract performance, in each case identifying the representational issues and the prospects for providing automated support tools.


title: A Constraint-Driven System for Contract Assembly

abstract: We present an approach for modelling the structure and coarse content of legal documents with a view to providing automated support for the drafting of contracts and contract database retrieval. The approach is designed to be applicable where contract drafting is based on model-form contracts or on existing examples of a similar type. The main features of the approach are: (1) the representation addresses the structure and the interrelationships between the constituent parts of contracts, but not the text of the document itself; (2) the representation of documents is separated from the mechanisms that manipulate it; and (3) the drafting process is subject to a collection of explicitly stated constraints that govern the structure of the documents. We describe the representation of document instances and of 'generic documents', which are data structures used to drive the creation of new document instances, and we show extracts from a sample session to illustrate the features of a prototype system implemented in MacProlog.


title: Modelling Contractual Arguments

abstract: One influential approach to assessing the "goodness" of arguments is offered by the Pragma-Dialectical school (p-d) (Eemeren & Grootendorst 1992). This can be compared with Rhetorical Structure Theory (RST) (Mann & Thompson 1988), an approach that originates in discourse analysis. In p-d terms an argument is good if it avoids committing a fallacy, whereas in RST terms an argument is good if it is coherent. RST has been criticised (Snoeck Henkemans 1997) for providing only a partially functional account of argument, and similar criticisms have been raised in the Natural Language Generation (NLG) community-particularly by Moore & Pollack (1992)- with regards to its account of intentionality in text in general. Mann and Thompson themselves note that although RST can be successfully applied to a wide range of texts from diverse domains, it fails to characterise some types of text, most notably legal contracts. There is ongoing research in the Artificial Intelligence and Law community exploring the potential for providing electronic support to contract negotiators, focusing on long-term, complex engineering agreements (see for example Daskalopulu & Sergot 1997). This paper provides a brief introduction to RST and illustrates its shortcomings with respect to contractual text. An alternative approach for modelling argument structure is presented which not only caters for contractual text, but also overcomes the aforementioned limitations of RST.