title: Computing Functional and Relational Box Consistency by Structured Propagation in Atomic Constraint Systems

abstract: Box consistency has been observed to yield exponentially better performance than chaotic constraint propagation in the interval constraint system obtained by decomposing the original expression into primitive constraints. The claim was made that the improvement is due to avoiding decomposition. In this paper we argue that the improvement is due to replacing chaotic iteration by a more structured alternative. To this end we distinguish the existing notion of box consistency from relational box consistency. We show that from a computational point of view it is important to maintain the functional structure in constraint systems that are associated with a system of equations. So far, it has only been considered computationally important that constraint propagation be fair. With the additional structure of functional constraint systems, one can define and implement computationally effective, structured, truncated constraint propagations. The existing algorithm for box consistency is one such. Our results suggest that there are others worth investigating.


title: Model Checking Contractual Protocols

abstract: This paper discusses how model checking, a technique used for the verification of behavioural requirements of dynamic systems, can be usefully deployed for the verification of contracts. A process view of agreements between parties is taken, whereby a contract is modelled as it evolves over time in terms of actions or more generally events that effect changes in its state. Modelling is done with Petri Nets in the spirit of other research work on the representation of trade procedures. The paper illustrates all the phases of the verification technique through an example and argues that the approach is useful particularly in the context of pre-contractual negotiation and contract drafting. The work reported here is part of a broader project on the development of logic-based tools for the analysis and representation of legal contracts.


title: Modelling Legal Contracts as Processes

abstract: This paper concentrates on the representation of the legal relations that obtain between parties once they have entered a contractual agreement and their evolution as the agreement progresses through time. Contracts are regarded as process and they are analysed in terms of the obligations that are active at various points during their life span. An informal notation is introduced that summarizes conveniently the states of an agreement as it evolves over time. Such a representation enables us to determine what the status of an agreement is, given an event or a sequence of events that concern the performance of actions by the agents involved. This is useful both in the context of contract drafting (where parties might wish to preview how their agreement might evolve) and in the context of contract performance monitoring (where parties might with to establish what their legal positions are once their agreement is in force). The discussion is based on an example that illustrates some typical patterns of contractual obligations.


title: Computational properties of environment-based disambiguation

abstract: The standard pipeline approach to semantic processing, in which sentences are morphologically and syntactically resolved to a single tree before they are interpreted, is a poor fit for applications such as natural language interfaces. This is because the environment information, in the form of the objects and events in the application's run-time environment, cannot be used to inform parsing decisions unless the input sentence is semantically analyzed, but this does not occur until after parsing in the single-tree semantic architecture. This paper describes the computational properties of an alternative architecture, in which semantic analysis is performed on all possible interpretations during parsing, in polynomial time.


title: Computational Properties of Metaquerying Problems

abstract: Metaquerying is a datamining technology by which hidden dependencies among several database relations can be discovered. This tool has already been successfully applied to several real-world applications. Recent papers provide only preliminary results about the complexity of metaquerying. In this paper we define several variants of metaquerying that encompass, as far as we know, all variants defined in the literature. We study both the combined complexity and the data complexity of these variants. We show that, under the combined complexity measure, metaquerying is generally intractable (unless P=NP), lying sometimes quite high in the complexity hierarchies (as high as NP^PP), depending on the characteristics of the plausibility index. However, we are able to single out some tractable and interesting metaquerying cases (whose combined complexity is LOGCFL-complete). As for the data complexity of metaquerying, we prove that, in general, this is in TC0, but lies within AC0 in some simpler cases. Finally, we discuss implementation of metaqueries, by providing algorithms to answer them.


title: The Set of Equations to Evaluate Objects

abstract: The notion of an equational shell is studied to involve the objects and their environment. Appropriate methods are studied as valid embeddings of refined objects. The refinement process determines the linkages between the variety of possible representations giving rise to variants of computations. The case study is equipped with the adjusted equational systems that validate the initial applicative framework.


title: L.T.Kuzin: Research Program

abstract: Lev T. Kuzin (1928--1997) is one of the founders of modern cybernetics and information science in Russia. He was awarded and honored the USSR State Prize for inspiring vision into the future of technical cybernetics and his invention and innovation of key technologies. The last years he interested in the computational models of geometrical and algebraic nature and their applications in various branches of computer science and information technologies. In the recent years the interest in computation models based on object notion has grown tremendously stimulating an interest to Kuzin's ideas. This year of 50th Anniversary of Cybernetics and on the occasion of his 70th birthday on September 12, 1998 seems especially appropriate for discussing Kuzin's Research Program.


title: Organizing Encyclopedic Knowledge based on the Web and its Application to Question Answering

abstract: We propose a method to generate large-scale encyclopedic knowledge, which is valuable for much NLP research, based on the Web. We first search the Web for pages containing a term in question. Then we use linguistic patterns and HTML structures to extract text fragments describing the term. Finally, we organize extracted term descriptions based on word senses and domains. In addition, we apply an automatically generated encyclopedia to a question answering system targeting the Japanese Information-Technology Engineers Examination.


title: File mapping Rule-based DBMS and Natural Language Processing

abstract: This paper describes the system of storage, extract and processing of information structured similarly to the natural language. For recursive inference the system uses the rules having the same representation, as the data. The environment of storage of information is provided with the File Mapping (SHM) mechanism of operating system. In the paper the main principles of construction of dynamic data structure and language for record of the inference rules are stated; the features of available implementation are considered and the description of the application realizing semantic information retrieval on the natural language is given.


title: An object evaluator to generate flexible applications

abstract: This paper contains a brief discussion of an object evaluator which is based on principles of evaluations in a category. The main tool system referred as the Application Development Environment (ADE) is used to build database applications involving the graphical user interface (GUI). The separation of a database access and the user interface is reached by distinguishing the potential and actual objects. The variety of applications may be generated that communicate with different and distinct desktop databases. The commutative diagrams' technique allows to involve retrieval and call of the delayed procedures.


title: Building the access pointers to a computation environment

abstract: A common object technique equipped with the categorical and computational styles is briefly outlined. An object is evaluated by embedding in a host computational environment which is the domain-ranged structure. An embedded object is accessed by the pointers generated within the host system. To assist with an easy extract the result of the evaluation a pre-embedded object is generated. It is observed as the decomposition into substitutional part and access function part which are generated during the object evaluation.


title: Playing Games with Algorithms: Algorithmic Combinatorial Game Theory

abstract: Combinatorial games lead to several interesting, clean problems in algorithms and complexity theory, many of which remain open. The purpose of this paper is to provide an overview of the area to encourage further research. In particular, we begin with general background in Combinatorial Game Theory, which analyzes ideal play in perfect-information games, and Constraint Logic, which provides a framework for showing hardness. Then we survey results about the complexity of determining ideal play in these games, and the related problems of solving puzzles, in terms of both polynomial-time algorithms and computational intractability results. Our review of background and survey of algorithmic results are by no means complete, but should serve as a useful primer.


title: Economic Models for Management of Resources in Grid Computing

abstract: The accelerated development in Grid and peer-to-peer computing has positioned them as promising next generation computing platforms. They enable the creation of Virtual Enterprises (VE) for sharing resources distributed across the world. However, resource management, application development and usage models in these environments is a complex undertaking. This is due to the geographic distribution of resources that are owned by different organizations. The resource owners of each of these resources have different usage or access policies and cost models, and varying loads and availability. In order to address complex resource management issues, we have proposed a computational economy framework for resource allocation and for regulating supply and demand in Grid computing environments. The framework provides mechanisms for optimizing resource provider and consumer objective functions through trading and brokering services. In a real world market, there exist various economic models for setting the price for goods based on supply-and-demand and their value to the user. They include commodity market, posted price, tenders and auctions. In this paper, we discuss the use of these models for interaction between Grid components in deciding resource value and the necessary infrastructure to realize them. In addition to normal services offered by Grid computing systems, we need an infrastructure to support interaction protocols, allocation mechanisms, currency, secure banking, and enforcement services. Furthermore, we demonstrate the usage of some of these economic models in resource brokering through Nimrod/G deadline and cost-based scheduling for two different optimization strategies on the World Wide Grid (WWG) testbed.


title: Object-oriented solutions

