title:
Generalization of a 3-D resonator model for the simulation of spherical
  enclosures

abstract:
  A rectangular enclosure has such an even distribution of resonances that it
can be accurately and efficiently modelled using a feedback delay network.
Conversely, a non rectangular shape such as a sphere has a distribution of
resonances that challenges the construction of an efficient model. This work
proposes an extension of the already known feedback delay network structure to
model the resonant properties of a sphere. A specific frequency distribution of
resonances can be approximated, up to a certain frequency, by inserting an
allpass filter of moderate order after each delay line of a feedback delay
network. The structure used for rectangular boxes is therefore augmented with a
set of allpass filters allowing parametric control over the enclosure size and
the boundary properties. This work was motivated by informal listening tests
which have shown that it is possible to identify a basic shape just from the
distribution of its audible resonances.


title: Internet Packet Filter Management and Rectangle Geometry

abstract:
  We consider rule sets for internet packet routing and filtering, where each
rule consists of a range of source addresses, a range of destination addresses,
a priority, and an action. A given packet should be handled by the action from
the maximum priority rule that matches its source and destination. We describe
new data structures for quickly finding the rule matching an incoming packet,
in near-linear space, and a new algorithm for determining whether a rule set
contains any conflicts, in time O(n^{3/2}).


title: The Random Oracle Methodology, Revisited

abstract:
  We take a critical look at the relationship between the security of
cryptographic schemes in the Random Oracle Model, and the security of the
schemes that result from implementing the random oracle by so called
"cryptographic hash functions". The main result of this paper is a negative
one: There exist signature and encryption schemes that are secure in the Random
Oracle Model, but for which any implementation of the random oracle results in
insecure schemes.
  In the process of devising the above schemes, we consider possible
definitions for the notion of a "good implementation" of a random oracle,
pointing out limitations and challenges.


title:
Using existing systems to supplement small amounts of annotated
  grammatical relations training data

abstract:
  Grammatical relationships (GRs) form an important level of natural language
processing, but different sets of GRs are useful for different purposes.
Therefore, one may often only have time to obtain a small training corpus with
the desired GR annotations. To boost the performance from using such a small
training corpus on a transformation rule learner, we use existing systems that
find related types of annotations.


title:
Towards Understanding the Predictability of Stock Markets from the
  Perspective of Computational Complexity

abstract:
  This paper initiates a study into the century-old issue of market
predictability from the perspective of computational complexity. We develop a
simple agent-based model for a stock market where the agents are traders
equipped with simple trading strategies, and their trades together determine
the stock prices. Computer simulations show that a basic case of this model is
already capable of generating price graphs which are visually similar to the
recent price movements of high tech stocks. In the general model, we prove that
if there are a large number of traders but they employ a relatively small
number of strategies, then there is a polynomial-time algorithm for predicting
future price movements with high accuracy. On the other hand, if the number of
strategies is large, market prediction becomes complete in two new
computational complexity classes CPP and BCPP, which are between P^NP[O(log n)]
and PP. These computational completeness results open up a novel possibility
that the price graph of an actual stock could be sufficiently deterministic for
various prediction goals but appear random to all polynomial-time prediction
algorithms.


title:
Noise-Tolerant Learning, the Parity Problem, and the Statistical Query
  Model

abstract:
  We describe a slightly sub-exponential time algorithm for learning parity
functions in the presence of random classification noise. This results in a
polynomial-time algorithm for the case of parity functions that depend on only
the first O(log n log log n) bits of input. This is the first known instance of
an efficient noise-tolerant algorithm for a concept class that is provably not
learnable in the Statistical Query model of Kearns. Thus, we demonstrate that
the set of problems learnable in the statistical query model is a strict subset
of those problems learnable in the presence of noise in the PAC model.
  In coding-theory terms, what we give is a poly(n)-time algorithm for decoding
linear k by n codes in the presence of random noise for the case of k = c log n
loglog n for some c > 0. (The case of k = O(log n) is trivial since one can
just individually check each of the 2^k possible messages and choose the one
that yields the closest codeword.)
  A natural extension of the statistical query model is to allow queries about
statistical properties that involve t-tuples of examples (as opposed to single
examples). The second result of this paper is to show that any class of
functions learnable (strongly or weakly) with t-wise queries for t = O(log n)
is also weakly learnable with standard unary queries. Hence this natural
extension to the statistical query model does not increase the set of weakly
learnable functions.


title: Oracle Complexity and Nontransitivity in Pattern Recognition

abstract:
  Different mathematical models of recognition processes are known. In the
present paper we consider a pattern recognition algorithm as an oracle
computation on a Turing machine. Such point of view seems to be useful in
pattern recognition as well as in recursion theory. Use of recursion theory in
pattern recognition shows connection between a recognition algorithm comparison
problem and complexity problems of oracle computation. That is because in many
cases we can take into account only the number of sign computations or in other
words volume of oracle information needed. Therefore, the problem of
recognition algorithm preference can be formulated as a complexity optimization
problem of oracle computation. Furthermore, introducing a certain "natural"
preference relation on a set of recognizing algorithms, we discover it to be
nontransitive. This relates to the well known nontransitivity paradox in
probability theory.
  Keywords: Pattern Recognition, Recursion Theory, Nontransitivity, Preference
Relation


title:
Exploring automatic word sense disambiguation with decision lists and
  the Web

abstract:
  The most effective paradigm for word sense disambiguation, supervised
learning, seems to be stuck because of the knowledge acquisition bottleneck. In
this paper we take an in-depth study of the performance of decision lists on
two publicly available corpora and an additional corpus automatically acquired
from the Web, using the fine-grained highly polysemous senses in WordNet.
Decision lists are shown a versatile state-of-the-art technique. The
experiments reveal, among other facts, that SemCor can be an acceptable (0.7
precision for polysemous words) starting point for an all-words system. The
results on the DSO corpus show that for some highly polysemous words 0.7
precision seems to be the current state-of-the-art limit. On the other hand,
independently constructed hand-tagged corpora are not mutually useful, and a
corpus automatically acquired from the Web is shown to fail.


title:
Extraction of semantic relations from a Basque monolingual dictionary
  using Constraint Grammar

abstract:
  This paper deals with the exploitation of dictionaries for the semi-automatic
construction of lexicons and lexical knowledge bases. The final goal of our
research is to enrich the Basque Lexical Database with semantic information
such as senses, definitions, semantic relations, etc., extracted from a Basque
monolingual dictionary. The work here presented focuses on the extraction of
the semantic relations that best characterise the headword, that is, those of
synonymy, antonymy, hypernymy, and other relations marked by specific relators
and derivation. All nominal, verbal and adjectival entries were treated. Basque
uses morphological inflection to mark case, and therefore semantic relations
have to be inferred from suffixes rather than from prepositions. Our approach
combines a morphological analyser and surface syntax parsing (based on
Constraint Grammar), and has proven very successful for highly inflected
languages such as Basque. Both the effort to write the rules and the actual
processing time of the dictionary have been very low. At present we have
extracted 42,533 relations, leaving only 2,943 (9%) definitions without any
extracted relation. The error rate is extremely low, as only 2.2% of the
extracted relations are wrong.


title: Enriching very large ontologies using the WWW

abstract:
  This paper explores the possibility to exploit text on the world wide web in
order to enrich the concepts in existing ontologies. First, a method to
retrieve documents from the WWW related to a concept is described. These
document collections are used 1) to construct topic signatures (lists of
topically related words) for each concept in WordNet, and 2) to build
hierarchical clusters of the concepts (the word senses) that lexicalize a given
word. The overall goal is to overcome two shortcomings of WordNet: the lack of
topical links among concepts, and the proliferation of senses. Topic signatures
are validated on a word sense disambiguation task with good results, which are
improved when the hierarchical clusters are used.


title: One Sense per Collocation and Genre/Topic Variations

abstract:
  This paper revisits the one sense per collocation hypothesis using
fine-grained sense distinctions and two different corpora. We show that the
hypothesis is weaker for fine-grained sense distinctions (70% vs. 99% reported
earlier on 2-way ambiguities). We also show that one sense per collocation does
hold across corpora, but that collocations vary from one corpus to the other,
following genre and topic variations. This explains the low results when
performing word sense disambiguation across corpora. In fact, we demonstrate
that when two independent corpora share a related genre/topic, the word sense
disambiguation results would be better. Future work on word sense
disambiguation will have to take into account genre and topic as important
parameters on their models.


title: Sequence-Based Abstract Interpretation of Prolog

abstract:
  Many abstract interpretation frameworks and analyses for Prolog have been
proposed, which seek to extract information useful for program optimization.
Although motivated by practical considerations, notably making Prolog
competitive with imperative languages, such frameworks fail to capture some of
the control structures of existing implementations of the language.
  In this paper we propose a novel framework for the abstract interpretation of
Prolog which handles the depth-first search rule and the cut operator. It
relies on the notion of substitution sequence to model the result of the
execution of a goal. The framework consists of (i) a denotational concrete
semantics, (ii) a safe abstraction of the concrete semantics defined in terms
of a class of post-fixpoints, and (iii) a generic abstract interpretation
algorithm. We show that traditional abstract domains of substitutions may
easily be adapted to the new framework, and provide experimental evidence of
the effectiveness of our approach. We also show that previous work on
determinacy analysis, that was not expressible by existing abstract
interpretation frameworks, can be seen as an instance of our framework.


title:
Using Modes to Ensure Subject Reduction for Typed Logic Programs with
  Subtyping

abstract:
  We consider a general prescriptive type system with parametric polymorphism