abstract: In this paper are briefly outlined the motivations, mathematical ideas in use, pre-formalization and assumptions, object-as-functor construction, `soft' types and concept constructions, case study for concepts based on variable domains, extracting a computational background, and examples of evaluations.


title: One More Revolution to Make: Free Scientific Publishing

abstract: Computer scientists are in the position to create new, free high-quality journals. So what would it take?


title: Object-oriented tools for advanced applications

abstract: This paper contains a brief discussion of the Application Development Environment (ADE) that is used to build database applications involving the graphical user interface (GUI). ADE computing separates the database access and the user interface. The variety of applications may be generated that communicate with different and distinct desktop databases. The advanced techniques allows to involve remote or stored procedures retrieval and call.


title: Objects and their computational framework

abstract: Most of the object notions are embedded into a logical domain, especially when dealing with a database theory. Thus, their properties within a computational domain are not yet studied properly. The main topic of this paper is to analyze different concepts of the distinct computational primitive frames to extract the useful object properties and their possible advantages. Some important metaoperators are used to unify the approaches and to establish their possible correspondences.


title: Information Integration and Computational Logic

abstract: Information Integration is a young and exciting field with enormous research and commercial significance in the new world of the Information Society. It stands at the crossroad of Databases and Artificial Intelligence requiring novel techniques that bring together different methods from these fields. Information from disparate heterogeneous sources often with no a-priori common schema needs to be synthesized in a flexible, transparent and intelligent way in order to respond to the demands of a query thus enabling a more informed decision by the user or application program. The field although relatively young has already found many practical applications particularly for integrating information over the World Wide Web. This paper gives a brief introduction of the field highlighting some of the main current and future research issues and application areas. It attempts to evaluate the current and potential role of Computational Logic in this and suggests some of the problems where logic-based techniques could be used.


title: Event Driven Computations for Relational Query Language

abstract: This paper deals with an extended model of computations which uses the parameterized families of entities for data objects and reflects a preliminary outline of this problem. Some topics are selected out, briefly analyzed and arranged to cover a general problem. The authors intended more to discuss the particular topics, their interconnection and computational meaning as a panel proposal, so that this paper is not yet to be evaluated as a closed journal paper. To save space all the technical and implementation features are left for the future paper. Data object is a schematic entity and modelled by the partial function. A notion of type is extended by the variable domains which depend on events and types. A variable domain is built from the potential and schematic individuals and generates the valid families of types depending on a sequence of events. Each valid type consists of the actual individuals which are actual relatively the event or script. In case when a type depends on the script then corresponding view for data objects is attached, otherwise a snapshot is generated. The type thus determined gives an upper range for typed variables so that the local ranges are event driven resulting is the families of actual individuals. An expressive power of the query language is extended using the extensional and intentional relations.


title: Event Driven Objects

abstract: A formal consideration in this paper is given for the essential notations to characterize the object that is distinguished in a problem domain. The distinct object is represented by another idealized object, which is a schematic element. When the existence of an element is significant, then a class of these partial elements is dropped down into actual, potential and virtual objects. The potential objects are gathered into the variable domains which are the extended ranges for unbound variables. The families of actual objects are shown to be parameterized with the types and events. The transitions between events are shown to be driven by the scripts. A computational framework arises which is described by the commutative diagrams.


title: Pricing Virtual Paths with Quality-of-Service Guarantees as Bundle Derivatives

abstract: We describe a model of a communication network that allows us to price complex network services as financial derivative contracts based on the spot price of the capacity in individual routers. We prove a theorem of a Girsanov transform that is useful for pricing linear derivatives on underlying assets, which can be used to price many complex network services, and it is used to price an option that gives access to one of several virtual channels between two network nodes, during a specified future time interval. We give the continuous time hedging strategy, for which the option price is independent of the service providers attitude towards risk. The option price contains the density function of a sum of lognormal variables, which has to be evaluated numerically.


title: Building Views with Description Logics in ADE: Application Development Environment

abstract: Any of views is formally defined within description logics that were established as a family of logics for modeling complex hereditary structures and have a suitable expressive power. This paper considers the Application Development Environment (ADE) over generalized variable concepts that are used to build database applications involving the supporting views. The front-end user interacts the database via separate ADE access mechanism intermediated by view support. The variety of applications may be generated that communicate with different and distinct desktop databases in a data warehouse. The advanced techniques allows to involve remote or stored procedures retrieval and call.


title: Logic, Individuals and Concepts

abstract: This extended abstract gives a brief outline of the connections between the descriptions and variable concepts. Thus, the notion of a concept is extended to include both the syntax and semantics features. The evaluation map in use is parameterized by a kind of computational environment, the index, giving rise to indexed concepts. The concepts are inhabited into language by the descriptions from the higher order logic. In general the idea of object-as-functor should assist the designer to outline a programming tool in conceptual shell style.


title: Complexity Results and Practical Algorithms for Logics in Knowledge Representation

abstract: Description Logics (DLs) are used in knowledge-based systems to represent and reason about terminological knowledge of the application domain in a semantically well-defined manner. In this thesis, we establish a number of novel complexity results and give practical algorithms for expressive DLs that provide different forms of counting quantifiers. We show that, in many cases, adding local counting in the form of qualifying number restrictions to DLs does not increase the complexity of the inference problems, even if binary coding of numbers in the input is assumed. On the other hand, we show that adding different forms of global counting restrictions to a logic may increase the complexity of the inference problems dramatically. We provide exact complexity results and a practical, tableau based algorithm for the DL SHIQ, which forms the basis of the highly optimized DL system iFaCT. Finally, we describe a tableau algorithm for the clique guarded fragment (CGF), which we hope will serve as the basis for an efficient implementation of a CGF reasoner.


title: Hinged Kite Mirror Dissection

abstract: Any two polygons of equal area can be partitioned into congruent sets of polygonal pieces, and in many cases one can connect the pieces by flexible hinges while still allowing the connected set to form both polygons. However it is open whether such a hinged dissection always exists. We solve a special case of this problem, by showing that any asymmetric polygon always has a hinged dissection to its mirror image. Our dissection forms a chain of kite-shaped pieces, found by a circle-packing algorithm for quadrilateral mesh generation. A hinged mirror dissection of a polygon with n sides can be formed with O(n) kites in O(n log n) time.


title: location.location.location: Internet Addresses as Evolving Property

abstract: I describe recent developments in the rules governing registration and ownership of Internet and World Wide Web addresses or "domain names." I consider the idea that "virtual" properties like domain names are more similar to real estate than to trademarks. Therefore, it would be economically efficient to grant domain name owners stronger rights than those of trademarks and copyright holders.


title: Solving equations in the relational algebra

abstract: Enumerating all solutions of a relational algebra equation is a natural and powerful operation which, when added as a query language primitive to the nested relational algebra, yields a query language for nested relational databases, equivalent to the well-known powerset algebra. We study \emph{sparse} equations, which are equations with at most polynomially many solutions. We look at their complexity, and compare their expressive power with that of similar notions in the powerset algebra.


title: Polymorphic type inference for the relational algebra

abstract: We give a polymorphic account of the relational algebra. We introduce a formalism of ``type formulas'' specifically tuned for relational algebra expressions, and present an algorithm that computes the ``principal'' type for a given expression. The principal type of an expression is a formula that specifies, in a clear and concise manner, all assignments of types (sets of attributes) to relation names, under which a given relational algebra expression is well-typed, as well as the output type that expression will have under each of these assignments. Topics discussed include complexity and polymorphic expressive power.


title: Convergence and Error Bounds for Universal Prediction of Nonbinary Sequences

abstract: Solomonoff's uncomputable universal prediction scheme $\xi$ allows to predict the next symbol $x_k$ of a sequence $x_1...x_{k-1}$ for any Turing computable, but otherwise unknown, probabilistic environment $\mu$. This scheme will be generalized to arbitrary environmental classes, which, among others, allows the construction of computable universal prediction schemes $\xi$. Convergence of $\xi$ to $\mu$ in a conditional mean squared sense and with $\mu$ probability 1 is proven. It is shown that the average number of prediction errors made by the universal $\xi$ scheme rapidly converges to those made by the best possible informed $\mu$ scheme. The schemes, theorems and proofs are given for general finite alphabet, which results in additional complications as compared to the binary case. Several extensions of the presented theory and results are outlined. They include general loss functions and bounds, games of chance, infinite alphabet, partial and delayed prediction, classification, and more active systems.


title: Using the No-Search Easy-Hard Technique for Downward Collapse

abstract: The top part of the preceding figure [figure appears in actual paper] shows some classes from the (truth-table) bounded-query and boolean hierarchies. It is well-known that if either of these hierarchies collapses at a given level, then all higher levels of that hierarchy collapse to that same level. This is a standard ``upward translation of equality'' that has been known for over a decade. The issue of whether these hierarchies can translate equality {\em downwards\/} has proven vastly more challenging. In particular, with regard to the figure above, consider the following claim: $$P_{m-tt}^{\Sigma_k^p} = P_{m+1-tt}^{\Sigma_k^p} \implies DIFF_m(\Sigma_k^p) coDIFF_m(\Sigma_k^p) = BH(\Sigma_k^p). (*) $$ This claim, if true, says that equality translates downwards between levels of the bounded-query hierarchy and the boolean hierarchy levels that (before the fact) are immediately below them. Until recently, it was not known whether (*) {\em ever\/} held, except for the degenerate cases $m=0$ and $k=0$. Then Hemaspaandra, Hemaspaandra, and Hempel \cite{hem-hem-hem:j:downward-translation} proved that (*) holds for all $m$, for $k > 2$. Buhrman and Fortnow~\cite{buh-for:j:two-queries} then showed that, when $k=2$, (*) holds for the case $m = 1$. In this paper, we prove that for the case $k=2$, (*) holds for all values of $m$. Since there is an oracle relative to which ``for $k=1$, (*) holds for all $m$'' fails \cite{buh-for:j:two-queries}, our achievement of the $k=2$ case cannot to be strengthened to $k=1$ by any relativizable proof technique. The new downward translation we obtain also tightens the collapse in the polynomial hierarchy implied by a collapse in the bounded-query hierarchy of the second level of the polynomial hierarchy.


title: Simple and Effective Distributed Computing with a Scheduling Service

abstract: High-throughput computing projects require the solution of large numbers of problems. In many cases, these problems can be solved on desktop PCs, or can be broken down into independent "PC-solvable" sub-problems. In such cases, the projects are high-performance computing projects, but only because of the sheer number of the needed calculations. We briefly describe our efforts to increase the throughput of one such project. We then explain how to easily set up a distributed computing facility composed of standard networked PCs running Windows 95, 98, 2000, or NT. The facility requires no special software or hardware, involves little or no re-coding of application software, and operates almost invisibly to the owners of the PCs. Depending on the number and quality of PCs recruited, performance can rival that of supercomputers.


title: Iterative Residual Rescaling: An Analysis and Generalization of LSI

abstract: We consider the problem of creating document representations in which inter-document similarity measurements correspond to semantic similarity. We first present a novel subspace-based framework for formalizing this task. Using this framework, we derive a new analysis of Latent Semantic Indexing (LSI), showing a precise relationship between its performance and the uniformity of the underlying distribution of documents over topics. This analysis helps explain the improvements gained by Ando's (2000) Iterative Residual Rescaling (IRR) algorithm: IRR can compensate for distributional non-uniformity. A further benefit of our framework is that it provides a well-motivated, effective method for automatically determining the rescaling factor IRR depends on, leading to further improvements. A series of experiments over various settings and with several evaluation metrics validates our claims.


title: Stacking classifiers for anti-spam filtering of e-mail

abstract: We evaluate empirically a scheme for combining classifiers, known as stacked generalization, in the context of anti-spam filtering, a novel cost-sensitive application of text categorization. Unsolicited commercial e-mail, or "spam", floods mailboxes, causing frustration, wasting bandwidth, and exposing minors to unsuitable content. Using a public corpus, we show that stacking can improve the efficiency of automatically induced anti-spam filters, and that such filters can be used in real-life applications.


title: Computing Complete Graph Isomorphisms and Hamiltonian Cycles from Partial Ones

abstract: We prove that computing a single pair of vertices that are mapped onto each other by an isomorphism $\phi$ between two isomorphic graphs is as hard as computing $\phi$ itself. This result optimally improves upon a result of G\'{a}l et al. We establish a similar, albeit slightly weaker, result about computing complete Hamiltonian cycles of a graph from partial Hamiltonian cycles.


title: MACE 2.0 Reference Manual and Guide

abstract: MACE is a program that searches for finite models of first-order statements. The statement to be modeled is first translated to clauses, then to relational clauses; finally for the given domain size, the ground instances are constructed. A Davis-Putnam-Loveland-Logeman procedure decides the propositional problem, and any models found are translated to first-order models. MACE is a useful complement to the theorem prover Otter, with Otter searching for proofs and MACE looking for countermodels.


title: Using the Distribution of Performance for Studying Statistical NLP Systems and Corpora

abstract: Statistical NLP systems are frequently evaluated and compared on the basis of their performances on a single split of training and test data. Results obtained using a single split are, however, subject to sampling noise. In this paper we argue in favour of reporting a distribution of performance figures, obtained by resampling the training data, rather than a single number. The additional information from distributions can be used to make statistically quantified statements about differences across parameter settings, systems, and corpora.


title: A Sequential Model for Multi-Class Classification

abstract: Many classification problems require decisions among a large number of competing classes. These tasks, however, are not handled well by general purpose learning methods and are usually addressed in an ad-hoc fashion. We suggest a general approach -- a sequential learning model that utilizes classifiers to sequentially restrict the number of competing classes while maintaining, with high probability, the presence of the true outcome in the candidates set. Some theoretical and computational properties of the model are discussed and we argue that these are important in NLP-like domains. The advantages of the model are illustrated in an experiment in part-of-speech tagging.


title: A Note on the Complexity of Computing the Smallest Four-Coloring of Planar Graphs

abstract: We show that computing the lexicographically first four-coloring for planar graphs is P^{NP}-hard. This result optimally improves upon a result of Khuller and Vazirani who prove this problem to be NP-hard, and conclude that it is not self-reducible in the sense of Schnorr, assuming P \neq NP. We discuss this application to non-self-reducibility and provide a general related result.


title: Expressing the cone radius in the relational calculus with real polynomial constraints

abstract: We show that there is a query expressible in first-order logic over the reals that returns, on any given semi-algebraic set A, for every point a radius around which A is conical. We obtain this result by combining famous results from calculus and real algebraic geometry, notably Sard's theorem and Thom's first isotopy lemma, with recent algorithmic results by Rannou.


title: Modeling informational novelty in a conversational system with a hybrid statistical and grammar-based approach to natural language generation

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


title: On some optimization problems for star-free graphs

abstract: It is shown that in star-free graphs the maximum independent set problem, the minimum dominating set problem and the minimum independent dominating set problem are approximable up to constant factor by any maximal independent set.


title: Recursively Undecidable Properties of NP

abstract: We show that there cannot be any algorithm that for a given nondeterministic polynomial-time Turing machine determinates whether or not the language recognized by this machine belongs to P


title: Classes of Terminating Logic Programs

abstract: Termination of logic programs depends critically on the selection rule, i.e. the rule that determines which atom is selected in each resolution step. In this article, we classify programs (and queries) according to the selection rules for which they terminate. This is a survey and unified view on different approaches in the literature. For each class, we present a sufficient, for most classes even necessary, criterion for determining that a program is in that class. We study six classes: a program strongly terminates if it terminates for all selection rules; a program input terminates if it terminates for selection rules which only select atoms that are sufficiently instantiated in their input positions, so that these arguments do not get instantiated any further by the unification; a program local delay terminates if it terminates for local selection rules which only select atoms that are bounded w.r.t. an appropriate level mapping; a program left-terminates if it terminates for the usual left-to-right selection rule; a program exists-terminates if there exists a selection rule for which it terminates; finally, a program has bounded nondeterminism if it only has finitely many refutations. We propose a semantics-preserving transformation from programs with bounded nondeterminism into strongly terminating programs. Moreover, by unifying different formalisms and making appropriate assumptions, we are able to establish a formal hierarchy between the different classes.


title: Users Guide for SnadiOpt: A Package Adding Automatic Differentiation to Snopt

abstract: SnadiOpt is a package that supports the use of the automatic differentiation package ADIFOR with the optimization package Snopt. Snopt is a general-purpose system for solving optimization problems with many variables and constraints. It minimizes a linear or nonlinear function subject to bounds on the variables and sparse linear or nonlinear constraints. It is suitable for large-scale linear and quadratic programming and for linearly constrained optimization, as well as for general nonlinear programs. The method used by Snopt requires the first derivatives of the objective and constraint functions to be available. The SnadiOpt package allows users to avoid the time-consuming and error-prone process of evaluating and coding these derivatives. Given Fortran code for evaluating only the values of the objective and constraints, SnadiOpt automatically generates the code for evaluating the derivatives and builds the relevant Snopt input files and sparse data structures.


title: Acceptability with general orderings

abstract: We present a new approach to termination analysis of logic programs. The essence of the approach is that we make use of general orderings (instead of level mappings), like it is done in transformational approaches to logic program termination analysis, but we apply these orderings directly to the logic program and not to the term-rewrite system obtained through some transformation. We define some variants of acceptability, based on general orderings, and show how they are equivalent to LD-termination. We develop a demand driven, constraint-based approach to verify these acceptability-variants. The advantage of the approach over standard acceptability is that in some cases, where complex level mappings are needed, fairly simple orderings may be easily generated. The advantage over transformational approaches is that it avoids the transformation step all together. {\bf Keywords:} termination analysis, acceptability, orderings.


title: Inference of termination conditions for numerical loops

abstract: We present a new approach to termination analysis of numerical computations in logic programs. Traditional approaches fail to analyse them due to non well-foundedness of the integers. We present a technique that allows to overcome these difficulties. Our approach is based on transforming a program in way that allows integrating and extending techniques originally developed for analysis of numerical computations in the framework of query-mapping pairs with the well-known framework of acceptability. Such an integration not only contributes to the understanding of termination behaviour of numerical computations, but also allows to perform a correct analysis of such computations automatically, thus, extending previous work on a constraints-based approach to termination. In the last section of the paper we discuss possible extensions of the technique, including incorporating general term orderings.


title: Software Toolkit for Building Embedded and Distributed Knowledge-based Systems

abstract: The paper discusses the basic principles and the architecture of the software toolkit for constructing knowledge-based systems which can be used cooperatively over computer networks and also embedded into larger software systems in different ways. Presented architecture is based on frame knowledge representation and production rules, which also allows to interface high-level programming languages and relational databases by exposing corresponding classes or database tables as frames. Frames located on the remote computers can also be transparently accessed and used in inference, and the dynamic knowledge for specific frames can also be transferred over the network. The issues of implementation of such a system are addressed, which use Java programming language, CORBA and XML for external knowledge representation. Finally, some applications of the toolkit are considered, including e-business approach to knowledge sharing, intelligent web behaviours, etc.


title: A Seamless Integration of Association Rule Mining with Database Systems

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


title: Randomized Two-Process Wait-Free Test-and-Set

abstract: We present the first explicit, and currently simplest, randomized algorithm for 2-process wait-free test-and-set. It is implemented with two 4-valued single writer single reader atomic variables. A test-and-set takes at most 11 expected elementary steps, while a reset takes exactly 1 elementary step. Based on a finite-state analysis, the proofs of correctness and expected length are compressed into one table.


title: Exposing and harvesting metadata using the OAI metadata harvesting protocol: A tutorial

abstract: In this article I outline the ideas behind the Open Archives Initiative metadata harvesting protocol (OAIMH), and attempt to clarify some common misconceptions. I then consider how the OAIMH protocol can be used to expose and harvest metadata. Perl code examples are given as practical illustration.


title: Enabling the Long-Term Archival of Signed Documents through Time Stamping

abstract: In this paper we describe how to build a trusted reliable distributed service across administrative domains in a peer-to-peer network. The application we use to motivate our work is a public key time stamping service called Prokopius. The service provides a secure, verifiable but distributable stable archive that maintains time stamped snapshots of public keys over time. This in turn allows clients to verify time stamped documents or certificates that rely on formerly trusted public keys that are no longer in service or where the signer no longer exists. We find that such a service can time stamp the snapshots of public keys in a network of 148 nodes at the granularity of a couple of days, even in the worst case where an adversary causes the maximal amount of damage allowable within our fault model.


title: CHR as grammar formalism. A first report

abstract: Grammars written as Constraint Handling Rules (CHR) can be executed as efficient and robust bottom-up parsers that provide a straightforward, non-backtracking treatment of ambiguity. Abduction with integrity constraints as well as other dynamic hypothesis generation techniques fit naturally into such grammars and are exemplified for anaphora resolution, coordination and text interpretation.


title: Analysis of Network Traffic in Switched Ethernet Systems

abstract: A 100 Mbps Ethernet link between a college campus and the outside world was monitored with a dedicated PC and the measured data analysed for its statistical properties. Similar measurements were taken at an internal node of the network. The networks in both cases are a full-duplex switched Ethernet. Inter-event interval histograms and power spectra of the throughput aggregated for 10ms bins were used to analyse the measured traffic. For most investigated cases both methods reveal that the traffic behaves according to a power law. The results will be used in later studies to parameterise models for network traffic.


title: Enhancing Constraint Propagation with Composition Operators

abstract: Constraint propagation is a general algorithmic approach for pruning the search space of a CSP. In a uniform way, K. R. Apt has defined a computation as an iteration of reduction functions over a domain. He has also demonstrated the need for integrating static properties of reduction functions (commutativity and semi-commutativity) to design specialized algorithms such as AC3 and DAC. We introduce here a set of operators for modeling compositions of reduction functions. Two of the major goals are to tackle parallel computations, and dynamic behaviours (such as slow convergence).


title: Lower Bounds for Zero-knowledge on the Internet

abstract: We consider zero knowledge interactive proofs in a richer, more realistic communication environment. In this setting, one may simultaneously engage in many interactive proofs, and these proofs may take place in an asynchronous fashion. It is known that zero-knowledge is not necessarily preserved in such an environment; we show that for a large class of protocols, it cannot be preserved. Any 4 round (computational) zero-knowledge interactive proof (or argument) for a non-trivial language L is not black-box simulatable in the asynchronous setting.


title: On Concurrent and Resettable Zero-Knowledge Proofs for NP

abstract: A proof is concurrent zero-knowledge if it remains zero-knowledge when many copies of the proof are run in an asynchronous environment, such as the Internet. It is known that zero-knowledge is not necessarily preserved in such an environment. Designing concurrent zero-knowledge proofs is a fundamental issue in the study of zero-knowledge since known zero-knowledge protocols cannot be run in a realistic modern computing environment. In this paper we present a concurrent zero-knowledge proof systems for all languages in NP. Currently, the proof system we present is the only known proof system that retains the zero-knowledge property when copies of the proof are allowed to run in an asynchronous environment. Our proof system has $\tilde{O}(\log^2 k)$ rounds (for a security parameter $k$), which is almost optimal, as it is shown by Canetti Kilian Petrank and Rosen that black-box concurrent zero-knowledge requires $\tilde{\Omega}(\log k)$ rounds. Canetti, Goldreich, Goldwasser and Micali introduced the notion of {\em resettable} zero-knowledge, and modified an earlier version of our proof system to obtain the first resettable zero-knowledge proof system. This protocol requires $k^{\theta(1)}$ rounds. We note that their technique also applies to our current proof system, yielding a resettable zero-knowledge proof for NP with $\tilde{O}(\log^2 k)$ rounds.


title: The Role of Conceptual Relations in Word Sense Disambiguation

abstract: We explore many ways of using conceptual distance measures in Word Sense Disambiguation, starting with the Agirre-Rigau conceptual density measure. We use a generalized form of this measure, introducing many (parameterized) refinements and performing an exhaustive evaluation of all meaningful combinations. We finally obtain a 42% improvement over the original algorithm, and show that measures of conceptual distance are not worse indicators for sense disambiguation than measures based on word-coocurrence (exemplified by the Lesk algorithm). Our results, however, reinforce the idea that only a combination of different sources of knowledge might eventually lead to accurate word sense disambiguation.


title: Looking Under the Hood : Tools for Diagnosing your Question Answering Engine

abstract: In this paper we analyze two question answering tasks : the TREC-8 question answering task and a set of reading comprehension exams. First, we show that Q/A systems perform better when there are multiple answer opportunities per question. Next, we analyze common approaches to two subproblems: term overlap for answer sentence identification, and answer typing for short answer extraction. We present general tools for analyzing the strengths and limitations of techniques for these subproblems. Our results quantify the limitations of both term overlap and answer typing to distinguish between competing answer candidates.


title: The Risk Profile Problem for Stock Portfolio Optimization

abstract: This work initiates research into the problem of determining an optimal investment strategy for investors with different attitudes towards the trade-offs of risk and profit. The probability distribution of the return values of the stocks that are considered by the investor are assumed to be known, while the joint distribution is unknown. The problem is to find the best investment strategy in order to minimize the probability of losing a certain percentage of the invested capital based on different attitudes of the investors towards future outcomes of the stock market. For portfolios made up of two stocks, this work shows how to exactly and quickly solve the problem of finding an optimal portfolio for aggressive or risk-averse investors, using an algorithm based on a fast greedy solution to a maximum flow problem. However, an investor looking for an average-case guarantee (so is neither aggressive or risk-averse) must deal with a more difficult problem. In particular, it is #P-complete to compute the distribution function associated with the average-case bound. On the positive side, approximate answers can be computed by using random sampling techniques similar to those for high-dimensional volume estimation. When k>2 stocks are considered, it is proved that a simple solution based on the same flow concepts as the 2-stock algorithm would imply that P = NP, so is highly unlikely. This work gives approximation algorithms for this case as well as exact algorithms for some important special cases.


title: Complex Tilings

abstract: We study the minimal complexity of tilings of a plane with a given tile set. We note that every tile set admits either no tiling or some tiling with O(n) Kolmogorov complexity of its n-by-n squares. We construct tile sets for which this bound is tight: all n-by-n squares in all tilings have complexity at least n. This adds a quantitative angle to classical results on non-recursivity of tilings -- that we also develop in terms of Turing degrees of unsolvability. Keywords: Tilings, Kolmogorov complexity, recursion theory


title: A Blueprint for Building Serverless Applications on the Net

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


title: Algorithms for Boolean Function Query Properties

abstract: We present new algorithms to compute fundamental properties of a Boolean function given in truth-table form. Specifically, we give an O(N^2.322 log N) algorithm for block sensitivity, an O(N^1.585 log N) algorithm for `tree decomposition,' and an O(N) algorithm for `quasisymmetry.' These algorithms are based on new insights into the structure of Boolean functions that may be of independent interest. We also give a subexponential-time algorithm for the space-bounded quantum query complexity of a Boolean function. To prove this algorithm correct, we develop a theory of limited-precision representation of unitary operators, building on work of Bernstein and Vazirani.


title: Distributed Broadcast in Wireless Networks with Unknown Topology

abstract: A multi-hop synchronous wirelss network is said to be unknown if the nodes have no knowledge of the topology. A basic task in wireless network is that of broadcasting a message (created by a fixed source node) to all nodes of the network. The multi-broadcast that consists in performing a set of r independent broadcasts. In this paper, we study the completion and the termination time of distributed protocols for both the (single) broadcast and the multi-broadcast operations on unknown networks as functions of the number of nodes n, the maximum eccentricity D, the maximum in-degree Delta, and the congestion c of the networks. We establish new connections between these operations and some combinatorial concepts, such as selective families, strongly-selective families (also known as superimposed codes), and pairwise r-different families. Such connections, combined with a set of new lower and upper bounds on the size of the above families, allow us to derive new lower bounds and new distributed protocols for the broadcast and multi-broadcast operations. In particular, our upper bounds are almost tight and improve exponentially over the previous bounds when D and Delta are polylogarithmic in n. Network topologies having ``small'' eccentricity and ``small'' degree (such as bounded-degree expanders) are often used in practice to achieve efficient communication.


title: Three-Stage Quantitative Neural Network Model of the Tip-of-the-Tongue Phenomenon

abstract: A new three-stage computer artificial neural network model of the tip-of-the-tongue phenomenon is shortly described, and its stochastic nature was demonstrated. A way to calculate strength and appearance probability of tip-of-the-tongue states, neural network mechanism of feeling-of-knowing phenomenon are proposed. The model synthesizes memory, psycholinguistic, and metamemory approaches, bridges speech errors and naming chronometry research traditions. A model analysis of a tip-of-the-tongue case from Anton Chekhov's short story 'A Horsey Name' is performed. A new 'throw-up-one's-arms effect' is defined.