and subtyping for logic programs. The property of subject reduction expresses
the consistency of the type system w.r.t. the execution model: if a program is
"well-typed", then all derivations starting in a "well-typed" goal are again
"well-typed". It is well-established that without subtyping, this property is
readily obtained for logic programs w.r.t. their standard (untyped) execution
model. Here we give syntactic conditions that ensure subject reduction also in
the presence of general subtyping relations between type constructors. The idea
is to consider logic programs with a fixed dataflow, given by modes.


title: Reduction of Intermediate Alphabets in Finite-State Transducer Cascades

abstract:
  This article describes an algorithm for reducing the intermediate alphabets
in cascades of finite-state transducers (FSTs). Although the method modifies
the component FSTs, there is no change in the overall relation described by the
whole cascade. No additional information or special algorithm, that could
decelerate the processing of input, is required at runtime. Two examples from
Natural Language Processing are used to illustrate the effect of the algorithm
on the sizes of the FSTs and their alphabets. With some FSTs the number of arcs
and symbols shrank considerably.


title: Opportunity Cost Algorithms for Combinatorial Auctions

abstract:
  Two general algorithms based on opportunity costs are given for approximating
a revenue-maximizing set of bids an auctioneer should accept, in a
combinatorial auction in which each bidder offers a price for some subset of
the available goods and the auctioneer can only accept non-intersecting bids.
Since this problem is difficult even to approximate in general, the algorithms
are most useful when the bids are restricted to be connected node subsets of an
underlying object graph that represents which objects are relevant to each
other. The approximation ratios of the algorithms depend on structural
properties of this graph and are small constants for many interesting families
of object graphs. The running times of the algorithms are linear in the size of
the bid graph, which describes the conflicts between bids. Extensions of the
algorithms allow for efficient processing of additional constraints, such as
budget constraints that associate bids with particular bidders and limit how
many bids from a particular bidder can be accepted.


title: Super Logic Programs

abstract:
  The Autoepistemic Logic of Knowledge and Belief (AELB) is a powerful
nonmonotic formalism introduced by Teodor Przymusinski in 1994. In this paper,
we specialize it to a class of theories called `super logic programs'. We argue
that these programs form a natural generalization of standard logic programs.
In particular, they allow disjunctions and default negation of arbibrary
positive objective formulas.
  Our main results are two new and powerful characterizations of the static
semant ics of these programs, one syntactic, and one model-theoretic. The
syntactic fixed point characterization is much simpler than the fixed point
construction of the static semantics for arbitrary AELB theories. The
model-theoretic characterization via Kripke models allows one to construct
finite representations of the inherently infinite static expansions.
  Both characterizations can be used as the basis of algorithms for query
answering under the static semantics. We describe a query-answering interpreter
for super programs which we developed based on the model-theoretic
characterization and which is available on the web.


title: A Formal Framework for Linguistic Annotation (revised version)

abstract:
  `Linguistic annotation' covers any descriptive or analytic notations applied