title: The Logic Programming Paradigm and Prolog

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


title: Transformations of CCP programs

abstract: We introduce a transformation system for concurrent constraint programming (CCP). We define suitable applicability conditions for the transformations which guarantee that the input/output CCP semantics is preserved also when distinguishing deadlocked computations from successful ones and when considering intermediate results of (possibly) non-terminating computations. The system allows us to optimize CCP programs while preserving their intended meaning: In addition to the usual benefits that one has for sequential declarative languages, the transformation of concurrent programs can also lead to the elimination of communication channels and of synchronization points, to the transformation of non-deterministic computations into deterministic ones, and to the crucial saving of computational space. Furthermore, since the transformation system preserves the deadlock behavior of programs, it can be used for proving deadlock freeness of a given program wrt a class of queries. To this aim it is sometimes sufficient to apply our transformations and to specialize the resulting program wrt the given queries in such a way that the obtained program is trivially deadlock free.


title: From Neel to NPC: Colouring Small Worlds

abstract: In this note, we present results for the colouring problem on small world graphs created by rewiring square, triangular, and two kinds of cubic (with coordination numbers 5 and 6) lattices. As the rewiring parameter p tends to 1, we find the expected crossover to the behaviour of random graphs with corresponding connectivity. However, for the cubic lattices there is a region near p=0 for which the graphs are colourable. This could in principle be used as an additional heuristic for solving real world colouring or scheduling problems. Small worlds with connectivity 5 and p ~ 0.1 provide an interesting ensemble of graphs whose colourability is hard to determine. For square lattices, we get good data collapse plotting the fraction of colourable graphs against the rescaled parameter parameter $p N^{-\nu}$ with $\nu = 1.35$. No such collapse can be obtained for the data from lattices with coordination number 5 or 6.


title: Introduction to the CoNLL-2001 Shared Task: Clause Identification

abstract: We describe the CoNLL-2001 shared task: dividing text into clauses. We give background information on the data sets, present a general overview of the systems that have taken part in the shared task and briefly discuss their performance.


title: Learning Computational Grammars

abstract: This paper reports on the "Learning Computational Grammars" (LCG) project, a postdoc network devoted to studying the application of machine learning techniques to grammars suitable for computational use. We were interested in a more systematic survey to understand the relevance of many factors to the success of learning, esp. the availability of annotated data, the kind of dependencies in the data, and the availability of knowledge bases (grammars). We focused on syntax, esp. noun phrase (NP) syntax.


title: Combining a self-organising map with memory-based learning

abstract: Memory-based learning (MBL) has enjoyed considerable success in corpus-based natural language processing (NLP) tasks and is thus a reliable method of getting a high-level of performance when building corpus-based NLP systems. However there is a bottleneck in MBL whereby any novel testing item has to be compared against all the training items in memory base. For this reason there has been some interest in various forms of memory editing whereby some method of selecting a subset of the memory base is employed to reduce the number of comparisons. This paper investigates the use of a modified self-organising map (SOM) to select a subset of the memory items for comparison. This method involves reducing the number of comparisons to a value proportional to the square root of the number of training items. The method is tested on the identification of base noun-phrases in the Wall Street Journal corpus, using sections 15 to 18 for training and section 20 for testing.


title: Applying Natural Language Generation to Indicative Summarization

abstract: The task of creating indicative summaries that help a searcher decide whether to read a particular document is a difficult task. This paper examines the indicative summarization task from a generation perspective, by first analyzing its required content via published guidelines and corpus analysis. We show how these summaries can be factored into a set of document features, and how an implemented content planner uses the topicality document feature to create indicative multidocument query-based summaries.


title: Transformation-Based Learning in the Fast Lane

abstract: Transformation-based learning has been successfully employed to solve many natural language processing problems. It achieves state-of-the-art performance on many natural language processing tasks and does not overtrain easily. However, it does have a serious drawback: the training time is often intorelably long, especially on the large corpora which are often used in NLP. In this paper, we present a novel and realistic method for speeding up the training time of a transformation-based learner without sacrificing performance. The paper compares and contrasts the training time needed and performance achieved by our modified learner with two other systems: a standard transformation-based learner, and the ICA system \cite{hepple00:tbl}. The results of these experiments show that our system is able to achieve a significant improvement in training time while still achieving the same performance as a standard transformation-based learner. This is a valuable contribution to systems and algorithms which utilize transformation-based learning at any part of the execution.


title: Multidimensional Transformation-Based Learning

abstract: This paper presents a novel method that allows a machine learning algorithm following the transformation-based learning paradigm \cite{brill95:tagging} to be applied to multiple classification tasks by training jointly and simultaneously on all fields. The motivation for constructing such a system stems from the observation that many tasks in natural language processing are naturally composed of multiple subtasks which need to be resolved simultaneously; also tasks usually learned in isolation can possibly benefit from being learned in a joint framework, as the signals for the extra tasks usually constitute inductive bias. The proposed algorithm is evaluated in two experiments: in one, the system is used to jointly predict the part-of-speech and text chunks/baseNP chunks of an English corpus; and in the second it is used to learn the joint prediction of word segment boundaries and part-of-speech tagging for Chinese. The results show that the simultaneous learning of multiple tasks does achieve an improvement in each task upon training the same tasks sequentially. The part-of-speech tagging result of 96.63% is state-of-the-art for individual systems on the particular train/test split.


title: An interactive semantics of logic programming

abstract: We apply to logic programming some recently emerging ideas from the field of reduction-based communicating systems, with the aim of giving evidence of the hidden interactions and the coordination mechanisms that rule the operational machinery of such a programming paradigm. The semantic framework we have chosen for presenting our results is tile logic, which has the advantage of allowing a uniform treatment of goals and observations and of applying abstract categorical tools for proving the results. As main contributions, we mention the finitary presentation of abstract unification, and a concurrent and coordinated abstract semantics consistent with the most common semantics of logic programming. Moreover, the compositionality of the tile semantics is guaranteed by standard results, as it reduces to check that the tile systems associated to logic programs enjoy the tile decomposition property. An extension of the approach for handling constraint systems is also discussed.


title: Vertex-Unfoldings of Simplicial Polyhedra

abstract: We present two algorithms for unfolding the surface of any polyhedron, all of whose faces are triangles, to a nonoverlapping, connected planar layout. The surface is cut only along polyhedron edges. The layout is connected, but it may have a disconnected interior: the triangles are connected at vertices, but not necessarily joined along edges.


title: Enumerating Foldings and Unfoldings between Polygons and Polytopes

abstract: We pose and answer several questions concerning the number of ways to fold a polygon to a polytope, and how many polytopes can be obtained from one polygon; and the analogous questions for unfolding polytopes to polygons. Our answers are, roughly: exponentially many, or nondenumerably infinite.


title: Computer validated proofs of a toolset for adaptable arithmetic

abstract: Most existing implementations of multiple precision arithmetic demand that the user sets the precision {\em a priori}. Some libraries are said adaptable in the sense that they dynamically change the precision of each intermediate operation individually to deliver the target accuracy according to the actual inputs. We present in this text a new adaptable numeric core inspired both from floating point expansions and from on-line arithmetic. The numeric core is cut down to four tools. The tool that contains arithmetic operations is proved to be correct. The proofs have been formally checked by the Coq assistant. Developing the proofs, we have formally proved many results published in the literature and we have extended a few of them. This work may let users (i) develop application specific adaptable libraries based on the toolset and / or (ii) write new formal proofs based on the set of validated facts.