to raw language data. The basic data may be in the form of time functions -
audio, video and/or physiological recordings - or it may be textual. The added
notations may include transcriptions of all sorts (from phonetic features to
discourse structures), part-of-speech and sense tagging, syntactic analysis,
`named entity' identification, co-reference annotation, and so on. While there
are several ongoing efforts to provide formats and tools for such annotations
and to publish annotated linguistic databases, the lack of widely accepted
standards is becoming a critical problem. Proposed standards, to the extent
they exist, have focused on file formats. This paper focuses instead on the
logical structure of linguistic annotations. We survey a wide variety of
existing annotation formats and demonstrate a common conceptual core, the
annotation graph. This provides a formal framework for constructing,
maintaining and searching linguistic annotations, while remaining consistent
with many alternative data structures and file formats.


title: Static Analysis Techniques for Equational Logic Programming

abstract:
  An equational logic program is a set of directed equations or rules, which
are used to compute in the obvious way (by replacing equals with ``simpler''
equals). We present static analysis techniques for efficient equational logic
programming, some of which have been implemented in $LR^2$, a laboratory for
developing and evaluating fast, efficient, and practical rewriting techniques.
Two novel features of $LR^2$ are that non-left-linear rules are allowed in most
contexts and it has a tabling option based on the congruence-closure based
algorithm to compute normal forms. Although, the focus of this research is on
the tabling approach some of the techniques are applicable to the untabled
approach as well. Our presentation is in the context of $LR^2$, which is an
interpreter, but some of the techniques apply to compilation as well.


title:
Proceedings of the Fourth International Workshop on Automated Debugging
  (AADEBUG 2000)

abstract:
  Over the past decades automated debugging has seen major achievements.
However, as debugging is by necessity attached to particular programming
paradigms, the results are scattered. The aims of the workshop are to gather
common themes and solutions across programming communities, and to
cross-fertilize ideas. AADEBUG 2000 in Munich follows AADEBUG'93 in Linkoeping,
Sweden; AADEBUG'95 in Saint Malo, France; AADEBUG'97 in Linkoeping, Sweden.


title: Lattice Structure and Convergence of a Game of Cards

abstract:
  This paper is devoted to the study of the dynamics of a discrete system
related to some self stabilizing protocol on a ring of processors.


title: On the relationship between fuzzy logic and four-valued relevance logic

abstract:
  In fuzzy propositional logic, to a proposition a partial truth in [0,1] is
assigned. It is well known that under certain circumstances, fuzzy logic
collapses to classical logic. In this paper, we will show that under dual
conditions, fuzzy logic collapses to four-valued (relevance) logic, where
propositions have truth-value true, false, unknown, or contradiction. As a
consequence, fuzzy entailment may be considered as ``in between'' four-valued
(relevance) entailment and classical entailment.


title: Collecting Graphical Abstract Views of Mercury Program Executions

abstract:
  A program execution monitor is a program that collects and abstracts
information about program executions. The "collect" operator is a high level,
general purpose primitive which lets users implement their own monitors.
"Collect" is built on top of the Mercury trace. In previous work, we have
demonstrated how this operator can be used to efficiently collect various kinds
of statistics about Mercury program executions. In this article we further
demonstrate the expressive power and effectiveness of "collect" by providing
more monitor examples. In particular, we show how to implement monitors that
generate graphical abstractions of program executions such as proof trees,
control flow graphs and dynamic call graphs. We show how those abstractions can
be easily modified and adapted, since those monitors only require several
dozens of lines of code. Those abstractions are intended to serve as front-ends
of software visualization tools. Although "collect" is currently implemented on
top of the Mercury trace, none of its underlying concepts depend of Mercury and
it can be implemented on top of any tracer for any programming language.


title: Computational Geometry Column 40

abstract:
  It has recently been established by Below, De Loera, and Richter-Gebert that
finding a minimum size (or even just a small) triangulation of a convex
polyhedron is NP-complete. Their 3SAT-reduction proof is discussed.


title:
Utilizing the World Wide Web as an Encyclopedia: Extracting Term
  Descriptions from Semi-Structured Texts

abstract:
  In this paper, we propose a method to extract descriptions of technical terms
from Web pages in order to utilize the World Wide Web as an encyclopedia. We
use linguistic patterns and HTML text structures to extract text fragments
containing term descriptions. We also use a language model to discard
extraneous descriptions, and a clustering method to summarize resultant
descriptions. We show the effectiveness of our method by way of experiments.


title: A Novelty-based Evaluation Method for Information Retrieval

abstract:
  In information retrieval research, precision and recall have long been used
to evaluate IR systems. However, given that a number of retrieval systems
resembling one another are already available to the public, it is valuable to
retrieve novel relevant documents, i.e., documents that cannot be retrieved by
those existing systems. In view of this problem, we propose an evaluation
method that favors systems retrieving as many novel documents as possible. We
also used our method to evaluate systems that participated in the IREX
workshop.


title:
Applying Machine Translation to Two-Stage Cross-Language Information
  Retrieval

abstract:
  Cross-language information retrieval (CLIR), where queries and documents are
in different languages, needs a translation of queries and/or documents, so as
to standardize both of them into a common representation. For this purpose, the
use of machine translation is an effective approach. However, computational
cost is prohibitive in translating large-scale document collections. To resolve
this problem, we propose a two-stage CLIR method. First, we translate a given
query into the document language, and retrieve a limited number of foreign
documents. Second, we machine translate only those documents into the user
language, and re-rank them based on the translation result. We also show the
effectiveness of our method by way of experiments using Japanese queries and
English technical documents.


title: Anonymous Oblivious Transfer

abstract:
  In this short note we want to introduce {\em anonymous oblivious transfer} a
new cryptographic primitive which can be proven to be strictly more powerful
than oblivious transfer. We show that all functions can be robustly realized by
multi party protocols with {\em anonymous oblivious transfer}. No assumption
about possible collusions of cheaters or disruptors have to be made.
Furthermore we shortly discuss how to realize anonymous oblivious transfer with
oblivious broadcast or by quantum cryptography. The protocol of anonymous
oblivious transfer was inspired by a quantum protocol: the anonymous quantum
channel.


title: Non-intrusive on-the-fly data race detection using execution replay

abstract:
  This paper presents a practical solution for detecting data races in parallel
programs. The solution consists of a combination of execution replay (RecPlay)
with automatic on-the-fly data race detection. This combination enables us to
perform the data race detection on an unaltered execution (almost no probe
effect). Furthermore, the usage of multilevel bitmaps and snooped matrix clocks
limits the amount of memory used. As the record phase of RecPlay is highly
efficient, there is no need to switch it off, hereby eliminating the
possibility of Heisenbugs because tracing can be left on all the time.


title: Execution replay and debugging

abstract:
  As most parallel and distributed programs are internally non-deterministic --
consecutive runs with the same input might result in a different program flow
-- vanilla cyclic debugging techniques as such are useless. In order to use
cyclic debugging tools, we need a tool that records information about an
execution so that it can be replayed for debugging. Because recording
information interferes with the execution, we must limit the amount of
information and keep the processing of the information fast. This paper
contains a survey of existing execution replay techniques and tools.


title: Tree-gram Parsing: Lexical Dependencies and Structural Relations

abstract:
  This paper explores the kinds of probabilistic relations that are important
in syntactic disambiguation. It proposes that two widely used kinds of
relations, lexical dependencies and structural relations, have complementary
disambiguation capabilities. It presents a new model based on structural
relations, the Tree-gram model, and reports experiments showing that structural
relations should benefit from enrichment by lexical dependencies.


title: A Lambda-Calculus with letrec, case, constructors and non-determinism

abstract:
  A non-deterministic call-by-need lambda-calculus \calc with case,
constructors, letrec and a (non-deterministic) erratic choice, based on
rewriting rules is investigated. A standard reduction is defined as a variant
of left-most outermost reduction. The semantics is defined by contextual
equivalence of expressions instead of using $\alpha\beta(\eta)$-equivalence. It
is shown that several program transformations are correct, for example all
(deterministic) rules of the calculus, and in addition the rules for garbage
collection, removing indirections and unique copy.
  This shows that the combination of a context lemma and a meta-rewriting on
reductions using complete sets of commuting (forking, resp.) diagrams is a
useful and successful method for providing a semantics of a functional
programming language and proving correctness of program transformations.


title: Small Maximal Independent Sets and Faster Exact Graph Coloring

abstract:
  We show that, for any n-vertex graph G and integer parameter k, there are at
most 3^{4k-n}4^{n-3k} maximal independent sets I \subset G with |I| <= k, and
that all such sets can be listed in time O(3^{4k-n} 4^{n-3k}). These bounds are
tight when n/4 <= k <= n/3. As a consequence, we show how to compute the exact
chromatic number of a graph in time O((4/3 + 3^{4/3}/4)^n) ~= 2.4150^n,
improving a previous O((1+3^{1/3})^n) ~= 2.4422^n algorithm of Lawler (1976).


title: Extension Language Automation of Embedded System Debugging

abstract:
  Embedded systems contain several layers of target processing abstraction.
These layers include electronic circuit, binary machine code, mnemonic assembly
code, and high-level procedural and object-oriented abstractions. Physical and
temporal constraints and artifacts within physically embedded systems make it
impossible for software engineers to operate at a single layer of processor
abstraction. The Luxdbg embedded system debugger exposes these layers to
debugger users, and it adds an additional layer, the extension language layer,
that allows users to extend both the debugger and its target processor
capabilities. Tcl is Luxdbg's extension language. Luxdbg users can apply Tcl to
automate interactive debugging steps, to redirect and to interconnect target
processor input-output facilities, to schedule multiple processor execution, to
log and to react to target processing exceptions, and to automate target system
testing. Inclusion of an extension language like Tcl in a debugger promises
additional advantages for distributed debugging, where debuggers can pass
extension language expressions across computer networks.


title: Formal Properties of XML Grammars and Languages

abstract:
  XML documents are described by a document type definition (DTD). An
XML-grammar is a formal grammar that captures the syntactic features of a DTD.
We investigate properties of this family of grammars. We show that every
XML-language basically has a unique XML-grammar. We give two characterizations
of languages generated by XML-grammars, one is set-theoretic, the other is by a
kind of saturation property. We investigate decidability problems and prove
that some properties that are undecidable for general context-free languages
become decidable for XML-languages. We also characterize those XML-grammars
that generate regular XML-languages.


title: Causes and Explanations: A Structural-Model Approach, Part I: Causes

abstract:
  We propose a new definition of actual cause, using structural equations to
model counterfactuals. We show that the definition yields a plausible and
elegant account of causation that handles well examples which have caused
problems for other definitions and resolves major difficulties in the
traditional account.


title: Transformation-Based Bottom-Up Computation of the Well-Founded Model

abstract:
  We present a framework for expressing bottom-up algorithms to compute the
well-founded model of non-disjunctive logic programs. Our method is based on
the notion of conditional facts and elementary program transformations studied
by Brass and Dix for disjunctive programs. However, even if we restrict their
framework to nondisjunctive programs, their residual program can grow to
exponential size, whereas for function-free programs our program remainder is
always polynomial in the size of the extensional database (EDB).
  We show that particular orderings of our transformations (we call them
strategies) correspond to well-known computational methods like the alternating
fixpoint approach, the well-founded magic sets method and the magic alternating
fixpoint procedure. However, due to the confluence of our calculi, we come up
with computations of the well-founded model that are provably better than these
methods.
  In contrast to other approaches, our transformation method treats magic set
transformed programs correctly, i.e. it always computes a relevant part of the
well-founded model of the original program.


title: Chip-level CMP Modeling and Smart Dummy for HDP and Conformal CVD Films

abstract:
  Chip-level CMP modeling is investigated to obtain the post-CMP film profile
thickness across a die from its design layout file and a few film deposition
and CMP parameters. The work covers both HDP and conformal CVD film. The
experimental CMP results agree well with the modeled results. Different
algorithms for filling of dummy structure are compared. A smart algorithm for
dummy filling is presented, which achieves maximal pattern-density uniformity
and CMP planarity.


title: A Decomposition Theorem for Maximum Weight Bipartite Matchings

abstract:
  Let G be a bipartite graph with positive integer weights on the edges and
without isolated nodes. Let n, N and W be the node count, the largest edge
weight and the total weight of G. Let k(x,y) be log(x)/log(x^2/y). We present a
new decomposition theorem for maximum weight bipartite matchings and use it to
design an O(sqrt(n)W/k(n,W/N))-time algorithm for computing a maximum weight
matching of G. This algorithm bridges a long-standing gap between the best
known time complexity of computing a maximum weight matching and that of
computing a maximum cardinality matching. Given G and a maximum weight matching
of G, we can further compute the weight of a maximum weight matching of G-{u}
for all nodes u in O(W) time.


title: Designing Proxies for Stock Market Indices is Computationally Hard

abstract:
  In this paper, we study the problem of designing proxies (or portfolios) for
various stock market indices based on historical data. We use four different
methods for computing market indices, all of which are formulas used in actual
stock market analysis. For each index, we consider three criteria for designing
the proxy: the proxy must either track the market index, outperform the market
index, or perform within a margin of error of the index while maintaining a low
volatility. In eleven of the twelve cases (all combinations of four indices
with three criteria except the problem of sacrificing return for less
volatility using the price-relative index) we show that the problem is NP-hard,
and hence most likely intractable.


title: Automatic Debugging Support for UML Designs

abstract:
  Design of large software systems requires rigorous application of software
engineering methods covering all phases of the software process. Debugging
during the early design phases is extremely important, because late bug-fixes
are expensive.
  In this paper, we describe an approach which facilitates debugging of UML
requirements and designs. The Unified Modeling Language (UML) is a set of
notations for object-orient design of a software system. We have developed an
algorithm which translates requirement specifications in the form of annotated
sequence diagrams into structured statecharts. This algorithm detects conflicts
between sequence diagrams and inconsistencies in the domain knowledge. After
synthesizing statecharts from sequence diagrams, these statecharts usually are
subject to manual modification and refinement. By using the ``backward''
direction of our synthesis algorithm, we are able to map modifications made to
the statechart back into the requirements (sequence diagrams) and check for
conflicts there. Fed back to the user conflicts detected by our algorithm are
the basis for deductive-based debugging of requirements and domain theory in
very early development stages. Our approach allows to generate explanations on
why there is a conflict and which parts of the specifications are affected.


title:
Optimal Buy-and-Hold Strategies for Financial Markets with Bounded Daily
  Returns

abstract:
  In the context of investment analysis, we formulate an abstract online
computing problem called a planning game and develop general tools for solving
such a game. We then use the tools to investigate a practical buy-and-hold
trading problem faced by long-term investors in stocks. We obtain the unique
optimal static online algorithm for the problem and determine its exact
competitive ratio. We also compare this algorithm with the popular dollar
averaging strategy using actual market data.


title:
A Moment of Perfect Clarity II: Consequences of Sparse Sets Hard for NP
  with Respect to Weak Reductions

abstract:
  This paper discusses advances, due to the work of Cai, Naik, and Sivakumar
and Glasser, in the complexity class collapses that follow if NP has sparse
hard sets under reductions weaker than (full) truth-table reductions.


title: The Use of Instrumentation in Grammar Engineering

abstract:
  This paper explores the usefulness of a technique from software engineering,
code instrumentation, for the development of large-scale natural language
grammars. Information about the usage of grammar rules in test and corpus
sentences is used to improve grammar and testsuite, as well as adapting a
grammar to a specific genre. Results show that less than half of a
large-coverage grammar for German is actually tested by two large testsuites,
and that 10--30% of testing time is redundant. This methodology applied can be
seen as a re-use of grammar writing knowledge for testsuite compilation.


title: On-the-fly Query-Based Debugging with Examples

abstract:
  Program errors are hard to find because of the cause-effect gap between the
time when an error occurs and the time when the error becomes apparent to the
programmer. Although debugging techniques such as conditional and data
breakpoints help to find error causes in simple cases, they fail to effectively
bridge the cause-effect gap in many situations. Query-based debuggers offer
programmers an effective tool that provides instant error alert by continuously
checking inter-object relationships while the debugged program is running. To
enable the query-based debugger in the middle of program execution in a
portable way, we propose efficient Java class file instrumentation and discuss
alternative techniques. Although the on-the-fly debugger has a higher overhead
than a dynamic query-based debugger, it offers additional interactive power and
flexibility while maintaining complete portability. To speed up dynamic query
evaluation, our debugger implemented in portable Java uses a combination of
program instrumentation, load-time code generation, query optimization, and
incremental reevaluation. This paper discusses on-the-fly debugging and
demonstrates the query-based debugger application for debugging Java gas tank
applet as well as SPECjvm98 suite applications.


title: Apache web server execution tracing using Third Eye

abstract:
  Testing of modern software systems that integrate many components developed
by different teams is a difficult task. Third Eye is a framework for tracing
and validating software systems using application domain events. We use formal
descriptions of the constraints between events to identify violations in
execution traces. Third Eye is a flexible and modular framework that can be
used in different products. We present the validation of the Apache Web Server
access policy implementation. The results indicate that our tool is a helpful
addition to software development infrastructure.


title: Optimal Bidding Algorithms Against Cheating in Multiple-Object Auctions

abstract:
  This paper studies some basic problems in a multiple-object auction model
using methodologies from theoretical computer science. We are especially
concerned with situations where an adversary bidder knows the bidding
algorithms of all the other bidders. In the two-bidder case, we derive an
optimal randomized bidding algorithm, by which the disadvantaged bidder can
procure at least half of the auction objects despite the adversary's a priori
knowledge of his algorithm. In the general $k$-bidder case, if the number of
objects is a multiple of $k$, an optimal randomized bidding algorithm is found.
If the $k-1$ disadvantaged bidders employ that same algorithm, each of them can
obtain at least $1/k$ of the objects regardless of the bidding algorithm the
adversary uses. These two algorithms are based on closed-form solutions to
certain multivariate probability distributions. In situations where a
closed-form solution cannot be obtained, we study a restricted class of bidding
algorithms as an approximation to desired optimal algorithms.


title: Algorithms for Rewriting Aggregate Queries Using Views

abstract:
  Queries involving aggregation are typical in database applications. One of
the main ideas to optimize the execution of an aggregate query is to reuse
results of previously answered queries. This leads to the problem of rewriting
aggregate queries using views. Due to a lack of theory, algorithms for this
problem were rather ad-hoc. They were sound, but were not proven to be
complete.
  Recently we have given syntactic characterizations for the equivalence of
aggregate queries and applied them to decide when there exist rewritings.
However, these decision procedures do not lend themselves immediately to an
implementation. In this paper, we present practical algorithms for rewriting
queries with $\COUNT$ and $\SUM$. Our algorithms are sound. They are also
complete for important cases. Our techniques can be used to improve well-known
procedures for rewriting non-aggregate queries. These procedures can then be
adapted to obtain algorithms for rewriting queries with $\MIN$ and $\MAX$. The
algorithms presented are a basis for realizing optimizers that rewrite queries
using views.


title:
Termination analysis of logic programs using acceptability with general
  term orders

abstract:
  We present a new approach to termination analysis of logic programs. The
essence of the approach is that we make use of general term-orderings (instead
of level mappings), like it is done in transformational approaches to logic
program termination analysis, but that 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
term-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 term-orderings
may be easily generated. The advantage over transformational approaches is that
it avoids the transformation step all together.


title: When Can You Fold a Map?

abstract:
  We explore the following problem: given a collection of creases on a piece of
paper, each assigned a folding direction of mountain or valley, is there a flat
folding by a sequence of simple folds? There are several models of simple
folds; the simplest one-layer simple fold rotates a portion of paper about a
crease in the paper by +-180 degrees. We first consider the analogous questions
in one dimension lower -- bending a segment into a flat object -- which lead to
interesting problems on strings. We develop efficient algorithms for the
recognition of simply foldable 1D crease patterns, and reconstruction of a
sequence of simple folds. Indeed, we prove that a 1D crease pattern is
flat-foldable by any means precisely if it is by a sequence of one-layer simple
folds.
  Next we explore simple foldability in two dimensions, and find a surprising
contrast: ``map'' folding and variants are polynomial, but slight
generalizations are NP-complete. Specifically, we develop a linear-time
algorithm for deciding foldability of an orthogonal crease pattern on a
rectangular piece of paper, and prove that it is (weakly) NP-complete to decide
foldability of (1) an orthogonal crease pattern on a orthogonal piece of paper,
(2) a crease pattern of axis-parallel and diagonal (45-degree) creases on a
square piece of paper, and (3) crease patterns without a mountain/valley
assignment.


title: Extended Abstract - Model-Based Debugging of Java Programs

abstract:
  Model-based reasoning is a central concept in current research into
intelligent diagnostic systems. It is based on the assumption that sources of
incorrect behavior in technical devices can be located and identified via the
existence of a model describing the basic properties of components of a certain
application domain. When actual data concerning the misbehavior of a system
composed from such components is available, a domain-independent diagnosis
engine can be used to infer which parts of the system contribute to the
observed behavior. This paper describes the application of the model-based
approach to the debugging of Java programs written in a subset of Java. We show
how a simple dependency model can be derived from a program, demonstrate the
use of the model for debugging and reducing the required user interactions,
give a comparison of the functional dependency model with program slicing, and
finally discuss some current research issues.


title:
Retrieval from Captioned Image Databases Using Natural Language
  Processing

abstract:
  It might appear that natural language processing should improve the accuracy
of information retrieval systems, by making available a more detailed analysis
of queries and documents. Although past results appear to show that this is not
so, if the focus is shifted to short phrases rather than full documents, the
situation becomes somewhat different. The ANVIL system uses a natural language
technique to obtain high accuracy retrieval of images which have been annotated
with a descriptive textual caption. The natural language techniques also allow
additional contextual information to be derived from the relation between the
query and the caption, which can help users to understand the overall
collection of retrieval results. The techniques have been successfully used in
a information retrieval system which forms both a testbed for research and the
basis of a commercial system.


title: Systematic Debugging of Attribute Grammars

abstract:
  Although attribute grammars are commonly used for compiler construction,
little investigation has been conducted on debugging attribute grammars. The
paper proposes two types of systematic debugging methods, an algorithmic
debugging and slice-based debugging, both tailored for attribute grammars. By
means of query-based interaction with the developer, our debugging methods
effectively narrow the potential bug space in the attribute grammar description
and eventually identify the incorrect attribution rule. We have incorporated
this technology in our visual debugging tool called Aki.


title:
Logic Programming Approaches for Representing and Solving Constraint
  Satisfaction Problems: A Comparison

abstract:
  Many logic programming based approaches can be used to describe and solve
combinatorial search problems. On the one hand there is constraint logic
programming which computes a solution as an answer substitution to a query
containing the variables of the constraint satisfaction problem. On the other
hand there are systems based on stable model semantics, abductive systems, and
first order logic model generators which compute solutions as models of some
theory. This paper compares these different approaches from the point of view
of knowledge representation (how declarative are the programs) and from the
point of view of performance (how good are they at solving typical problems).


title:
SimLab 1.1, Software for Sensitivity and Uncertainty Analysis, tool for
  sound modelling

abstract:
  The aim of this paper is to present and describe SimLab 1.1 (Simulation
Laboratory for Uncertainty and Sensitivity Analysis) software designed for
Monte Carlo analysis that is based on performing multiple model evaluations
with probabilistically selected model input. The results of these evaluations
are used to determine both the uncertainty in model predictions and the input
variables that drive this uncertainty. This methodology is essential in
situations where a decision has to be taken based on the model results; typical
examples include risk and emergency management systems, financial analysis and
many others. It is also highly recommended as part of model validation, even
where the models are used for diagnostic purposes, as an element of sound model
building. SimLab allows an exploration of the space of possible alternative
model assumptions and structure on the prediction of the model, thereby testing
both the quality of the model and the robustness of the model based inference.


title: Top-down induction of clustering trees

abstract:
  An approach to clustering is presented that adapts the basic top-down
induction of decision trees method towards clustering. To this aim, it employs
the principles of instance based learning. The resulting methodology is
implemented in the TIC (Top down Induction of Clustering trees) system for
first order clustering. The TIC system employs the first order logical decision
tree representation of the inductive logic programming system Tilde. Various
experiments with TIC are presented, in both propositional and relational
domains.


title: Web Mining Research: A Survey

abstract:
  With the huge amount of information available online, the World Wide Web is a
fertile area for data mining research. The Web mining research is at the cross
road of research from several research communities, such as database,
information retrieval, and within AI, especially the sub-areas of machine
learning and natural language processing. However, there is a lot of confusions
when comparing research efforts from different point of views. In this paper,
we survey the research in the area of Web mining, point out some confusions
regarded the usage of the term Web mining and suggest three Web mining
categories. Then we situate some of the research with respect to these three
categories. We also explore the connection between the Web mining categories
and the related agent paradigm. For the survey, we focus on representation
issues, on the process, on the learning algorithm, and on the application of
the recent works as the criteria. We conclude the paper with some research
issues.


title: Semantic interpretation of temporal information by abductive inference

abstract:
  Besides temporal information explicitly available in verbs and adjuncts, the
temporal interpretation of a text also depends on general world knowledge and
default assumptions. We will present a theory for describing the relation
between, on the one hand, verbs, their tenses and adjuncts and, on the other,
the eventualities and periods of time they represent and their relative
temporal locations.
  The theory is formulated in logic and is a practical implementation of the
concepts described in Ness Schelkens et al. We will show how an abductive
resolution procedure can be used on this representation to extract temporal
information from texts.


title: Abductive reasoning with temporal information

abstract:
  Texts in natural language contain a lot of temporal information, both
explicit and implicit. Verbs and temporal adjuncts carry most of the explicit
information, but for a full understanding general world knowledge and default
assumptions have to be taken into account. We will present a theory for
describing the relation between, on the one hand, verbs, their tenses and
adjuncts and, on the other, the eventualities and periods of time they
represent and their relative temporal locations, while allowing interaction
with general world knowledge.
  The theory is formulated in an extension of first order logic and is a
practical implementation of the concepts described in Van Eynde 2001 and
Schelkens et al. 2000. We will show how an abductive resolution procedure can
be used on this representation to extract temporal information from texts. The
theory presented here is an extension of that in Verdoolaege et al. 2000,
adapted to VanEynde 2001, with a simplified and extended analysis of adjuncts
and with more emphasis on how a model can be constructed.


title:
Automatic Termination Analysis of Programs Containing Arithmetic
  Predicates

abstract:
  For logic programs with arithmetic predicates, showing termination is not
easy, since the usual order for the integers is not well-founded. A new method,
easily incorporated in the TermiLog system for automatic termination analysis,
is presented for showing termination in this case.
  The method consists of the following steps: First, a finite abstract domain
for representing the range of integers is deduced automatically. Based on this
abstraction, abstract interpretation is applied to the program. The result is a
finite number of atoms abstracting answers to queries which are used to extend
the technique of query-mapping pairs. For each query-mapping pair that is
potentially non-terminating, a bounded (integer-valued) termination function is
guessed. If traversing the pair decreases the value of the termination
function, then termination is established. Simple functions often suffice for
each query-mapping pair, and that gives our approach an edge over the classical
approach of using a single termination function for all loops, which must
inevitably be more complicated and harder to guess automatically. It is worth
noting that the termination of McCarthy's 91 function can be shown
automatically using our method.
  In summary, the proposed approach is based on combining a finite abstraction
of the integers with the technique of the query-mapping pairs, and is
essentially capable of dividing a termination proof into several cases, such
that a simple termination function suffices for each case. Consequently, the
whole process of proving termination can be done automatically in the framework
of TermiLog and similar systems.


title:
A syntactical analysis of non-size-increasing polynomial time
  computation

abstract:
  A syntactical proof is given that all functions definable in a certain affine
linear typed lambda-calculus with iteration in all types are polynomial time
computable. The proof provides explicit polynomial bounds that can easily be
calculated.


title:
Provably Fast and Accurate Recovery of Evolutionary Trees through
  Harmonic Greedy Triplets

abstract:
  We give a greedy learning algorithm for reconstructing an evolutionary tree
based on a certain harmonic average on triplets of terminal taxa. After the
pairwise distances between terminal taxa are estimated from sequence data, the
algorithm runs in O(n^2) time using O(n) work space, where n is the number of
terminal taxa. These time and space complexities are optimal in the sense that
the size of an input distance matrix is n^2 and the size of an output tree is
n. Moreover, in the Jukes-Cantor model of evolution, the algorithm recovers the
correct tree topology with high probability using sample sequences of length
polynomial in (1) n, (2) the logarithm of the error probability, and (3) the
inverses of two small parameters.


title: A Complete Characterization of Complete Intersection-Type Theories

abstract:
  We characterize those intersection-type theories which yield complete
intersection-type assignment systems for lambda-calculi, with respect to the
three canonical set-theoretical semantics for intersection-types: the inference
semantics, the simple semantics and the F-semantics. These semantics arise by
taking as interpretation of types subsets of applicative structures, as
interpretation of the intersection constructor set-theoretic inclusion, and by
taking the interpretation of the arrow constructor a' la Scott, with respect to
either any possible functionality set, or the largest one, or the least one.
  These results strengthen and generalize significantly all earlier results in
the literature, to our knowledge, in at least three respects. First of all the
inference semantics had not been considered before. Secondly, the
characterizations are all given just in terms of simple closure conditions on
the preorder relation on the types, rather than on the typing judgments
themselves. The task of checking the condition is made therefore considerably
more tractable. Lastly, we do not restrict attention just to lambda-models, but
to arbitrary applicative structures which admit an interpretation function.
Thus we allow also for the treatment of models of restricted lambda-calculi.
Nevertheless the characterizations we give can be tailored just to the case of
lambda-models.


title: Do All Fragments Count?

abstract:
  We aim at finding the minimal set of fragments which achieves maximal parse
accuracy in Data Oriented Parsing. Experiments with the Penn Wall Street
Journal treebank show that counts of almost arbitrary fragments within parse
trees are important, leading to improved parse accuracy over previous models
tested on this treebank. We isolate a number of dependency relations which
previous models neglect but which contribute to higher parse accuracy.


title: EquiX---A Search and Query Language for XML

abstract:
  EquiX is a search language for XML that combines the power of querying with
the simplicity of searching. Requirements for such languages are discussed and
it is shown that EquiX meets the necessary criteria. Both a graphical abstract
syntax and a formal concrete syntax are presented for EquiX queries. In
addition, the semantics is defined and an evaluation algorithm is presented.
The evaluation algorithm is polynomial under combined complexity.
  EquiX combines pattern matching, quantification and logical expressions to
query both the data and meta-data of XML documents. The result of a query in
EquiX is a set of XML documents. A DTD describing the result documents is
derived automatically from the query.


title: Order-consistent programs are cautiously monotonic

abstract:
  Some normal logic programs under the answer set (stable model) semantics lack
the appealing property of "cautious monotonicity." That is, augmenting a
program with one of its consequences may cause it to lose another of its
consequences. The syntactic condition of "order-consistency" was shown by Fages
to guarantee existence of an answer set. This note establishes that
order-consistent programs are not only consistent, but cautiously monotonic.
  From this it follows that they are also "cumulative." That is, augmenting an
order-consistent with some of its consequences does not alter its consequences.
In fact, as we show, its answer sets remain unchanged.


title: Rewriting Calculus: Foundations and Applications

abstract:
  This thesis is devoted to the study of a calculus that describes the
application of conditional rewriting rules and the obtained results at the same
level of representation. We introduce the rewriting calculus, also called the
rho-calculus, which generalizes the first order term rewriting and
lambda-calculus, and makes possible the representation of the non-determinism.
In our approach the abstraction operator as well as the application operator
are objects of calculus. The result of a reduction in the rewriting calculus is
either an empty set representing the application failure, or a singleton
representing a deterministic result, or a set having several elements
representing a not-deterministic choice of results.
  In this thesis we concentrate on the properties of the rewriting calculus
where a syntactic matching is used in order to bind the variables to their
current values. We define evaluation strategies ensuring the confluence of the
calculus and we show that these strategies become trivial for restrictions of
the general rewriting calculus to simpler calculi like the lambda-calculus. The
rewriting calculus is not terminating in the untyped case but the strong
normalization is obtained for the simply typed calculus.
  In the rewriting calculus extended with an operator allowing to test the
application failure we define terms representing innermost and outermost
normalizations with respect to a set of rewriting rules. By using these terms,
we obtain a natural and concise description of the conditional rewriting.
Finally, starting from the representation of the conditional rewriting rules,
we show how the rewriting calculus can be used to give a semantics to ELAN, a
language based on the application of rewriting rules controlled by strategies.


title: Scaling Up Inductive Logic Programming by Learning from Interpretations

abstract:
  When comparing inductive logic programming (ILP) and attribute-value learning
techniques, there is a trade-off between expressive power and efficiency.
Inductive logic programming techniques are typically more expressive but also
less efficient. Therefore, the data sets handled by current inductive logic
programming systems are small according to general standards within the data
mining community. The main source of inefficiency lies in the assumption that
several examples may be related to each other, so they cannot be handled
independently.
  Within the learning from interpretations framework for inductive logic
programming this assumption is unnecessary, which allows to scale up existing
ILP algorithms. In this paper we explain this learning setting in the context
of relational databases. We relate the setting to propositional data mining and
to the classical ILP setting, and show that learning from interpretations
corresponds to learning from multiple relations and thus extends the
expressiveness of propositional learning, while maintaining its efficiency to a
large extent (which is not the case in the classical ILP setting).
  As a case study, we present two alternative implementations of the ILP system
Tilde (Top-down Induction of Logical DEcision trees): Tilde-classic, which
loads all data in main memory, and Tilde-LDS, which loads the examples one by
one. We experimentally compare the implementations, showing Tilde-LDS can
handle large data sets (in the order of 100,000 examples or 100 MB) and indeed
scales up linearly in the number of examples.


title: Index Assignment for Multichannel Communication under Failure

abstract:
  We consider the problem of multiple description scalar quantizers and
describing the achievable rate-distortion tuples in that setting. We formulate
it as a combinatorial optimization problem of arranging numbers in a matrix to
minimize the maximum difference between the largest and the smallest number in
any row or column. We develop a technique for deriving lower bounds on the
distortion at given channel rates. The approach is constructive, thus allowing
an algorithm that gives a closely matching upper bound. For the case of two
communication channels with equal rates, the bounds coincide, thus giving the
precise lowest achievable distortion at fixed rates. The bounds are within a
small constant for higher number of channels. To the best of our knowledge,
this is the first result concerning systems with more than two communication
channels. The problem is also equivalent to the bandwidth minimization problem
of Hamming graphs.


title: Available Stabilizing Heaps

abstract:
  This paper describes a heap construction that supports insert and delete
operations in arbitrary (possibly illegitimate) states. After any sequence of
at most O(m) heap operations, the heap state is guarantee to be legitimate,
where m is the initial number of items in the heap. The response from each
operation is consistent with its effect on the data structure, even for
illegitimate states. The time complexity of each operation is O(lg K) where K
is the capacity of the data structure; when the heap's state is legitimate the
time complexity is O(lg n) for n equal to the number items in the heap.


title: Dancing links

abstract:
  The author presents two tricks to accelerate depth-first search algorithms
for a class of combinatorial puzzle problems, such as tiling a tray by a fixed
set of polyominoes. The first trick is to implement each assumption of the
search with reversible local operations on doubly linked lists. By this trick,
every step of the search affects the data incrementally.
  The second trick is to add a ghost square that represents the identity of
each polyomino. Thus puts the rule that each polyomino be used once on the same
footing as the rule that each square be covered once. The coding simplifies to
a more abstract form which is equivalent to 0-1 integer programming. More
significantly for the total computation time, the search can naturally switch
between placing a fixed polyomino or covering a fixed square at different
stages, according to a combined heuristic.
  Finally the author reports excellent performance for his algorithm for some
familiar puzzles. These include tiling a hexagon by 19 hexiamonds and the N
queens problem for N up to 18.


title: Available and Stabilizing 2-3 Trees

abstract:
  Transient faults corrupt the content and organization of data structures. A
recovery technique dealing with such faults is stabilization, which guarantees,
following some number of operations on the data structure, that content of the
data structure is legitimate. Another notion of fault tolerance is
availability, which is the property that operations continue to be applied
during the period of recovery after a fault, and successful updates are not
lost while the data structure stabilizes to a legitimate state. The available,
stabilizing 2-3 tree supports find, insert, and delete operations, each with
O(lg n) complexity when the tree's state is legitimate and contains n items.
For an illegitimate state, these operations have O(lg K) complexity where K is
the maximum capacity of the tree. Within O(t) operations, the state of the tree
is guaranteed to be legitimate, where t is the number of nodes accessible via
some path from the tree's root at the initial state. This paper resolves, for
the first time, issues of dynamic allocation and pointer organization in a
stabilizing data structure.


title: Random Shuffling to Reduce Disorder in Adaptive Sorting Scheme

abstract:
  In this paper we present a random shuffling scheme to apply with adaptive
sorting algorithms. Adaptive sorting algorithms utilize the presortedness
present in a given sequence. We have probabilistically increased the amount of
presortedness present in a sequence by using a random shuffling technique that
requires little computation. Theoretical analysis suggests that the proposed
scheme can improve the performance of adaptive sorting. Experimental results
show that it significantly reduces the amount of disorder present in a given
sequence and improves the execution time of adaptive sorting algorithm as well.


title:
Questions for a Materialist Philosophy Implying the Equivalence of
  Computers and Human Cognition

abstract:
  Issues related to a materialist philosophy are explored as concerns the
implied equivalence of computers running software and human observers. One
issue explored concerns the measurement process in quantum mechanics. Another
issue explored concerns the nature of experience as revealed by the existence
of dreams. Some difficulties stemming from a materialist philosophy as regards
these issues are pointed out. For example, a gedankenexperiment involving what
has been called "negative" observation is discussed that illustrates the
difficulty with a materialist assumption in quantum mechanics. Based on an
exploration of these difficulties, specifications are outlined briefly that
would provide a means to demonstrate the equivalence of of computers running
software and human experience given a materialist assumption.


title: Improving Performance of heavily loaded agents

abstract:
  With the increase in agent-based applications, there are now agent systems
that support \emph{concurrent} client accesses. The ability to process large
volumes of simultaneous requests is critical in many such applications. In such
a setting, the traditional approach of serving these requests one at a time via
queues (e.g. \textsf{FIFO} queues, priority queues) is insufficient.
Alternative models are essential to improve the performance of such
\emph{heavily loaded} agents. In this paper, we propose a set of
\emph{cost-based algorithms} to \emph{optimize} and \emph{merge} multiple
requests submitted to an agent. In order to merge a set of requests, one first
needs to identify commonalities among such requests. First, we provide an
\emph{application independent framework} within which an agent developer may
specify relationships (called \emph{invariants}) between requests. Second, we
provide two algorithms (and various accompanying heuristics) which allow an
agent to automatically rewrite requests so as to avoid redundant work---these
algorithms take invariants associated with the agent into account. Our
algorithms are independent of any specific agent framework. For an
implementation, we implemented both these algorithms on top of the \impact
agent development platform, and on top of a (non-\impact) geographic database
agent. Based on these implementations, we conducted experiments and show that
our algorithms are considerably more efficient than methods that use the $A^*$
algorithm.


title: Value Withdrawal Explanation in CSP

abstract:
  This work is devoted to constraint solving motivated by the debugging of
constraint logic programs a la GNU-Prolog. The paper focuses only on the
constraints. In this framework, constraint solving amounts to domain reduction.
A computation is formalized by a chaotic iteration. The computed result is
described as a closure. This model is well suited to the design of debugging
notions and tools, for example failure explanations or error diagnosis. In this
paper we detail an application of the model to an explanation of a value
withdrawal in a domain. Some other works have already shown the interest of
such a notion of explanation not only for failure analysis.


title: Support for Debugging Automatically Parallelized Programs

abstract:
  We describe a system that simplifies the process of debugging programs
produced by computer-aided parallelization tools. The system uses relative
debugging techniques to compare serial and parallel executions in order to show
where the computations begin to differ. If the original serial code is correct,
errors due to parallelization will be isolated by the comparison.
  One of the primary goals of the system is to minimize the effort required of
the user. To that end, the debugging system uses information produced by the
parallelization tool to drive the comparison process. In particular, the
debugging system relies on the parallelization tool to provide information
about where variables may have been modified and how arrays are distributed
across multiple processes. User effort is also reduced through the use of
dynamic instrumentation. This allows us to modify the program execution without
changing the way the user builds the executable.
  The use of dynamic instrumentation also permits us to compare the executions
in a fine-grained fashion and only involve the debugger when a difference has
been detected. This reduces the overhead of executing instrumentation.


title:
Kima - an Automated Error Correction System for Concurrent Logic
  Programs

abstract:
  We have implemented Kima, an automated error correction system for concurrent
logic programs. Kima corrects near-misses such as wrong variable occurrences in
the absence of explicit declarations of program properties. Strong
moding/typing and constraint-based analysis are turning to play fundamental
roles in debugging concurrent logic programs as well as in establishing the
consistency of communication protocols and data types. Mode/type analysis of
Moded Flat GHC is a constraint satisfaction problem with many simple mode/type
constraints, and can be solved efficiently. We proposed a simple and efficient
technique which, given a non-well-moded/typed program, diagnoses the
``reasons'' of inconsistency by finding minimal inconsistent subsets of
mode/type constraints. Since each constraint keeps track of the symbol
occurrence in the program, a minimal subset also tells possible sources of
program errors. Kima realizes automated correction by replacing symbol
occurrences around the possible sources and recalculating modes and types of
the rewritten programs systematically. As long as bugs are near-misses, Kima
proposes a rather small number of alternatives that include an intended
program.


title: A General Framework for Automatic Termination Analysis of Logic Programs

abstract:
  This paper describes a general framework for automatic termination analysis
of logic programs, where we understand by ``termination'' the finitenes s of
the LD-tree constructed for the program and a given query. A general property
of mappings from a certain subset of the branches of an infinite LD-tree into a
finite set is proved. From this result several termination theorems are
derived, by using different finite sets. The first two are formulated for the
predicate dependency and atom dependency graphs. Then a general result for the
case of the query-mapping pairs relevant to a program is proved (cf.
\cite{Sagiv,Lindenstrauss:Sagiv}). The correctness of the {\em TermiLog} system
described in \cite{Lindenstrauss:Sagiv:Serebrenik} follows from it. In this
system it is not possible to prove termination for programs involving
arithmetic predicates, since the usual order for the integers is not
well-founded. A new method, which can be easily incorporated in {\em TermiLog}
or similar systems, is presented, which makes it possible to prove termination
for programs involving arithmetic predicates. It is based on combining a finite
abstraction of the integers with the technique of the query-mapping pairs, and
is essentially capable of dividing a termination proof into several cases, such
that a simple termination function suffices for each case. Finally several
possible extensions are outlined.


title: Finding Failure Causes through Automated Testing

abstract:
  A program fails. Under which circumstances does this failure occur? One
single algorithm, the delta debugging algorithm, suffices to determine these
failure-inducing circumstances. Delta debugging tests a program systematically
and automatically to isolate failure-inducing circumstances such as the program
input, changes to the program code, or executed statements.


title: The Role of Commutativity in Constraint Propagation Algorithms

abstract:
  Constraint propagation algorithms form an important part of most of the
constraint programming systems. We provide here a simple, yet very general
framework that allows us to explain several constraint propagation algorithms
in a systematic way. In this framework we proceed in two steps. First, we
introduce a generic iteration algorithm on partial orderings and prove its
correctness in an abstract setting. Then we instantiate this algorithm with
specific partial orderings and functions to obtain specific constraint
propagation algorithms.
  In particular, using the notions commutativity and semi-commutativity, we
show that the {\tt AC-3}, {\tt PC-2}, {\tt DAC} and {\tt DPC} algorithms for
achieving (directional) arc consistency and (directional) path consistency are
instances of a single generic algorithm. The work reported here extends and
simplifies that of Apt \citeyear{Apt99b}.


title:
Towards a Universal Theory of Artificial Intelligence based on
  Algorithmic Probability and Sequential Decision Theory

abstract:
  Decision theory formally solves the problem of rational agents in uncertain
worlds if the true environmental probability distribution is known.
Solomonoff's theory of universal induction formally solves the problem of
sequence prediction for unknown distribution. We unify both theories and give
strong arguments that the resulting universal AIXI model behaves optimal in any
computable environment. The major drawback of the AIXI model is that it is
uncomputable. To overcome this problem, we construct a modified algorithm
AIXI^tl, which is still superior to any other time t and space l bounded agent.
The computation time of AIXI^tl is of the order t x 2^l.


title: A brief overview of the MAD debugging activities

abstract:
  Debugging parallel and distributed programs is a difficult activitiy due to
the multiplicity of sequential bugs, the existence of malign effects like race
conditions and deadlocks, and the huge amounts of data that have to be
processed. These problems are addressed by the Monitoring And Debugging
environment MAD, which offers debugging functionality based on a graphical
representation of a program's execution. The target applications of MAD are
parallel programs applying the standard Message-Passing Interface MPI, which is
used extensively in the high-performance computing domain. The highlights of
MAD are interactive inspection mechanisms including visualization of
distributed arrays, the possibility to graphically place breakpoints, a
mechanism for monitor overhead removal, and the evaluation of racing messages
occuring due to nondeterminism in the code.


title: Taxation and Valuation

abstract:
  The greatest harm from highway robbers lies not in seized wallets but in
inhibited travel. Similarly, incentives for tax-reducing strategies put much
sand in the wheels of the economy. Demands to replace our monumental tax code
with a simple, graceful one that does not distort economic incentives heat up
periodically in political debate, but such dreams never materialize. A
FUNDAMENTAL obstacle, not yet well understood in the economic literature, is
the impossibility of objectively evaluating the tax base -- assets, income,
etc. One can see this even in toy examples, say, trying to assess the value of
a position in chess: great masters' assessments will all differ. Here computer
theory can add an insight not provided by classical economics tools.
  A way around is to avoid evaluations by expressing the tax in natural units,
not in cash. For publicly traded corporations, these could be corporate shares.
I discuss a simple (postcard-sized in ALL details) corporate tax system that
avoids ANY distortion of incentives. (Tax tools MEANT to influence corporate
policies should be set as explicit separate taxes or credits, open to public
scrutiny, not hidden between lines of an incomprehensible tax code.) Roughly,
the~system is to periodically take a t*i fraction of shares to auction, where t
is the tax rate, i is the interest rate. It replaces all income taxes on
publicly traded corporations, their subsidiaries, and shareholders.
  The interest rate is defined via specially designed bonds, so that the whole
system can be shown PRECISELY equivalent to a flat tax on INVESTMENT RETURN.
Note that taxing the return DIRECTLY is impossible: it would invite
manipulation of stock market~prices. The main feature is that nothing
corporations and investors do can change their tax (t*i fraction of shares), so
they would do business exactly the SAME WAY they would WITHOUT TAXES.


title: Slicing of Constraint Logic Programs

abstract:
  Slicing is a program analysis technique originally developed for imperative
languages. It facilitates understanding of data flow and debugging.
  This paper discusses slicing of Constraint Logic Programs. Constraint Logic
Programming (CLP) is an emerging software technology with a growing number of
applications. Data flow in constraint programs is not explicit, and for this
reason the concepts of slice and the slicing techniques of imperative languages
are not directly applicable.
  This paper formulates declarative notions of slice suitable for CLP. They
provide a basis for defining slicing techniques (both dynamic and static) based
on variable sharing. The techniques are further extended by using groundness
information.
  A prototype dynamic slicer of CLP programs implementing the presented ideas
is briefly described together with the results of some slicing experiments.


title: Well-Typed Logic Programs Are not Wrong

abstract:
  We consider prescriptive type systems for logic programs (as in Goedel or
Mercury). In such systems, the typing is static, but it guarantees an
operational property: if a program is "well-typed", then all derivations
starting in a "well-typed" query are again "well-typed". This property has been
called subject reduction. We show that this property can also be phrased as a
property of the proof-theoretic semantics of logic programs, thus abstracting
from the usual operational (top-down) semantics. This proof-theoretic view
leads us to questioning a condition which is usually considered necessary for
subject reduction, namely the head condition. It states that the head of each
clause must have a type which is a variant (and not a proper instance) of the
declared type. We provide a more general condition, thus reestablishing a
certain symmetry between heads and body atoms. The condition ensures that in a
derivation, the types of two unified terms are themselves unifiable. We discuss
possible implications of this result. We also discuss the relationship between
the head condition and polymorphic recursion, a concept known in functional
programming.


title: A Virtual Java Simulation Lab for Computer Science Students

abstract:
  The VJ-Lab is a project oriented to improve the students learning process of
Computer Science degree at the National University of La Plata. The VJ-Lab is a
Web application with Java based simulations. Java can be used to provide
simulation environments with simple pictorial interfaces that can help students
to understand the subject. There are many fields in which it is difficult to
give students a feel for the subject that they are learning. Computer based
simulations offer a fun and effective way to enable students to learn by doing.
Both, practicing skills and applying knowledge are both allowed in simulated
worlds. We will focus on the VJ-Lab project overview, the work in progress and
some Java based simulations running. They imitate the behavior of data network
protocol and data structure algorithms. These applets are produced by the
students of the 'Software Development Laboratory' course.


title: Towards Robust Quantum Computation

abstract:
  Quantum computation is a subject of much theoretical promise, but has not
been realized in large scale, despite the discovery of fault-tolerant
procedures to overcome decoherence. Part of the reason is that the
theoretically modest requirements still present daunting experimental
challenges. The goal of this Dissertation is to reduce various resources
required for robust quantum computation, focusing on quantum error correcting
codes and solution NMR quantum computation. A variety of techniques have been
developed, including high rate quantum codes for amplitude damping, relaxed
criteria for quantum error correction, systematic construction of
fault-tolerant gates, recipes for quantum process tomography, techniques in
bulk thermal state computation, and efficient decoupling techniques to
implement selective coupled logic gates. A detailed experimental study of a
quantum error correcting code in NMR is also presented. The Dissertation
clarifies and extends results previously reported in quant-ph/9610043,
quant-ph/9704002, quant-ph/9811068, quant-ph/9904100, quant-ph/9906112,
quant-ph/0002039. Additionally, a procedure for quantum process tomography
using maximally entangled states, and a review on NMR quantum computation are
included.


title: Resource-distribution via Boolean constraints

abstract:
  We consider the problem of searching for proofs in sequential presentations
of logics with multiplicative (or intensional) connectives. Specifically, we
start with the multiplicative fragment of linear logic and extend, on the one
hand, to linear logic with its additives and, on the other, to the additives of
the logic of bunched implications, BI. We give an algebraic method for
calculating the distribution of the side-formulae in multiplicative rules which
allows the occurrence or non-occurrence of a formula on a branch of a proof to
be determined once sufficient information is available. Each formula in the
conclusion of such a rule is assigned a Boolean expression. As a search
proceeds, a set of Boolean constraint equations is generated. We show that a
solution to such a set of equations determines a proof corresponding to the
given search. We explain a range of strategies, from the lazy to the eager, for
solving sets of constraint equations. We indicate how to apply our methods
systematically to large family of relevant systems.


title: A Note on Power-Laws of Internet Topology

abstract:
  The three Power-Laws proposed by Faloutsos et al(1999) are important
discoveries among many recent works on finding hidden rules in the seemingly
chaotic Internet topology. In this note, we want to point out that the first
two laws discovered by Faloutsos et al(1999, hereafter, {\it Faloutsos' Power
Laws}) are in fact equivalent. That is, as long as any one of them is true, the
other can be derived from it, and {\it vice versa}. Although these two laws are
equivalent, they provide different ways to measure the exponents of their
corresponding power law relations. We also show that these two measures will
give equivalent results, but with different error bars. We argue that for nodes
of not very large out-degree($\leq 32$ in our simulation), the first Faloutsos'
Power Law is superior to the second one in giving a better estimate of the
exponent, while for nodes of very large out-degree($> 32$) the power law
relation may not be present, at least for the relation between the frequency of
out-degree and node out-degree.


title: Creativity and Delusions: A Neurocomputational Approach

abstract:
  Thinking is one of the most interesting mental processes. Its complexity is
sometimes simplified and its different manifestations are classified into
normal and abnormal, like the delusional and disorganized thought or the
creative one. The boundaries between these facets of thinking are fuzzy causing
difficulties in medical, academic, and philosophical discussions. Considering
the dopaminergic signal-to-noise neuronal modulation in the central nervous
system, and the existence of semantic maps in human brain, a self-organizing
neural network model was developed to unify the different thought processes
into a single neurocomputational substrate. Simulations were performed varying
the dopaminergic modulation and observing the different patterns that emerged
at the semantic map. Assuming that the thought process is the total pattern
elicited at the output layer of the neural network, the model shows how the
normal and abnormal thinking are generated and that there are no borders
between their different manifestations. Actually, a continuum of different
qualitative reasoning, ranging from delusion to disorganization of thought, and
passing through the normal and the creative thinking, seems to be more
plausible. The model is far from explaining the complexities of human thinking
but, at least, it seems to be a good metaphorical and unifying view of the many
facets of this phenomenon usually studied in separated settings.


title:
A Benchmark for Image Retrieval using Distributed Systems over the
  Internet: BIRDS-I

abstract:
  The performance of CBIR algorithms is usually measured on an isolated
workstation. In a real-world environment the algorithms would only constitute a
minor component among the many interacting components. The Internet
dramati-cally changes many of the usual assumptions about measuring CBIR
performance. Any CBIR benchmark should be designed from a networked systems
standpoint. These benchmarks typically introduce communication overhead because
the real systems they model are distributed applications. We present our
implementation of a client/server benchmark called BIRDS-I to measure image
retrieval performance over the Internet. It has been designed with the trend
toward the use of small personalized wireless systems in mind. Web-based CBIR
implies the use of heteroge-neous image sets, imposing certain constraints on
how the images are organized and the type of performance metrics applicable.
BIRDS-I only requires controlled human intervention for the compilation of the
image collection and none for the generation of ground truth in the measurement
of retrieval accuracy. Benchmark image collections need to be evolved
incrementally toward the storage of millions of images and that scaleup can
only be achieved through the use of computer-aided compilation. Finally, our
scoring metric introduces a tightly optimized image-ranking window.


title: Performance and Scalability Models for a Hypergrowth e-Commerce Web Site

abstract:
  The performance of successful Web-based e-commerce services has all the
allure of a roller-coaster ride: accelerated fiscal growth combined with the
ever-present danger of running out of server capacity. This chapter presents a
case study based on the author's own capacity planning engagement with one of
the hottest e-commerce Web sites in the world. Several spreadsheet techniques
are presented for forecasting both short-term and long-term trends in the
consumption of server capacity. Two new performance metrics are introduced for
site planning and procurement: the effective demand, and the doubling period.


title: The Tale of One-way Functions

abstract:
  The existence of one-way functions is arguably the most important problem in
computer theory. The article discusses and refines a number of concepts
relevant to this problem. For instance, it gives the first combinatorial
complete owf, i.e., a function which is one-way if any function is. There are
surprisingly many subtleties in basic definitions. Some of these subtleties are
discussed or hinted at in the literature and some are overlooked. Here, a
unified approach is attempted.


title: Byzantine Agreement with Faulty Majority using Bounded Broadcast

abstract:
  Byzantine Agreement introduced in [Pease, Shostak, Lamport, 80] is a widely
used building block of reliable distributed protocols. It simulates broadcast
despite the presence of faulty parties within the network, traditionally using
only private unicast links. Under such conditions, Byzantine Agreement requires
more than 2/3 of the parties to be compliant. [Fitzi, Maurer, 00], constructed
a Byzantine Agreement protocol for any compliant majority based on an
additional primitive allowing transmission to any two parties simultaneously.
They proposed a problem of generalizing these results to wider channels and
fewer compliant parties. We prove that 2f < kh condition is necessary and
sufficient for implementing broadcast with h compliant and f faulty parties
using k-cast channels.


title: Automatic Differentiation Tools in Optimization Software

abstract:
  We discuss the role of automatic differentiation tools in optimization
software. We emphasize issues that are important to large-scale optimization
and that have proved useful in the installation of nonlinear solvers in the
NEOS Server. Our discussion centers on the computation of the gradient and
Hessian matrix for partially separable functions and shows that the gradient
and Hessian matrix can be computed with guaranteed bounds in time and memory
requirements


title: Automated Debugging In Java Using OCL And JDI

abstract:
  Correctness constraints provide a foundation for automated debugging within
object-oriented systems. This paper discusses a new approach to incorporating
correctness constraints into Java development environments. Our approach uses
the Object Constraint Language ("OCL") as a specification language and the Java
Debug Interface ("JDI") as a verification API. OCL provides a standard language
for expressing object-oriented constraints that can integrate with Unified
Modeling Language ("UML") software models. JDI provides a standard Java API
capable of supporting type-safe and side effect free runtime constraint
evaluation. The resulting correctness constraint mechanism: (1) entails no
programming language modifications; (2) requires neither access nor changes to
existing source code; and (3) works with standard off-the-shelf Java virtual
machines ("VMs"). A prototype correctness constraint auditor is presented to
demonstrate the utility of this mechanism for purposes of automated debugging.


title:
Signal-Theoretic Characterization of Waveguide Mesh Geometries for
  Models of Two--Dimensional Wave Propagation in Elastic Media

abstract:
  Waveguide Meshes are efficient and versatile models of wave propagation along
a multidimensional ideal medium. The choice of the mesh geometry affects both
the computational cost and the accuracy of simulations. In this paper, we focus
on 2D geometries and use multidimensional sampling theory to compare the
square, triangular, and hexagonal meshes in terms of sampling efficiency and
dispersion error under conditions of critical sampling. The analysis shows that
the triangular geometry exhibits the most desirable tradeoff between accuracy
and computational cost.


title: Decomposing Finite Abelian Groups

abstract:
  This paper describes a quantum algorithm for efficiently decomposing finite
Abelian groups. Such a decomposition is needed in order to apply the Abelian
hidden subgroup algorithm. Such a decomposition (assuming the Generalized
Riemann Hypothesis) also leads to an efficient algorithm for computing class
numbers (known to be at least as difficult as factoring).


title: Slicing Event Traces of Large Software Systems

abstract:
  Debugging of large software systems consisting of many processes accessing
shared resources is a very difficult task. Many commercial systems record
essential events during system execution for post-mortem analysis. However, the
event traces of large and long-running systems can be quite voluminous.
Analysis of such event traces to identify sources of incorrect behavior can be
very tedious, error-prone, and inefficient. In this paper, we propose a novel
technique of slicing event traces as a means of reducing the number of events
for analysis. This technique identifies events that may have influenced
observed incorrect system behavior. In order to recognize influencing events
several types of dependencies between events are identified. These dependencies
are determined automatically from an event trace. In order to improve the
precision of slicing we propose to use additional dependencies, referred to as
cause-effect dependencies, which can further reduce the size of sliced event
traces. Our initial experience has shown that this slicing technique can
significantly reduce the size of event traces for analysis.


title:
Optimal Moebius Transformations for Information Visualization and
  Meshing

abstract:
  We give linear-time quasiconvex programming algorithms for finding a Moebius
transformation of a set of spheres in a unit ball or on the surface of a unit
sphere that maximizes the minimum size of a transformed sphere. We can also use
similar methods to maximize the minimum distance among a set of pairs of input
points. We apply these results to vertex separation and symmetry display in
spherical graph drawing, viewpoint selection in hyperbolic browsing, element
size control in conformal structured mesh generation, and brain flat mapping.


title:
Assertion checker for the C programming language based on computations
  over event traces

abstract:
  This paper suggests an approach to the development of software testing and
debugging automation tools based on precise program behavior models. The
program behavior model is defined as a set of events (event trace) with two
basic binary relations over events -- precedence and inclusion, and represents
the temporal relationship between actions. A language for the computations over
event traces is developed that provides a basis for assertion checking,
debugging queries, execution profiles, and performance measurements. The
approach is nondestructive, since assertion texts are separated from the target
program source code and can be maintained independently. Assertions can capture
the dynamic properties of a particular target program and can formalize the
general knowledge of typical bugs and debugging strategies. An event grammar
provides a sound basis for assertion language implementation via target program
automatic instrumentation. An implementation architecture and preliminary
experiments with a prototype assertion checker for the C programming language
are discussed.


title: A Knowledge-based Automated Debugger in Learning System

abstract:
  Currently, programming instructors continually face the problem of helping to
debug students' programs. Although there currently exist a number of debuggers
and debugging tools in various platforms, most of these projects or products
are crafted through the needs of software maintenance, and not through the
perspective of teaching of programming. Moreover, most debuggers are too
general, meant for experts as well as not user-friendly. We propose a new
knowledge-based automated debugger to be used as a user-friendly tool by the
students to self-debug their own programs. Stereotyped code (cliche) and bugs
cliche will be stored as library of plans in the knowledge-base. Recognition of
correct code or bugs is based on pattern matching and constraint satisfaction.
Given a syntax error-free program and its specification, this debugger called
Adil (Automated Debugger in Learning system) will be able locate, pinpoint and
explain logical errors of programs. If there are no errors, it will be able to
explain the meaning of the program. Adil is based on the design of the
Conceiver, an automated program understanding system developed at Universiti
Kebangsaan Malaysia.


title: Generation of and Debugging with Logical Pre and Postconditions

abstract:
  This paper shows the debugging facilities provided by the SLAM system. The
SLAM system includes i) a specification language that integrates algebraic
specifications and model-based specifications using the object oriented model.
Class operations are defined by using rules each of them with logical pre and
postconditions but with a functional flavour. ii) A development environment
that, among other features, is able to generate readable code in a high level
object oriented language. iii) The generated code includes (part of) the pre
and postconditions as assertions, that can be automatically checked in the
debug mode execution of programs. We focus on this last aspect.
  The SLAM language is expressive enough to describe many useful properties and
these properties are translated into a Prolog program that is linked (via an
adequate interface) with the user program. The debugging execution of the
program interacts with the Prolog engine which is responsible for checking
properties.


title:
An Even Faster and More Unifying Algorithm for Comparing Trees via
  Unbalanced Bipartite Matchings

abstract:
  A widely used method for determining the similarity of two labeled trees is
to compute a maximum agreement subtree of the two trees. Previous work on this
similarity measure is only concerned with the comparison of labeled trees of
two special kinds, namely, uniformly labeled trees (i.e., trees with all their
nodes labeled by the same symbol) and evolutionary trees (i.e., leaf-labeled
trees with distinct symbols for distinct leaves). This paper presents an
algorithm for comparing trees that are labeled in an arbitrary manner. In
addition to this generality, this algorithm is faster than the previous
algorithms.
  Another contribution of this paper is on maximum weight bipartite matchings.
We show how to speed up the best known matching algorithms when the input
graphs are node-unbalanced or weight-unbalanced. Based on these enhancements,
we obtain an efficient algorithm for a new matching problem called the
hierarchical bipartite matching problem, which is at the core of our maximum
agreement subtree algorithm.


title: Multiple-Size Divide-and-Conquer Recurrences

abstract:
  This short note reports a master theorem on tight asymptotic solutions to
divide-and-conquer recurrences with more than one recursive term: for example,
T(n) = 1/4 T(n/16) + 1/3 T(3n/5) + 4 T(n/100) + 10 T(n/300) + n^2.