title: Annotated revision programs

abstract: Revision programming is a formalism to describe and enforce updates of belief sets and databases. That formalism was extended by Fitting who assigned annotations to revision atoms. Annotations provide a way to quantify the confidence (probability) that a revision atom holds. The main goal of our paper is to reexamine the work of Fitting, argue that his semantics does not always provide results consistent with intuition, and to propose an alternative treatment of annotated revision programs. Our approach differs from that proposed by Fitting in two key aspects: we change the notion of a model of a program and we change the notion of a justified revision. We show that under this new approach fundamental properties of justified revisions of standard revision programs extend to the annotated case.


title: Fixed-parameter complexity of semantics for logic programs

abstract: A decision problem is called parameterized if its input is a pair of strings. One of these strings is referred to as a parameter. The problem: given a propositional logic program P and a non-negative integer k, decide whether P has a stable model of size no more than k, is an example of a parameterized decision problem with k serving as a parameter. Parameterized problems that are NP-complete often become solvable in polynomial time if the parameter is fixed. The problem to decide whether a program P has a stable model of size no more than k, where k is fixed and not a part of input, can be solved in time O(mn^k), where m is the size of P and n is the number of atoms in P. Thus, this problem is in the class P. However, algorithms with the running time given by a polynomial of order k are not satisfactory even for relatively small values of k. The key question then is whether significantly better algorithms (with the degree of the polynomial not dependent on k) exist. To tackle it, we use the framework of fixed-parameter complexity. We establish the fixed-parameter complexity for several parameterized decision problems involving models, supported models and stable models of logic programs. We also establish the fixed-parameter complexity for variants of these problems resulting from restricting attention to Horn programs and to purely negative programs. Most of the problems considered in the paper have high fixed-parameter complexity. Thus, it is unlikely that fixing bounds on models (supported models, stable models) will lead to fast algorithms to decide the existence of such models.


title: Propositional satisfiability in answer-set programming

abstract: We show that propositional logic and its extensions can support answer-set programming in the same way stable logic programming and disjunctive logic programming do. To this end, we introduce a logic based on the logic of propositional schemata and on a version of the Closed World Assumption. We call it the extended logic of propositional schemata with CWA (PS+, in symbols). An important feature of this logic is that it supports explicit modeling of constraints on cardinalities of sets. In the paper, we characterize the class of problems that can be solved by finite PS+ theories. We implement a programming system based on the logic PS+ and design and implement a solver for processing theories in PS+. We present encouraging performance results for our approach --- we show it to be competitive with smodels, a state-of-the-art answer-set programming system based on stable logic programming.


title: aspps --- an implementation of answer-set programming with propositional schemata

abstract: We present an implementation of an answer-set programming paradigm, called aspps (short for answer-set programming with propositional schemata). The system aspps is designed to process PS+ theories. It consists of two basic modules. The first module, psgrnd, grounds an PS+ theory. The second module, referred to as aspps, is a solver. It computes models of ground PS+ theories.


title: Reconciliation of a Quantum-Distributed Gaussian Key

abstract: Two parties, Alice and Bob, wish to distill a binary secret key out of a list of correlated variables that they share after running a quantum key distribution protocol based on continuous-spectrum quantum carriers. We present a novel construction that allows the legitimate parties to get equal bit strings out of correlated variables by using a classical channel, with as few leaked information as possible. This opens the way to securely correcting non-binary key elements. In particular, the construction is refined to the case of Gaussian variables as it applies directly to recent continuous-variable protocols for quantum key distribution.


title: The Complexity of Clickomania

abstract: We study a popular puzzle game known variously as Clickomania and Same Game. Basically, a rectangular grid of blocks is initially colored with some number of colors, and the player repeatedly removes a chosen connected monochromatic group of at least two square blocks, and any blocks above it fall down. We show that one-column puzzles can be solved, i.e., the maximum possible number of blocks can be removed, in linear time for two colors, and in polynomial time for an arbitrary number of colors. On the other hand, deciding whether a puzzle is solvable (all blocks can be removed) is NP-complete for two columns and five colors, or five columns and three colors.


title: Coupled Clustering: a Method for Detecting Structural Correspondence

abstract: This paper proposes a new paradigm and computational framework for identification of correspondences between sub-structures of distinct composite systems. For this, we define and investigate a variant of traditional data clustering, termed coupled clustering, which simultaneously identifies corresponding clusters within two data sets. The presented method is demonstrated and evaluated for detecting topical correspondences in textual corpora.


title: Yet another zeta function and learning

abstract: We study the convergence speed of the batch learning algorithm, and compare its speed to that of the memoryless learning algorithm and of learning with memory (as analyzed in joint work with N. Komarova). We obtain precise results and show in particular that the batch learning algorithm is never worse than the memoryless learning algorithm (at least asymptotically). Its performance vis-a-vis learning with full memory is less clearcut, and depends on certainprobabilistic assumptions. These results necessitate theintroduction of the moment zeta function of a probability distribution and the study of some of its properties.


title: NEOS Server 4.0 Administrative Guide

abstract: The NEOS Server 4.0 provides a general Internet-based client/server as a link between users and software applications. The administrative guide covers the fundamental principals behind the operation of the NEOS Server, installation and trouble-shooting of the Server software, and implementation details of potential interest to a NEOS Server administrator. The guide also discusses making new software applications available through the Server, including areas of concern to remote solver administrators such as maintaining security, providing usage instructions, and enforcing reasonable restrictions on jobs. The administrative guide is intended both as an introduction to the NEOS Server and as a reference for use when running the Server.


title: Semantic Web Content Accessibility Guidelines for Current Research Information Systems (CRIS)

abstract: The most exciting challenge for CRIS is to create a service for research information which should be wide-spread, distributed and actual like Google, but at the same time structured, trusted, with a complex search and navigation similar to today CRIS application. The core technology for such a "new" CRIS is the semantic web technology to integrate database contents with HTML and XML web pages for being provided to the research interested public. One (at the moment the best) possible way is to use RDF (Resource Description Framework) which is also recommended by the W3 consortium.


title: TeXmacs interfaces to Maxima, MuPAD and REDUCE

abstract: GNU TeXmacs is a free wysiwyg word processor providing an excellent typesetting quality of texts and formulae. It can also be used as an interface to Computer Algebra Systems (CASs). In the present work, interfaces to three general-purpose CASs have been implemented.


title: The Cactus Worm: Experiments with Dynamic Resource Discovery and Allocation in a Grid Environment

abstract: The ability to harness heterogeneous, dynamically available "Grid" resources is attractive to typically resource-starved computational scientists and engineers, as in principle it can increase, by significant factors, the number of cycles that can be delivered to applications. However, new adaptive application structures and dynamic runtime system mechanisms are required if we are to operate effectively in Grid environments. In order to explore some of these issues in a practical setting, we are developing an experimental framework, called Cactus, that incorporates both adaptive application structures for dealing with changing resource characteristics and adaptive resource selection mechanisms that allow applications to change their resource allocations (e.g., via migration) when performance falls outside specified limits. We describe here the adaptive resource selection mechanisms and describe how they are used to achieve automatic application migration to "better" resources following performance degradation. Our results provide insights into the architectural structures required to support adaptive resource selection. In addition, we suggest that this "Cactus Worm" is an interesting challenge problem for Grid computing.


title: Bounded Concurrent Timestamp Systems Using Vector Clocks

abstract: Shared registers are basic objects used as communication mediums in asynchronous concurrent computation. A concurrent timestamp system is a higher typed communication object, and has been shown to be a powerful tool to solve many concurrency control problems. It has turned out to be possible to construct such higher typed objects from primitive lower typed ones. The next step is to find efficient constructions. We propose a very efficient wait-free construction of bounded concurrent timestamp systems from 1-writer multireader registers. This finalizes, corrects, and extends, a preliminary bounded multiwriter construction proposed by the second author in 1986. That work partially initiated the current interest in wait-free concurrent objects, and introduced a notion of discrete vector clocks in distributed algorithms.


title: The Partial Evaluation Approach to Information Personalization

abstract: Information personalization refers to the automatic adjustment of information content, structure, and presentation tailored to an individual user. By reducing information overload and customizing information access, personalization systems have emerged as an important segment of the Internet economy. This paper presents a systematic modeling methodology - PIPE (`Personalization is Partial Evaluation') - for personalization. Personalization systems are designed and implemented in PIPE by modeling an information-seeking interaction in a programmatic representation. The representation supports the description of information-seeking activities as partial information and their subsequent realization by partial evaluation, a technique for specializing programs. We describe the modeling methodology at a conceptual level and outline representational choices. We present two application case studies that use PIPE for personalizing web sites and describe how PIPE suggests a novel evaluation criterion for information system designs. Finally, we mention several fundamental implications of adopting the PIPE model for personalization and when it is (and is not) applicable.


title: Links tell us about lexical and semantic Web content

abstract: The latest generation of Web search tools is beginning to exploit hypertext link information to improve ranking\cite{Brin98,Kleinberg98} and crawling\cite{Menczer00,Ben-Shaul99etal,Chakrabarti99} algorithms. The hidden assumption behind such approaches, a correlation between the graph structure of the Web and its content, has not been tested explicitly despite increasing research on Web topology\cite{Lawrence98,Albert99,Adamic99,Butler00}. Here I formalize and quantitatively validate two conjectures drawing connections from link information to lexical and semantic Web content. The clink-content conjecture states that a page is similar to the pages that link to it, i.e., one can infer the lexical content of a page by looking at the pages that link to it. I also show that lexical inferences based on link cues are quite heterogeneous across Web communities. The link-cluster conjecture states that pages about the same topic are clustered together, i.e., one can infer the meaning of a page by looking at its neighbours. These results explain the success of the newest search technologies and open the way for more dynamic and scalable methods to locate information in a topic or user driven way.


title: A Bit of Progress in Language Modeling

abstract: In the past several years, a number of different language modeling improvements over simple trigram models have been found, including caching, higher-order n-grams, skipping, interpolated Kneser-Ney smoothing, and clustering. We present explorations of variations on, or of the limits of, each of these techniques, including showing that sentence mixture models may have more potential. While all of these techniques have been studied separately, they have rarely been studied in combination. We find some significant interactions, especially with smoothing and clustering techniques. We compare a combination of all techniques together to a Katz smoothed trigram model with no count cutoffs. We achieve perplexity reductions between 38% and 50% (1 bit of entropy), depending on training data size, as well as a word error rate reduction of 8.9%. Our perplexity reductions are perhaps the highest reported compared to a fair baseline. This is the extended version of the paper; it contains additional details and proofs, and is designed to be a good introduction to the state of the art in language modeling.


title: Classes for Fast Maximum Entropy Training

abstract: Maximum entropy models are considered by many to be one of the most promising avenues of language modeling research. Unfortunately, long training times make maximum entropy research difficult. We present a novel speedup technique: we change the form of the model to use classes. Our speedup works by creating two maximum entropy models, the first of which predicts the class of each word, and the second of which predicts the word itself. This factoring of the model leads to fewer non-zero indicator functions, and faster normalization, achieving speedups of up to a factor of 35 over one of the best previous techniques. It also results in typically slightly lower perplexities. The same trick can be used to speed training of other machine learning techniques, e.g. neural networks, applied to any problem with a large number of outputs, such as language modeling.


title: Abstract versus Concrete Computation on Metric Partial Algebras

abstract: A model of computation is abstract if, when applied to any algebra, the resulting programs for computable functions and sets on that algebra are invariant under isomorphisms, and hence do not depend on a representation for the algebra. Otherwise it is concrete. Intuitively, concrete models depend on the implementation of the algebra. The difference is particularly striking in the case of topological partial algebras, and notably in algebras over the reals. We investigate the relationship between abstract and concrete models of partial metric algebras. In the course of this investigation, interesting aspects of continuity, extensionality and non-determinism are uncovered.


title: Using Methods of Declarative Logic Programming for Intelligent Information Agents

abstract: The search for information on the web is faced with several problems, which arise on the one hand from the vast number of available sources, and on the other hand from their heterogeneity. A promising approach is the use of multi-agent systems of information agents, which cooperatively solve advanced information-retrieval problems. This requires capabilities to address complex tasks, such as search and assessment of sources, query planning, information merging and fusion, dealing with incomplete information, and handling of inconsistency. In this paper, our interest is in the role which some methods from the field of declarative logic programming can play in the realization of reasoning capabilities for information agents. In particular, we are interested in how they can be used and further developed for the specific needs of this application domain. We review some existing systems and current projects, which address information-integration problems. We then focus on declarative knowledge-representation methods, and review and evaluate approaches from logic programming and nonmonotonic reasoning for information agents. We discuss advantages and drawbacks, and point out possible extensions and open issues.


title: Artificial Neurons with Arbitrarily Complex Internal Structures

abstract: Artificial neurons with arbitrarily complex internal structure are introduced. The neurons can be described in terms of a set of internal variables, a set activation functions which describe the time evolution of these variables and a set of characteristic functions which control how the neurons interact with one another. The information capacity of attractor networks composed of these generalized neurons is shown to reach the maximum allowed bound. A simple example taken from the domain of pattern recognition demonstrates the increased computational power of these neurons. Furthermore, a specific class of generalized neurons gives rise to a simple transformation relating attractor networks of generalized neurons to standard three layer feed-forward networks. Given this correspondence, we conjecture that the maximum information capacity of a three layer feed-forward network is 2 bits per weight.


title: A Note on Tiling under Tomographic Constraints

abstract: Given a tiling of a 2D grid with several types of tiles, we can count for every row and column how many tiles of each type it intersects. These numbers are called the_projections_. We are interested in the problem of reconstructing a tiling which has given projections. Some simple variants of this problem, involving tiles that are 1x1 or 1x2 rectangles, have been studied in the past, and were proved to be either solvable in polynomial time or NP-complete. In this note we make progress toward a comprehensive classification of various tiling reconstruction problems, by proving NP-completeness results for several sets of tiles.


title: On Classes of Functions for which No Free Lunch Results Hold

abstract: In a recent paper it was shown that No Free Lunch results hold for any subset F of the set of all possible functions from a finite set X to a finite set Y iff F is closed under permutation of X. In this article, we prove that the number of those subsets can be neglected compared to the overall number of possible subsets. Further, we present some arguments why problem classes relevant in practice are not likely to be closed under permutation.


title: A polynomial axles-detection algorithm for a four-contacts treadle

abstract: This submission was removed because it contained proprietary information that was distributed without permission.


title: Convergent Approximate Solving of First-Order Constraints by Approximate Quantifiers

abstract: Exactly solving first-order constraints (i.e., first-order formulas over a certain predefined structure) can be a very hard, or even undecidable problem. In continuous structures like the real numbers it is promising to compute approximate solutions instead of exact ones. However, the quantifiers of the first-order predicate language are an obstacle to allowing approximations to arbitrary small error bounds. In this paper we solve the problem by modifying the first-order language and replacing the classical quantifiers with approximate quantifiers. These also have two additional advantages: First, they are tunable, in the sense that they allow the user to decide on the trade-off between precision and efficiency. Second, they introduce additional expressivity into the first-order language by allowing reasoning over the size of solution sets.


title: What's Fit To Print: The Effect Of Ownership Concentration On Product Variety In Daily Newspaper Markets

abstract: This paper examines the effect of ownership concentration on product position, product variety and readership in markets for daily newspapers. US antitrust policy presumes that mergers reduce the amount and diversity of content available to consumers. However, the effects of consolidation in differentiated product markets cannot be determined solely from theory. Because multi-product firms internalize business stealing, mergers may encourage firms to reposition products, leading to more, not less, variety. Using data on reporter assignments from 1993-1999, results show that differentiation and variety increase with concentration. Moreover, there is evidence that additional variety increases readership, suggesting that concentration benefits consumers.


title: Spiders and Crawlers and Bots, Oh My: The Economic Efficiency and Public Policy of Contracts that Restrict Data Collection

abstract: Recent trends reveal the search by companies for a legal hook to prevent the undesired and unauthorized copying of information posted on websites. In the center of this controversy are metasites, websites that display prices for a variety of vendors. Metasites function by implementing shopbots, which extract pricing data from other vendors' websites. Technological mechanisms have proved unsuccessful in blocking shopbots, and in response, websites have asserted a variety of legal claims. Two recent cases, which rely on the troublesome trespass to chattels doctrine, suggest that contract law may provide a less demanding legal method of preventing the search of websites by data robots. If blocking collection of pricing data is as simple as posting an online contract, the question arises whether this end result is desirable and legally viable.


title: Verifying Sequential Consistency on Shared-Memory Multiprocessors by Model Checking

abstract: The memory model of a shared-memory multiprocessor is a contract between the designer and programmer of the multiprocessor. The sequential consistency memory model specifies a total order among the memory (read and write) events performed at each processor. A trace of a memory system satisfies sequential consistency if there exists a total order of all memory events in the trace that is both consistent with the total order at each processor and has the property that every read event to a location returns the value of the last write to that location. Descriptions of shared-memory systems are typically parameterized by the number of processors, the number of memory locations, and the number of data values. It has been shown that even for finite parameter values, verifying sequential consistency on general shared-memory systems is undecidable. We observe that, in practice, shared-memory systems satisfy the properties of causality and data independence. Causality is the property that values of read events flow from values of write events. Data independence is the property that all traces can be generated by renaming data values from traces where the written values are distinct from each other. If a causal and data independent system also has the property that the logical order of write events to each location is identical to their temporal order, then sequential consistency can be verified algorithmically. Specifically, we present a model checking algorithm to verify sequential consistency on such systems for a finite number of processors and memory locations and an arbitrary number of data values.


title: Security Considerations for Remote Electronic Voting over the Internet

abstract: This paper discusses the security considerations for remote electronic voting in public elections. In particular, we examine the feasibility of running national federal elections over the Internet. The focus of this paper is on the limitations of the current deployed infrastructure in terms of the security of the hosts and the Internet itself. We conclude that at present, our infrastructure is inadequate for remote Internet voting.


title: Bipartite graph partitioning and data clustering

abstract: Many data types arising from data mining applications can be modeled as bipartite graphs, examples include terms and documents in a text corpus, customers and purchasing items in market basket analysis and reviewers and movies in a movie recommender system. In this paper, we propose a new data clustering method based on partitioning the underlying bipartite graph. The partition is constructed by minimizing a normalized sum of edge weights between unmatched pairs of vertices of the bipartite graph. We show that an approximate solution to the minimization problem can be obtained by computing a partial singular value decomposition (SVD) of the associated edge weight matrix of the bipartite graph. We point out the connection of our clustering algorithm to correspondence analysis used in multivariate analysis. We also briefly discuss the issue of assigning data objects to multiple clusters. In the experimental results, we apply our clustering algorithm to the problem of document clustering to illustrate its effectiveness and efficiency.


title: Scalable Unix Commands for Parallel Processors: A High-Performance Implementation

abstract: We describe a family of MPI applications we call the Parallel Unix Commands. These commands are natural parallel versions of common Unix user commands such as ls, ps, and find, together with a few similar commands particular to the parallel environment. We describe the design and implementation of these programs and present some performance results on a 256-node Linux cluster. The Parallel Unix Commands are open source and freely available.


title: Flipping Cubical Meshes

abstract: We define and examine flip operations for quadrilateral and hexahedral meshes, similar to the flipping transformations previously used in triangular and tetrahedral mesh generation.


title: Computational Geometry Column 42

abstract: A compendium of thirty previously published open problems in computational geometry is presented.


title: Portability of Syntactic Structure for Language Modeling

abstract: The paper presents a study on the portability of statistical syntactic knowledge in the framework of the structured language model (SLM). We investigate the impact of porting SLM statistics from the Wall Street Journal (WSJ) to the Air Travel Information System (ATIS) domain. We compare this approach to applying the Microsoft rule-based parser (NLPwin) for the ATIS data and to using a small amount of data manually parsed at UPenn for gathering the intial SLM statistics. Surprisingly, despite the fact that it performs modestly in perplexity (PPL), the model initialized on WSJ parses outperforms the other initialization methods based on in-domain annotated data, achieving a significant 0.4% absolute and 7% relative reduction in word error rate (WER) over a baseline system whose word error rate is 5.8%; the improvement measured relative to the minimum WER achievable on the N-best lists we worked with is 12%.


title: Information Extraction Using the Structured Language Model

abstract: The paper presents a data-driven approach to information extraction (viewed as template filling) using the structured language model (SLM) as a statistical parser. The task of template filling is cast as constrained parsing using the SLM. The model is automatically trained from a set of sentences annotated with frame/slot labels and spans. Training proceeds in stages: first a constrained syntactic parser is trained such that the parses on training data meet the specified semantic spans, then the non-terminal labels are enriched to contain semantic information and finally a constrained syntactic+semantic parser is trained on the parse trees resulting from the previous stage. Despite the small amount of training data used, the model is shown to outperform the slot level accuracy of a simple semantic grammar authored manually for the MiPad --- personal information management --- task.


title: Abstract Computability, Algebraic Specification and Initiality

abstract: computable functions are defined by abstract finite deterministic algorithms on many-sorted algebras. We show that there exist finite universal algebraic specifications that specify uniquely (up to isomorphism) (i) all abstract computable functions on any many-sorted algebra; and (ii) all functions effectively approximable by abstract computable functions on any metric algebra. We show that there exist universal algebraic specifications for all the classically computable functions on the set R of real numbers. The algebraic specifications used are mainly bounded universal equations and conditional equations. We investigate the initial algebra semantics of these specifications, and derive situations where algebraic specifications define precisely the computable functions.


title: Probabilistic asynchronous pi-calculus

abstract: We propose an extension of the asynchronous pi-calculus with a notion of random choice. We define an operational semantics which distinguishes between probabilistic choice, made internally by the process, and nondeterministic choice, made externally by an adversary scheduler. This distinction will allow us to reason about the probabilistic correctness of algorithms under certain schedulers. We show that in this language we can solve the electoral problem, which was proved not possible in the asynchronous $\pi$-calculus. Finally, we show an implementation of the probabilistic asynchronous pi-calculus in a Java-like language.


title: On the generalized dining philosophers problem

abstract: We consider a generalization of the dining philosophers problem to arbitrary connection topologies. We focus on symmetric, fully distributed systems, and we address the problem of guaranteeing progress and lockout-freedom, even in presence of adversary schedulers, by using randomized algorithms. We show that the well-known algorithms of Lehmann and Rabin do not work in the generalized case, and we propose an alternative algorithm based on the idea of letting the philosophers assign a random priority to their adjacent forks.


title: Parallel Computing on a PC Cluster

abstract: The tremendous advance in computer technology in the past decade has made it possible to achieve the performance of a supercomputer on a very small budget. We have built a multi-CPU cluster of Pentium PC capable of parallel computations using the Message Passing Interface (MPI). We will discuss the configuration, performance, and application of the cluster to our work in physics.


title: Architectural Framework for Large-Scale Multicast in Mobile Ad Hoc Networks

abstract: Emerging ad hoc networks are infrastructure-less networks consisting of wireless devices with various power constraints, capabilities and mobility characteristics. An essential capability in future ad hoc networks is the ability to provide scalable multicast services. This paper presents a novel adaptive architecture to support multicast services in large-scale wide-area ad hoc networks. Existing works on multicast in ad hoc networks address only small size networks. Our main design goals are scalability, robustness and efficiency. We propose a self-configuring hierarchy extending zone-based routing with the notion of contacts based on the small world graphs phenomenon and new metrics of stability and mobility. We introduce a new geographic-based multicast address allocation scheme coupled with adaptive anycast based on group popularity. Our scheme is the first of its kind and promises efficient and robust operation in the common case. Also, based on the new concept of rendezvous regions, we provide a bootstrap mechanism for the multicast service; a challenge generally ignored in previous work.


title: On Properties of Update Sequences Based on Causal Rejection

abstract: We consider an approach to update nonmonotonic knowledge bases represented as extended logic programs under answer set semantics. New information is incorporated into the current knowledge base subject to a causal rejection principle enforcing that, in case of conflicts, more recent rules are preferred and older rules are overridden. Such a rejection principle is also exploited in other approaches to update logic programs, e.g., in dynamic logic programming by Alferes et al. We give a thorough analysis of properties of our approach, to get a better understanding of the causal rejection principle. We review postulates for update and revision operators from the area of theory change and nonmonotonic reasoning, and some new properties are considered as well. We then consider refinements of our semantics which incorporate a notion of minimality of change. As well, we investigate the relationship to other approaches, showing that our approach is semantically equivalent to inheritance programs by Buccafurri et al. and that it coincides with certain classes of dynamic logic programs, for which we provide characterizations in terms of graph conditions. Therefore, most of our results about properties of causal rejection principle apply to these approaches as well. Finally, we deal with computational complexity of our approach, and outline how the update semantics and its refinements can be implemented on top of existing logic programming engines.


title: Voice vs Data: Estimates of Media Usage and Network Traffic

abstract: The popular conception is that data traffic nearly, if not already, exceeds voice traffic on backbone networks. However, the results of research reported in this paper imply that voice traffic greatly exceeds data traffic when real users are asked to estimate their usage of a wide variety of media. Media usage was surveyed for students in New York City and in Los Angeles. Other than significant differences in radio listening, e-mails, and downloads, the usage was quite similar. Telephone usage (wired and wireless) was nearly an hour per day. When converted to bits, the telephone traffic was much greater than the data traffic over the Internet. This paper reports on the details of the two user studies. The traffic implications of the results are estimated. The finding that voice exceeds data will then be reconciled with the popular opposite conception.


title: The Role of Incentives for Opening Monopoly Markets: Comparing GTE and BOC Cooperation with Local Entrants

abstract: While the 1996 Telecommunications Act requires all incumbent local telephone companies to cooperate with local entrants, section 271 of the Act provides the Bell companies (but not GTE) additional incentives to cooperate. Using an original data set, I compare the negotiations of AT&T, as a local entrant, with GTE and with the Bell companies in states where both operate. My results suggest that the differential incentives matter: The Bells accommodate entry more than does GTE, as evidenced in quicker agreements, less litigation, and more favorable prices offered for network access. Consistent with this, there is more entry into Bell territories