title: Flood Routing Technique for Data Networks

abstract:
  In this paper, a new routing algorithm based on a flooding method is
introduced. Flooding techniques have been used previously, e.g. for
broadcasting the routing table in the ARPAnet [1] and other special purpose
networks [3][4][5]. However, sending data using flooding can often saturate the
network [2] and it is usually regarded as an inefficient broadcast mechanism.
Our approach is to flood a very short packet to explore an optimal route
without relying on a pre-established routing table, and an efficient flood
control algorithm to reduce the signalling traffic overhead. This is an
inherently robust mechanism in the face of a network configuration change,
achieves automatic load sharing across alternative routes and has potential to
solve many contemporary routing problems. An earlier version of this mechanism
was originally developed for virtual circuit establishment in the experimental
Caroline ATM LAN [6][7] at Monash University.


title: Analysis of Performance of Dynamic Multicast Routing Algorithms

abstract:
  In this paper, three new dynamic multicast routing algorithms based on the
greedy tree technique are proposed; Source Optimised Tree, Topology Based Tree
and Minimum Diameter Tree. A simulation analysis is presented showing various
performance aspects of the algorithms, in which a comparison is made with the
greedy and core based tree techniques. The effects of the tree source location
on dynamic membership change are also examined. The simulations demonstrate
that the Source Optimised Tree algorithm achieves a significant improvement in
terms of delay and link usage when compared to the Core Based Tree, and greedy
algorithm.


title: Bicriteria Network Design Problems

abstract:
  We study a general class of bicriteria network design problems. A generic
problem in this class is as follows: Given an undirected graph and two
minimization objectives (under different cost functions), with a budget
specified on the first, find a <subgraph \from a given subgraph-class that
minimizes the second objective subject to the budget on the first. We consider
three different criteria - the total edge cost, the diameter and the maximum
degree of the network. Here, we present the first polynomial-time approximation
algorithms for a large class of bicriteria network design problems for the
above mentioned criteria. The following general types of results are presented.
  First, we develop a framework for bicriteria problems and their
approximations. Second, when the two criteria are the same %(note that the cost
functions continue to be different) we present a ``black box'' parametric
search technique. This black box takes in as input an (approximation) algorithm
for the unicriterion situation and generates an approximation algorithm for the
bicriteria case with only a constant factor loss in the performance guarantee.
Third, when the two criteria are the diameter and the total edge costs we use a
cluster-based approach to devise a approximation algorithms --- the solutions
output violate both the criteria by a logarithmic factor. Finally, for the
class of treewidth-bounded graphs, we provide pseudopolynomial-time algorithms
for a number of bicriteria problems using dynamic programming. We show how
these pseudopolynomial-time algorithms can be converted to fully
polynomial-time approximation schemes using a scaling technique.


title:
Adaptive Multicast of Multi-Layered Video: Rate-Based and Credit-Based
  Approaches

abstract:
  Network architectures that can efficiently transport high quality, multicast
video are rapidly becoming a basic requirement of emerging multimedia
applications. The main problem complicating multicast video transport is
variation in network bandwidth constraints. An attractive solution to this
problem is to use an adaptive, multi-layered video encoding mechanism. In this
paper, we consider two such mechanisms for the support of video multicast; one
is a rate-based mechanism that relies on explicit rate congestion feedback from
the network, and the other is a credit-based mechanism that relies on
hop-by-hop congestion feedback. The responsiveness, bandwidth utilization,
scalability and fairness of the two mechanisms are evaluated through
simulations. Results suggest that while the two mechanisms exhibit performance
trade-offs, both are capable of providing a high quality video service in the
presence of varying bandwidth constraints.


title: Hyper-Systolic Matrix Multiplication

abstract:
  A novel parallel algorithm for matrix multiplication is presented. The
hyper-systolic algorithm makes use of a one-dimensional processor abstraction.
The procedure can be implemented on all types of parallel systems. It can
handle matrix-vector multiplications as well as transposed matrix products.


title: Processing Unknown Words in HPSG

abstract:
  The lexical acquisition system presented in this paper incrementally updates
linguistic properties of unknown words inferred from their surrounding context
by parsing sentences with an HPSG grammar for German. We employ a gradual,
information-based concept of ``unknownness'' providing a uniform treatment for
the range of completely known to maximally unknown lexical entries. ``Unknown''
information is viewed as revisable information, which is either generalizable
or specializable. Updating takes place after parsing, which only requires a
modified lexical lookup. Revisable pieces of information are identified by
grammar-specified declarations which provide access paths into the parse
feature structure. The updating mechanism revises the corresponding places in
the lexical feature structures iff the context actually provides new
information. For revising generalizable information, type union is required. A
worked-out example demonstrates the inferential capacity of our implemented
system.


title: Computing Declarative Prosodic Morphology

abstract:
  This paper describes a computational, declarative approach to prosodic
morphology that uses inviolable constraints to denote small finite candidate
sets which are filtered by a restrictive incremental optimization mechanism.
The new approach is illustrated with an implemented fragment of Modern Hebrew
verbs couched in MicroCUF, an expressive constraint logic formalism. For
generation and parsing of word forms, I propose a novel off-line technique to
eliminate run-time optimization. It produces a finite-state oracle that
efficiently restricts the constraint interpreter's search space. As a
byproduct, unknown words can be analyzed without special mechanisms. Unlike
pure finite-state transducer approaches, this hybrid setup allows for more
expressivity in constraints to specify e.g. token identity for reduplication or
arithmetic constraints for phonetics.


title: Learning Nested Agent Models in an Information Economy

abstract:
  We present our approach to the problem of how an agent, within an economic
Multi-Agent System, can determine when it should behave strategically (i.e.
learn and use models of other agents), and when it should act as a simple
price-taker. We provide a framework for the incremental implementation of
modeling capabilities in agents, and a description of the forms of knowledge
required. The agents were implemented and different populations simulated in
order to learn more about their behavior and the merits of using and learning
agent models. Our results show, among other lessons, how savvy buyers can avoid
being ``cheated'' by sellers, how price volatility can be used to
quantitatively predict the benefits of deeper models, and how specific types of
agent populations influence system behavior.


title: Linear Complexity Hexahedral Mesh Generation

abstract:
  We show that any polyhedron forming a topological ball with an even number of
quadrilateral sides can be partitioned into O(n) topological cubes, meeting
face to face. The result generalizes to non-simply-connected polyhedra
satisfying an additional bipartiteness condition. The same techniques can also
be used to reduce the geometric version of the hexahedral mesh generation
problem to a finite case analysis amenable to machine solution.


title: Similarity-Based Models of Word Cooccurrence Probabilities

abstract:
  In many applications of natural language processing (NLP) it is necessary to
determine the likelihood of a given word combination. For example, a speech
recognizer may need to determine which of the two word combinations ``eat a
peach'' and ``eat a beach'' is more likely. Statistical NLP methods determine
the likelihood of a word combination from its frequency in a training corpus.
However, the nature of language is such that many word combinations are
infrequent and do not occur in any given corpus. In this work we propose a
method for estimating the probability of such previously unseen word
combinations using available information on ``most similar'' words.
  We describe probabilistic word association models based on distributional
word similarity, and apply them to two tasks, language modeling and pseudo-word
disambiguation. In the language modeling task, a similarity-based model is used
to improve probability estimates for unseen bigrams in a back-off language
model. The similarity-based method yields a 20% perplexity improvement in the
prediction of unseen bigrams and statistically significant reductions in
speech-recognition error.
  We also compare four similarity-based estimation methods against back-off and
maximum-likelihood estimation methods on a pseudo-word sense disambiguation
task in which we controlled for both unigram and bigram frequency to avoid
giving too much weight to easy-to-disambiguate high-frequency configurations.
The similarity-based methods perform up to 40% better on this particular task.


title: Evolution of Neural Networks to Play the Game of Dots-and-Boxes

abstract:
  Dots-and-Boxes is a child's game which remains analytically unsolved. We
implement and evolve artificial neural networks to play this game, evaluating
them against simple heuristic players. Our networks do not evaluate or predict
the final outcome of the game, but rather recommend moves at each stage.
Superior generalisation of play by co-evolved populations is found, and a
comparison made with networks trained by back-propagation using simple
heuristics as an oracle.


title:
On the Evaluation and Comparison of Taggers: The Effect of Noise in
  Testing Corpora

abstract:
  This paper addresses the issue of {\sc pos} tagger evaluation. Such
evaluation is usually performed by comparing the tagger output with a reference
test corpus, which is assumed to be error-free. Currently used corpora contain
noise which causes the obtained performance to be a distortion of the real
value. We analyze to what extent this distortion may invalidate the comparison
between taggers or the measure of the improvement given by a new system. The
main conclusion is that a more rigorous testing experimentation
setting/designing is needed to reliably evaluate and compare tagger accuracies.


title: Improving Tagging Performance by Using Voting Taggers

abstract:
  We present a bootstrapping method to develop an annotated corpus, which is
specially useful for languages with few available resources. The method is
being applied to develop a corpus of Spanish of over 5Mw. The method consists
on taking advantage of the collaboration of two different POS taggers. The
cases in which both taggers agree present a higher accuracy and are used to
retrain the taggers.


title: The descriptive complexity approach to LOGCFL

abstract:
  Building upon the known generalized-quantifier-based first-order
characterization of LOGCFL, we lay the groundwork for a deeper investigation.
Specifically, we examine subclasses of LOGCFL arising from varying the arity
and nesting of groupoidal quantifiers. Our work extends the elaborate theory
relating monoidal quantifiers to NC1 and its subclasses. In the absence of the
BIT predicate, we resolve the main issues: we show in particular that no single
outermost unary groupoidal quantifier with FO can capture all the context-free
languages, and we obtain the surprising result that a variant of Greibach's
``hardest context-free language'' is LOGCFL-complete under quantifier-free
BIT-free projections. We then prove that FO with unary groupoidal quantifiers
is strictly more expressive with the BIT predicate than without. Considering a
particular groupoidal quantifier, we prove that first-order logic with majority
of pairs is strictly more expressive than first-order with majority of
individuals. As a technical tool of independent interest, we define the notion
of an aperiodic nondeterministic finite automaton and prove that FO
translations are precisely the mappings computed by single-valued aperiodic
nondeterministic finite transducers.


title: A Generalized Quantifier Concept in Computational Complexity Theory

abstract:
  A notion of generalized quantifier in computational complexity theory is
explored and used to give a unified treatment of leaf language definability,
oracle separations, type 2 operators, and circuits with monoidal gates.
Relations to Lindstroem quantifiers are pointed out.


title:
The Complexity of Computing Optimal Assignments of Generalized
  Propositional Formulae

abstract:
  We consider the problems of finding the lexicographically minimal (or
maximal) satisfying assignment of propositional formulae for different
restricted formula classes. It turns out that for each class from our
framework, the above problem is either polynomial time solvable or complete for
OptP. We also consider the problem of deciding if in the optimal assignment the
largest variable gets value 1. We show that this problem is either in P or P^NP
complete.


title: Hard instance generation for SAT

abstract:
  We propose an algorithm of generating hard instances for the Satisfying
Assignment Search Problem (in short, SAT). The algorithm transforms instances
of the integer factorization problem into SAT instances efficiently by using
the Chinese Remainder Theorem. For example, it is possible to construct SAT
instances with about 5,600 variables that is as hard as factorizing 100 bit
integers.


title: The Boolean Hierarchy over Level 1/2 of the Straubing-Therien Hierarchy

abstract:
  For some fixed alphabet A, a language L of A* is in the class L(1/2) of the
Straubing-Therien hierarchy if and only if it can be expressed as a finite
union of languages A*aA*bA*...A*cA*, where a,b,...,c are letters. The class
L(1) is defined as the boolean closure of L(1/2). It is known that the classes
L(1/2) and L(1) are decidable. We give a membership criterion for the single
classes of the boolean hierarchy over L(1/2). From this criterion we can
conclude that this boolean hierarchy is proper and that its classes are
decidable.In finite model theory the latter implies the decidability of the
classes of the boolean hierarchy over the class Sigma(1) of the FO(<)-logic.
Moreover we prove a ``forbidden-pattern'' characterization of L(1) of the type:
L is in L(1) if and only if a certain pattern does not appear in the transition
graph of a deterministic finite automaton accepting L. We discuss complexity
theoretical consequences of our results.


title:
Droems: experimental mathematics, informatics and infinite dimensional
  geometry

abstract:
  The article is devoted to a problem of elaboration of the real-time
interactive videosystems for accelerated nonverbal cognitive computer and
telecommunications. The proposed approach is based on the using of droems
(dynamically reconstructed objects of experimental mathematics) and
interpretational figures as pointers to them. Four paragraphs of the article
are devoted to (1) an exposition of basic notions of the interpretational
geometry, (2) the operator methods in the theory of interactive dynamical
videosystems, (3) the general concept of organization of the integrated
interactive real-time videocognitive systems, (4) the droems and processes of
their dynamical reconstruction, where the general notions are illustrated by a
concrete example related to the infinite dimensional geometry. The exposition
is presumably heuristic and conceptual (the first and the third paragraphs)
though some particular aspects such as content of the second and the fourth
paragraphs, which allow deeper formalization and detailing in present, are
exposed on the mathematical level of rigor.


title:
A Natural Deduction style proof system for propositional $\mu$-calculus
  and its formalization in inductive type theories

abstract:
  In this paper, we present a formalization of Kozen's propositional modal
$\mu$-calculus, in the Calculus of Inductive Constructions. We address several
problematic issues, such as the use of higher-order abstract syntax in
inductive sets in presence of recursive constructors, the encoding of modal
(``proof'') rules and of context sensitive grammars. The encoding can be used
in the \Coq system, providing an experimental computer-aided proof environment
for the interactive development of error-free proofs in the $\mu$-calculus. The
techniques we adopted can be readily ported to other languages and proof
systems featuring similar problematic issues.


title:
Using Local Optimality Criteria for Efficient Information Retrieval with
  Redundant Information Filters

abstract:
  We consider information retrieval when the data, for instance multimedia, is
coputationally expensive to fetch. Our approach uses "information filters" to
considerably narrow the universe of possiblities before retrieval. We are
especially interested in redundant information filters that save time over more
general but more costly filters. Efficient retrieval requires that decision
must be made about the necessity, order, and concurrent processing of proposed
filters (an "execution plan"). We develop simple polynomial-time local criteria
for optimal execution plans, and show that most forms of concurrency are
suboptimal with information filters. Although the general problem of finding an
optimal execution plan is likely exponential in the number of filters, we show
experimentally that our local optimality criteria, used in a polynomial-time
algorithm, nearly always find the global optimum with 15 filters or less, a
sufficient number of filters for most applications. Our methods do not require
special hardware and avoid the high processor idleness that is characteristic
of massive parallelism solutions to this problem. We apply our ideas to an
important application, information retrieval of cpationed data using
natural-language understanding, a problem for which the natural-language
processing can be the bottleneck if not implemented well.


title: Practical algorithms for on-line sampling

abstract:
  One of the core applications of machine learning to knowledge discovery
consists on building a function (a hypothesis) from a given amount of data (for
instance a decision tree or a neural network) such that we can use it
afterwards to predict new instances of the data. In this paper, we focus on a
particular situation where we assume that the hypothesis we want to use for
prediction is very simple, and thus, the hypotheses class is of feasible size.
We study the problem of how to determine which of the hypotheses in the class
is almost the best one. We present two on-line sampling algorithms for
selecting hypotheses, give theoretical bounds on the number of necessary
examples, and analize them exprimentally. We compare them with the simple batch
sampling approach commonly used and show that in most of the situations our
algorithms use much fewer number of examples.


title: A role of constraint in self-organization

abstract:
  In this paper we introduce a neural network model of self-organization. This
model uses a variation of Hebb rule for updating its synaptic weights, and
surely converges to the equilibrium status. The key point of the convergence is
the update rule that constrains the total synaptic weight and this seems to
make the model stable. We investigate the role of the constraint and show that
it is the constraint that makes the model stable. For analyzing this setting,
we propose a simple probabilistic game that models the neural network and the
self-organization process. Then, we investigate the characteristics of this
game, namely, the probability that the game becomes stable and the number of
the steps it takes.


title: Security Policy Specification Using a Graphical Approach

abstract:
  A security policy states the acceptable actions of an information system, as
the actions bear on security. There is a pressing need for organizations to
declare their security policies, even informal statements would be better than
the current practice. But, formal policy statements are preferable to support
(1) reasoning about policies, e.g., for consistency and completeness, (2)
automated enforcement of the policy, e.g., using wrappers around legacy systems
or after the fact with an intrusion detection system, and (3) other formal
manipulation of policies, e.g., the composition of policies. We present LaSCO,
the Language for Security Constraints on Objects, in which a policy consists of
two parts: the domain (assumptions about the system) and the requirement (what
is allowed assuming the domain is satisfied). Thus policies defined in LaSCO
have the appearance of conditional access control statements. LaSCO policies
are specified as expressions in logic and as directed graphs, giving a visual
view of policy. LaSCO has a simple semantics in first order logic (which we
provide), thus permitting policies we write, even for complex policies, to be
very perspicuous. LaSCO has syntax to express many of the situations we have
found to be useful on policies or, more interesting, the composition of
policies. LaSCO has an object-oriented structure, permitting it to be useful to
describe policies on the objects and methods of an application written in an
object-oriented language, in addition to the traditional policies on operating
system objects. A LaSCO specification can be automatically translated into
executable code that checks an invocation of a program with respect to a
policy. The implementation of LaSCO is in Java, and generates wrappers to check
Java programs with respect to a policy.


title: Distributed Computation, the Twisted Isomorphism, and Auto-Poiesis

abstract:
  This paper presents a synchronization-based, multi-process computational
model of anticipatory systems called the Phase Web. It describes a
self-organizing paradigm that explicitly recognizes and exploits the existence
of a boundary between inside and outside, accepts and exploits intentionality,
and uses explicit self-reference to describe eg. auto-poiesis. The model
explicitly connects computation to a discrete Clifford algebraic formalization
that is in turn extended into homology and co-homology, wherein the recursive
nature of objects and boundaries becomes apparent and itself subject to
hierarchical recursion. Topsy, a computer program embodying the Phase Web, is
available at www.cs.auc.dk/topsy.


title: On Dart-Zobel Algorithm for Testing Regular Type Inclusion

abstract:
  This paper answers open questions about the correctness and the completeness
of Dart-Zobel algorithm for testing the inclusion relation between two regular
types. We show that the algorithm is incorrect for regular types. We also prove
that the algorithm is complete for regular types as well as correct for tuple
distributive regular types. Also presented is a simplified version of
Dart-Zobel algorithm for tuple distributive regular types.


title: Pre-fetching tree-structured data in distributed memory

abstract:
  A distributed heap storage manager has been implemented on the Fujitsu AP1000
multicomputer. The performance of various pre-fetching strategies is
experimentally compared. Subjective programming benefits and objective
performance benefits of up to 10% in pre-fetching are found for certain
applications, but not for all. The performance benefits of pre-fetching depend
on the specific data structure and access patterns. We suggest that control of
pre-fetching strategy be dynamically under the control of the application.


title: A Linear Shift Invariant Multiscale Transform

abstract:
  This paper presents a multiscale decomposition algorithm. Unlike standard
wavelet transforms, the proposed operator is both linear and shift invariant.
The central idea is to obtain shift invariance by averaging the aligned wavelet
transform projections over all circular shifts of the signal. It is shown how
the same transform can be obtained by a linear filter bank.


title:
The Design of EzWindows: A Graphics API for an Introductory Programming
  Course

abstract:
  Teaching object-oriented programming in an introductory programming course
poses considerable challenges to the instructor. An often advocated approach to
meeting this challenge is the use of a simple, object-oriented graphics
library. We have developed a simple, portable graphics library for teaching
object-oriented programming using C++. The library, EzWindows, allows beginning
programmers to design and write programs that use the graphical display found
on all modern desktop computers. In addition to providing simple graphical
objects such as windows, geometric shapes, and bitmaps, EzWindows provides
facilities for introducing event-based programming using the mouse and timers.
EzWindows has proven to be extremely popular; it is currently in use at over
200 universities, colleges, and high schools. This paper describes the
rationale for EzWindows and its high-level design.


title: Anytime Coalition Structure Generation with Worst Case Guarantees

abstract:
  Coalition formation is a key topic in multiagent systems. One would prefer a
coalition structure that maximizes the sum of the values of the coalitions, but
often the number of coalition structures is too large to allow exhaustive
search for the optimal one. But then, can the coalition structure found via a
partial search be guaranteed to be within a bound from optimum? We show that
none of the previous coalition structure generation algorithms can establish
any bound because they search fewer nodes than a threshold that we show
necessary for establishing a bound. We present an algorithm that establishes a
tight bound within this minimal amount of search, and show that any other
algorithm would have to search strictly more. The fraction of nodes needed to
be searched approaches zero as the number of agents grows. If additional time
remains, our anytime algorithm searches further, and establishes a
progressively lower tight bound. Surprisingly, just searching one more node
drops the bound in half. As desired, our algorithm lowers the bound rapidly
early on, and exhibits diminishing returns to computation. It also drastically
outperforms its obvious contenders. Finally, we show how to distribute the
desired search across self-interested manipulative agents.


title: The Tiny Tera: A Packet Switch Core

abstract: The objective is to design and build a small, high-bandwidth switch.


title:
Randomization yields simple O(n log star n) algorithms for difficult
  Omega(n) problems

abstract:
  We use here the results on the influence graph by Boissonnat et al. to adapt
them for particular cases where additional information is available. In some
cases, it is possible to improve the expected randomized complexity of
algorithms from O(n log n) to O(n log star n).
  This technique applies in the following applications: triangulation of a
simple polygon, skeleton of a simple polygon, Delaunay triangulation of points
knowing the EMST (euclidean minimum spanning tree).


title: Axiomatizing Flat Iteration

abstract:
  Flat iteration is a variation on the original binary version of the Kleene
star operation P*Q, obtained by restricting the first argument to be a sum of
atomic actions. It generalizes prefix iteration, in which the first argument is
a single action. Complete finite equational axiomatizations are given for five
notions of bisimulation congruence over basic CCS with flat iteration, viz.
strong congruence, branching congruence, eta-congruence, delay congruence and
weak congruence. Such axiomatizations were already known for prefix iteration
and are known not to exist for general iteration. The use of flat iteration has
two main advantages over prefix iteration: 1.The current axiomatizations
generalize to full CCS, whereas the prefix iteration approach does not allow an
elimination theorem for an asynchronous parallel composition operator. 2.The
greater expressiveness of flat iteration allows for much shorter completeness
proofs.
  In the setting of prefix iteration, the most convenient way to obtain the
completeness theorems for eta-, delay, and weak congruence was by reduction to
the completeness theorem for branching congruence. In the case of weak
congruence this turned out to be much simpler than the only direct proof found.
In the setting of flat iteration on the other hand, the completeness theorems
for delay and weak (but not eta-) congruence can equally well be obtained by
reduction to the one for strong congruence, without using branching congruence
as an intermediate step. Moreover, the completeness results for prefix
iteration can be retrieved from those for flat iteration, thus obtaining a
second indirect approach for proving completeness for delay and weak congruence
in the setting of prefix iteration.


title: Object-Oriented Design of Graph Oriented Data Structures

abstract:
  Applied research in graph algorithms and combinatorial structures needs
comprehensive and versatile software libraries. However, the design and the
implementation of flexible libraries are challenging activities. Among the
other problems involved in such a difficult field, a very special role is
played by graph classification issues.
  We propose new techniques devised to help the designer and the programmer in
the development activities. Such techniques are especially suited for dealing
with graph classification problems and rely on an extension of the usual
object-oriented paradigm. In order to support the usage of our approach, we
devised an extension of the C++ programming language and implemented the
corresponding pre-compiler.


title: C++ Templates as Partial Evaluation

abstract:
  This paper explores the relationship between C++ templates and partial
evaluation. Templates were designed to support generic programming, but
unintentionally provided the ability to perform compile-time computations and
code generation. These features are completely accidental, and as a result
their syntax is awkward. By recasting these features in terms of partial
evaluation, a much simpler syntax can be achieved. C++ may be regarded as a
two-level language in which types are first-class values. Template
instantiation resembles an offline partial evaluator. This paper describes
preliminary work toward a single mechanism based on Partial Evaluation which
unifies generic programming, compile-time computation and code generation. The
language Catat is introduced to illustrate these ideas.


title:
Flysig: Dataflow Oriented Delay-Insensitive Processor for Rapid
  Prototyping of Signal Processing

abstract:
  As the one-chip integration of HW-modules designed by different companies
becomes more and more popular reliability of a HW-design and evaluation of the
timing behavior during the prototype stage are absolutely necessary. One way to
guarantee reliability is the use of robust design styles, e.g.,
delay-insensitivity. For early timing evaluation two aspects must be
considered: a) The timing needs to be proportional to technology variations and
b) the implemented architecture should be identical for prototype and target.
The first can be met also by delay-insensitive implementation. The latter one
is the key point. A unified architecture is needed for prototyping as well as
implementation. Our new approach to rapid prototyping of signal processing
tasks is based on a configurable, delay-insensitive implemented processor
called Flysig. In essence, the Flysig processor can be understood as a complex
FPGA where the CLBs are substituted by bit-serial operators. In this paper the
general concept is detailed and first experimental results are given for
demonstration of the main advantages: delay-insensitive design style, direct
correspondence between prototyping and target architecture, high performance
and reasonable shortening of the design cycle.


title: Ultrametric Distance in Syntax

abstract:
  Phrase structure trees have a hierarchical structure. In many subjects, most
notably in Taxonomy such tree structures have been studied using ultrametrics.
Here syntactical hierarchical phrase trees are subject to a similar analysis,
which is much siompler as the branching structure is more readily discernible
and switched. The occurence of hierarchical structure elsewhere in linguistics
is mentioned. The phrase tree can be represented by a matrix and the elements
of the matrix can be represented by triangles. The height at which branching
occurs is not prescribed in previous syntatic models, but it is by using the
ultrametric matrix. The ambiguity of which branching height to choose is
resolved by postulating that branching occurs at the lowest height available.
An ultrametric produces a measure of the complexity of sentences: presumably
the complexity of sentence increases as a language is aquired so that this can
be tested. A All ultrametric triangles are equilateral or isocles, here it is
shown that X structur implies that there are no equilateral triangles.
Restricting attention to simple syntax a minium ultrametric distance between
lexical categories is calculatex. This ultrametric distance is shown to be
different than the matrix obtasined from feaures. It is shown that the
definition of c-commabnd can be replaced by an equivalent ultrametric
definition. The new definition invokes a minimum distance between nodes and
this is more aesthetically satisfing than previouv varieties of definitions.
  From the new definition of c-command follows a new definition of government.


title: Early Experience with ASDL in lcc

abstract:
  The Abstract Syntax Description Language (ASDL) is a language for specifying
the tree data structures often found in compiler intermediate representations.
The ASDL generator reads an ASDL specification and generates code to construct,
read, and write instances of the trees specified. Using ASDL permits a compiler
to be decomposed into semi-independent components that communicate by reading
and writing trees. Each component can be written in a different language,
because the ASDL generator can emit code in several languages, and the files
written by ASDL-generated code are machine- and language-independent. ASDL is
part of the National Compiler Infrastructure project, which seeks to reduce
dramatically the overhead of computer systems research by making it much easier
to build high-quality compilers. This paper describes dividing lcc, a widely
used retargetable C compiler, into two components that communicate via trees
defined in ASDL. As the first use of ASDL in a `real' compiler, this experience
reveals much about the effort required to retrofit an existing compiler to use
ASDL, the overheads involved, and the strengths and weaknesses of ASDL itself
and, secondarily, of lcc.


title: Resources for Evaluation of Summarization Techniques

abstract:
  We report on two corpora to be used in the evaluation of component systems
for the tasks of (1) linear segmentation of text and (2) summary-directed
sentence extraction. We present characteristics of the corpora, methods used in
the collection of user judgments, and an overview of the application of the
corpora to evaluating the component system. Finally, we discuss the problems
and issues with construction of the test set which apply broadly to the
construction of evaluation resources for language technologies.


title: Restrictions on Tree Adjoining Languages

abstract:
  Several methods are known for parsing languages generated by Tree Adjoining
Grammars (TAGs) in O(n^6) worst case running time. In this paper we investigate
which restrictions on TAGs and TAG derivations are needed in order to lower
this O(n^6) time complexity, without introducing large runtime constants, and
without losing any of the generative power needed to capture the syntactic
constructions in natural language that can be handled by unrestricted TAGs. In
particular, we describe an algorithm for parsing a strict subclass of TAG in
O(n^5), and attempt to show that this subclass retains enough generative power
to make it useful in the general case.


title: SYNERGY: A Linear Planner Based on Genetic Programming

abstract:
  In this paper we describe SYNERGY, which is a highly parallelizable, linear
planning system that is based on the genetic programming paradigm. Rather than
reasoning about the world it is planning for, SYNERGY uses artificial
selection, recombination and fitness measure to generate linear plans that
solve conjunctive goals. We ran SYNERGY on several domains (e.g., the briefcase
problem and a few variants of the robot navigation problem), and the
experimental results show that our planner is capable of handling problem
instances that are one to two orders of magnitude larger than the ones solved
by UCPOP. In order to facilitate the search reduction and to enhance the
expressive power of SYNERGY, we also propose two major extensions to our
planning system: a formalism for using hierarchical planning operators, and a
framework for planning in dynamic environments.


title: General Theory of Image Normalization

abstract:
  We give a systematic, abstract formulation of the image normalization method
as applied to a general group of image transformations, and then illustrate the
abstract analysis by applying it to the hierarchy of viewing transformations of
a planar object.


title: A Proof Theoretic View of Constraint Programming

abstract:
  We provide here a proof theoretic account of constraint programming that
attempts to capture the essential ingredients of this programming style. We
exemplify it by presenting proof rules for linear constraints over interval
domains, and illustrate their use by analyzing the constraint propagation
process for the {\tt SEND + MORE = MONEY} puzzle. We also show how this
approach allows one to build new constraint solvers.


title: Gryphon: An Information Flow Based Approach to Message Brokering

abstract:
  Gryphon is a distributed computing paradigm for message brokering, which is
the transferring of information in the form of streams of events from
information providers to information consumers. This extended abstract outlines
the major problems in message brokering and Gryphon's approach to solving them.


title: Computational Geometry Column 33

abstract: Several recent SIGGRAPH papers on surface simplification are described.


title: Computational Geometry Column 32

abstract: The proof of Dey's new k-set bound is illustrated.


title:
Broy-Lamport Specification Problem: A Gurevich Abstract State Machine
  Solution

abstract:
  We apply the Gurevich Abstract State Machine methodology to a benchmark
specification problem of Broy and Lamport.


title: Equivalence is in the Eye of the Beholder

abstract:
  In a recent provocative paper, Lamport points out "the insubstantiality of
processes" by proving the equivalence of two different decompositions of the
same intuitive algorithm by means of temporal formulas. We point out that the
correct equivalence of algorithms is itself in the eye of the beholder. We
discuss a number of related issues and, in particular, whether algorithms can
be proved equivalent directly.


title: Evolving Algebras and Partial Evaluation

abstract:
  We describe an automated partial evaluator for evolving algebras implemented
at the University of Michigan.


title: An Offline Partial Evaluator for Evolving Algebras

abstract:
  We describe the architecture of an evolving algebra partial evaluator, a
program which specializes an evolving algebra with respect to a portion of its
input. We discuss the particular analysis, specialization, and optimization
techniques used and show an example of its use.


title:
The Railroad Crossing Problem: An Experiment with Instantaneous Actions
  and Immediate Reactions

abstract:
  We give an evolving algebra solution for the well-known railroad crossing
problem and use the occasion to experiment with agents that perform
instantaneous actions in continuous time and in particular with agents that
fire at the moment they are enabled.


title: Linguistic Reflection in Java

abstract:
  Reflective systems allow their own structures to be altered from within. Here
we are concerned with a style of reflection, called linguistic reflection,
which is the ability of a running program to generate new program fragments and
to integrate these into its own execution. In particular we describe how this
kind of reflection may be provided in the compiler-based, strongly typed
object-oriented programming language Java. The advantages of the programming
technique include attaining high levels of genericity and accommodating system
evolution. These advantages are illustrated by an example taken from persistent
programming which shows how linguistic reflection allows functionality (program
code) to be generated on demand (Just-In-Time) from a generic specification and
integrated into the evolving running program. The technique is evaluated
against alternative implementation approaches with respect to efficiency,
safety and ease of use.


title: A Polymorphic Groundness Analysis of Logic Programs

abstract:
  A polymorphic analysis is an analysis whose input and output contain
parameters which serve as placeholders for information that is unknown before
analysis but provided after analysis. In this paper, we present a polymorphic
groundness analysis that infers parameterised groundness descriptions of the
variables of interest at a program point. The polymorphic groundness analysis
is designed by replacing two primitive operators used in a monomorphic
groundness analysis and is shown to be as precise as the monomorphic groundness
analysis for any possible values for mode parameters. Experimental results of a
prototype implementation of the polymorphic groundness analysis are given.


title:
Factorization of linear partial differential operators and Darboux
  integrability of nonlinear PDEs

abstract:
  Using a new definition of generalized divisors we prove that the lattice of
such divisors for a given linear partial differential operator is modular and
obtain analogues of the well-known theorems of the Loewy-Ore theory of
factorization of linear ordinary differential operators. Possible applications
to factorized Groebner bases computations in the commutative and
non-commutative cases are discussed, an application to finding criterions of
Darboux integrability of nonlinear PDEs is given.


title: A Winnow-Based Approach to Context-Sensitive Spelling Correction

abstract:
  A large class of machine-learning problems in natural language require the
characterization of linguistic context. Two characteristic properties of such
problems are that their feature space is of very high dimensionality, and their
target concepts refer to only a small subset of the features in the space.
Under such conditions, multiplicative weight-update algorithms such as Winnow
have been shown to have exceptionally good theoretical properties. We present
an algorithm combining variants of Winnow and weighted-majority voting, and
apply it to a problem in the aforementioned class: context-sensitive spelling
correction. This is the task of fixing spelling errors that happen to result in
valid words, such as substituting "to" for "too", "casual" for "causal", etc.
We evaluate our algorithm, WinSpell, by comparing it against BaySpell, a
statistics-based method representing the state of the art for this task. We
find: (1) When run with a full (unpruned) set of features, WinSpell achieves
accuracies significantly higher than BaySpell was able to achieve in either the
pruned or unpruned condition; (2) When compared with other systems in the
literature, WinSpell exhibits the highest performance; (3) The primary reason
that WinSpell outperforms BaySpell is that WinSpell learns a better linear
separator; (4) When run on a test set drawn from a different corpus than the
training set was drawn from, WinSpell is better able than BaySpell to adapt,
using a strategy we will present that combines supervised learning on the
training set with unsupervised learning on the (noisy) test set.


title: Does Meaning Evolve?

abstract:
  A common method of making a theory more understandable, is by comparing it to
another theory which has been better developed. Radical interpretation is a
theory which attempts to explain how communication has meaning. Radical
interpretation is treated as another time-dependent theory and compared to the
time dependent theory of biological evolution. The main reason for doing this
is to find the nature of the time dependence; producing analogs between the two
theories is a necessary prerequisite to this and brings up many problems. Once
the nature of the time dependence is better known it might allow the underlying
mechanism to be uncovered. Several similarities and differences are uncovered,
there appear to be more differences than similarities.


title: Writing and Editing Complexity Theory: Tales and Tools

abstract:
  Each researcher should have a full shelf---physical or virtual---of books on
writing and editing prose. Though we make no claim to any special degree of
expertise, we recently edited a book of complexity theory surveys (Complexity
Theory Retrospective II, Springer-Verlag, 1997), and in doing so we were
brought into particularly close contact with the subject of this article, and
with a number of the excellent resources available to writers and editors. In
this article, we list some of these resources, and we also relate some of the
adventures we had as our book moved from concept to reality.


title: Machine Learning of Generic and User-Focused Summarization

abstract:
  A key problem in text summarization is finding a salience function which
determines what information in the source should be included in the summary.
This paper describes the use of machine learning on a training corpus of
documents and their abstracts to discover salience functions which describe
what combination of features is optimal for a given summarization task. The
method addresses both "generic" and user-focused summaries.


title: Second Product Line Practice Workshop Report

abstract:
  The second Software Engineering Institute Product Line Practice Workshop was
a hands-on meeting held in November 1997 to share industry practices in
software product lines and to explore the technical and non-technical issues
involved. This report synthesizes the workshop presentations and discussions,
which identified factors involved in product line practices and analyzed issues
in the areas of software engineering, technical management, and enterprise
management.


title:
Translating near-synonyms: Possibilities and preferences in the
  interlingua

abstract:
  This paper argues that an interlingual representation must explicitly
represent some parts of the meaning of a situation as possibilities (or
preferences), not as necessary or definite components of meaning (or
constraints). Possibilities enable the analysis and generation of nuance,
something required for faithful translation. Furthermore, the representation of
the meaning of words, especially of near-synonyms, is crucial, because it
specifies which nuances words can convey in which contexts.


title:
Choosing the Word Most Typical in Context Using a Lexical Co-occurrence
  Network

abstract:
  This paper presents a partial solution to a component of the problem of
lexical choice: choosing the synonym most typical, or expected, in context. We
apply a new statistical approach to representing the context of a word through
lexical co-occurrence networks. The implementation was trained and evaluated on
a large corpus, and results show that the inclusion of second-order
co-occurrence relations improves the performance of our implemented lexical
choice program.


title: Learning to Resolve Natural Language Ambiguities: A Unified Approach

abstract:
  We analyze a few of the commonly used statistics based and machine learning
algorithms for natural language disambiguation tasks and observe that they can
be re-cast as learning linear separators in the feature space. Each of the
methods makes a priori assumptions, which it employs, given the data, when
searching for its hypothesis. Nevertheless, as we show, it searches a space
that is as rich as the space of all linear separators. We use this to build an
argument for a data driven approach which merely searches for a good linear
separator in the feature space, without further assumptions on the domain or a
specific problem.
  We present such an approach - a sparse network of linear separators,
utilizing the Winnow learning algorithm - and show how to use it in a variety
of ambiguity resolution problems. The learning approach presented is
attribute-efficient and, therefore, appropriate for domains having very large
number of attributes.
  In particular, we present an extensive experimental comparison of our
approach with other methods on several well studied lexical disambiguation
tasks such as context-sensitive spelling correction, prepositional phrase
attachment and part of speech tagging. In all cases we show that our approach
either outperforms other methods tried for these tasks or performs comparably
to the best.


title: Case Study in Survivable Network System Analysis

abstract:
  This paper presents a method for analyzing the survivability of distributed
network systems and an example of its application.


title:
Deriving Abstract Semantics for Forward Analysis of Normal Logic
  Programs

abstract:
  The problem of forward abstract interpretation of {\em normal} logic programs
has not been formally addressed in the literature although negation as failure
is dealt with through the built-in predicate ! in the way it is implemented in
Prolog. This paper proposes a solution to this problem by deriving two generic
fixed-point abstract semantics $F^b and $F^\diamond for forward abstract
interpretation of {\em normal} logic programs. $F^b$ is intended for inferring
data descriptions for edges in the program graph where an edge denotes the
possibility that the control of execution transfers from its source program
point to its destination program point. $F^\diamond$ is derived from $F^b$ and
is intended for inferring data descriptions for textual program points.


title: The Asilomar Report on Database Research

abstract:
  The database research community is rightly proud of success in basic
research, and its remarkable record of technology transfer. Now the field needs
to radically broaden its research focus to attack the issues of capturing,
storing, analyzing, and presenting the vast array of online data. The database
research community should embrace a broader research agenda -- broadening the
definition of database management to embrace all the content of the Web and
other online data stores, and rethinking our fundamental assumptions in light
of technology shifts. To accelerate this transition, we recommend changing the
way research results are evaluated and presented. In particular, we advocate
encouraging more speculative and long-range work, moving conferences to a
poster format, and publishing all research literature on the Web.


title: Abstract State Machines 1988-1998: Commented ASM Bibliography

abstract:
  An annotated bibliography of papers which deal with or use Abstract State
Machines (ASMs), as of January 1998.


title: An Emptiness Algorithm for Regular Types with Set Operators

abstract:
  An algorithm to decide the emptiness of a regular type expression with set
operators given a set of parameterised type definitions is presented. The
algorithm can also be used to decide the equivalence of two regular type
expressions and the inclusion of one regular type expression in another. The
algorithm strictly generalises previous work in that tuple distributivity is
not assumed and set operators are permitted in type expressions.


title: Comparing a statistical and a rule-based tagger for German

abstract:
  In this paper we present the results of comparing a statistical tagger for
German based on decision trees and a rule-based Brill-Tagger for German. We
used the same training corpus (and therefore the same tag-set) to train both
taggers. We then applied the taggers to the same test corpus and compared their
respective behavior and in particular their error rates. Both taggers perform
similarly with an error rate of around 5%. From the detailed error analysis it
can be seen that the rule-based tagger has more problems with unknown words
than the statistical tagger. But the results are opposite for tokens that are
many-ways ambiguous. If the unknown words are fed into the taggers with the
help of an external lexicon (such as the Gertwol system) the error rate of the
rule-based tagger drops to 4.7%, and the respective rate of the statistical
taggers drops to around 3.7%. Combining the taggers by using the output of one
tagger to help the other did not lead to any further improvement.


title: Formulas as Programs

abstract:
  We provide here a computational interpretation of first-order logic based on
a constructive interpretation of satisfiability w.r.t. a fixed but arbitrary
interpretation. In this approach the formulas themselves are programs. This
contrasts with the so-called formulas as types approach in which the proofs of
the formulas are typed terms that can be taken as programs. This view of
computing is inspired by logic programming and constraint logic programming but
differs from them in a number of crucial aspects.
  Formulas as programs is argued to yield a realistic approach to programming
that has been realized in the implemented programming language ALMA-0 (Apt et
al.) that combines the advantages of imperative and logic programming. The work
here reported can also be used to reason about the correctness of non-recursive
ALMA-0 programs that do not include destructive assignment.


title: P-model Alternative to the T-model

abstract:
  Standard linguistic analysis of syntax uses the T-model. This model requires
the ordering: D-structure $>$ S-structure $>$ LF. Between each of these
representations there is movement which alters the order of the constituent
words; movement is achieved using the principles and parameters of syntactic
theory. Psychological serial models do not accommodate the T-model immediately
so that here a new model called the P-model is introduced. Here it is argued
that the LF representation should be replaced by a variant of Frege's three
qualities. In the F-representation the order of elements is not necessarily the
same as that in LF and it is suggested that the correct ordering is:
F-representation $>$ D-structure $>$ S-structure. Within this framework
movement originates as the outcome of emphasis applied to the sentence.


title: Locked and Unlocked Polygonal Chains in 3D

abstract:
  In this paper, we study movements of simple polygonal chains in 3D. We say
that an open, simple polygonal chain can be straightened if it can be
continuously reconfigured to a straight sequence of segments in such a manner
that both the length of each link and the simplicity of the chain are
maintained throughout the movement. The analogous concept for closed chains is
convexification: reconfiguration to a planar convex polygon. Chains that cannot
be straightened or convexified are called locked. While there are open chains
in 3D that are locked, we show that if an open chain has a simple orthogonal
projection onto some plane, it can be straightened. For closed chains, we show
that there are unknotted but locked closed chains, and we provide an algorithm
for convexifying a planar simple polygon in 3D with a polynomial number of
moves.


title: Digitizing Legacy Documents: A Knowledge-Base Preservation Project

abstract:
  This paper addresses the issue of making legacy information (that material
held in paper format only) electronically searchable and retrievable. We used
proprietary software and commercial hardware to create a process for scanning,
cataloging, archiving and electronically disseminating full-text documents.
This process is relatively easy to implement and reasonably affordable.


title:
Automatic Hardware Synthesis for a Hybrid Reconfigurable CPU Featuring
  Philips CPLDs

abstract:
  A high-level architecture of a Hybrid Reconfigurable CPU, based on a
Philips-supported core processor, is introduced. It features the Philips XPLA2
CPLD as a reconfigurable functional unit. A compilation chain is presented, in
which automatic implementation of time-critical program segments in custom
hardware is performed. The entire process is transparent from the programmer's
point of view. The hardware synthesis module of the chain, which translates
segments of assembly code into a hardware netlist, is discussed in details.
Application examples are also presented.


title: Expoiting Syntactic Structure for Language Modeling

abstract:
  The paper presents a language model that develops syntactic structure and
uses it to extract meaningful information from the word history, thus enabling
the use of long distance dependencies. The model assigns probability to every
joint sequence of words--binary-parse-structure with headword annotation and
operates in a left-to-right manner --- therefore usable for automatic speech
recognition. The model, its probabilistic parameterization, and a set of
experiments meant to evaluate its predictive power are presented; an
improvement over standard trigram modeling is achieved.


title: Complexity limitations on quantum computation

abstract:
  We use the powerful tools of counting complexity and generic oracles to help
understand the limitations of the complexity of quantum computation. We show
several results for the probabilistic quantum class BQP.
  1. BQP is low for PP, i.e., PP^BQP=PP.
  2. There exists a relativized world where P=BQP and the polynomial-time
hierarchy is infinite.
  3. There exists a relativized world where BQP does not have complete sets.
  4. There exists a relativized world where P=BQP but P is not equal to UP
intersect coUP and one-way functions exist. This gives a relativized answer to
an open question of Simon.


title: The Essence of Constraint Propagation

abstract:
  We show that several constraint propagation algorithms (also called (local)
consistency, consistency enforcing, Waltz, filtering or narrowing algorithms)
are instances of algorithms that deal with chaotic iteration. To this end we
propose a simple abstract framework that allows us to classify and compare
these algorithms and to establish in a uniform way their basic properties.


title: A Structured Language Model

abstract:
  The paper presents a language model that develops syntactic structure and
uses it to extract meaningful information from the word history, thus enabling
the use of long distance dependencies. The model assigns probability to every
joint sequence of words - binary-parse-structure with headword annotation. The
model, its probabilistic parametrization, and a set of experiments meant to
evaluate its predictive power are presented.


title: Designing an interface to optimize reading with small display windows

abstract:
  The electronic presentation of text in small display windows is mushrooming.
In the present paper, four ways of presenting text in a small display window
were examined and compared to a Normal Page condition: rapid serial visual
presentation (RSVP), RSVP with a Completion Meter, Sentence-by-Sentence
presentation, and Sentence-by-Sentence presentation with a Completion Meter.
Dependent measures were reading efficiency - speed and comprehension - and
preference. For designers of hardware or software with small display windows,
the results suggest the following: (1) Though RSVP is disliked by readers, the
present methods of allowing self-pacing and regressions in RSVP, unlike earlier
tested methods, are efficient and feasible. (2) Slower reading in RSVP should
be achieved by increasing pauses between sentences or by repeating sentences,
not by decreasing the within-sentence rate. (3) Completion meters do not
interfere with performance, and are usually preferred. (4) The space-saving
Sentence-by-Sentence format is as efficient and as preferred as the Normal Page
format.


title: Push vs. Pull in Web-Based Network Management

abstract:
  In this paper, we show how Web technologies can be used effectively to (i)
address some of the deficiencies of traditional IP network management
platforms, and (ii) render these expensive platforms redundant. We build on the
concept of embedded management application, proposed by Wellens and Auerbach,
and present two models of network management application designs that rely on
Web technologies. First, the pull model is based on the request/response
paradigm. It is typically used to perform data polling. Several commercial
management platforms already use Web technologies that rely on this model to
provide for ad hoc management; we demonstrate how to extend this to regular
management. Second, the push model is a novel approach which relies on the
publish/subscribe/distribute paradigm. It is better suited to regular
management than the pull model, and allows administrators to conserve network
bandwidth as well as CPU time on the management station. It can be seen as a
generalization of the paradigm commonly used for notification delivery.
Finally, we introduce the concept of the collapsed network management platform,
where these two models coexist.


title: TCP Trunking

abstract:
  A TCP trunk is an IP tunnel under TCP control, capable of carrying packets
from any number of user flows. By exploiting properties of TCP, a TCP trunk
provides elastic and reliable transmission over a network, and automatically
shares the network fairly with other competing trunks. Moreover, by aggregating
user flows into a single trunk flow, TCP trunking can significantly reduce the
number of flows that the network needs to manage, thereby allowing use of
simplified management to achieve improved perfor mance. For example, when
dealing with only a small number of TCP trunk flows, a router with a simple
FIFO buffer can experience low packet loss rates.
  A TCP trunk is a "soft" circuit in the sense that it requires no flow states
to be maintained inside the network. Setting up a TCP trunk involves only
configuring the two end nodes. This is in contrast with traditional methods of
configuring circuits via signaling of network nodes.
  A simple packet-dropping mechanism based on packet accounting at the
transmitter of a TCP trunk assures that, when the trunk reduces its bandwidth
in response to network congestion, user TCP flows carried by the trunk will
reduce their bandwidths by the same proportion. Simu lation results have
demonstrated that TCP trunks can provide improved network performance to users,
while achieving high network utilization.


title:
A Human - machine interface for teleoperation of arm manipulators in a
  complex environment

abstract:
  This paper discusses the feasibility of using configuration space (C-space)
as a means of visualization and control in operator-guided real-time motion of
a robot arm manipulator. The motivation is to improve performance of the human
operator in tasks involving the manipulator motion in an environment with
obstacles. Unlike some other motion planning tasks, operators are known to make
expensive mistakes in such tasks, even in a simpler two-dimensional case. They
have difficulty learning better procedures and their performance improves very
little with practice. Using an example of a two-dimensional arm manipulator, we
show that translating the problem into C-space improves the operator
performance rather remarkably, on the order of magnitude compared to the usual
work space control. An interface that makes the transfer possible is described,
and an example of its use in a virtual environment is shown.


title:
Generating Segment Durations in a Text-To-Speech System: A Hybrid
  Rule-Based/Neural Network Approach

abstract:
  A combination of a neural network with rule firing information from a
rule-based system is used to generate segment durations for a text-to-speech
system. The system shows a slight improvement in performance over a neural
network system without the rule firing information. Synthesized speech using
segment durations was accepted by listeners as having about the same quality as
speech generated using segment durations extracted from natural speech.


title: Speech Synthesis with Neural Networks

abstract:
  Text-to-speech conversion has traditionally been performed either by
concatenating short samples of speech or by using rule-based systems to convert
a phonetic representation of speech into an acoustic representation, which is
then converted into speech. This paper describes a system that uses a
time-delay neural network (TDNN) to perform this phonetic-to-acoustic mapping,
with another neural network to control the timing of the generated speech. The
neural network system requires less memory than a concatenation system, and
performed well in tests comparing it to commercial systems using other
technologies.


title:
Text-To-Speech Conversion with Neural Networks: A Recurrent TDNN
  Approach

abstract:
  This paper describes the design of a neural network that performs the
phonetic-to-acoustic mapping in a speech synthesis system. The use of a
time-domain neural network architecture limits discontinuities that occur at
phone boundaries. Recurrent data input also helps smooth the output parameter
tracks. Independent testing has demonstrated that the voice quality produced by
this system compares favorably with speech from existing commercial
text-to-speech systems.


title:
A Probabilistic Approach to Lexical Semantic Knowledge Acquisition and S
  tructural Disambiguation

abstract:
  In this thesis, I address the problem of automatically acquiring lexical
semantic knowledge, especially that of case frame patterns, from large corpus
data and using the acquired knowledge in structural disambiguation. The
approach I adopt has the following characteristics: (1) dividing the problem
into three subproblems: case slot generalization, case dependency learning, and
word clustering (thesaurus construction). (2) viewing each subproblem as that
of statistical estimation and defining probability models for each subproblem,
(3) adopting the Minimum Description Length (MDL) principle as learning
strategy, (4) employing efficient learning algorithms, and (5) viewing the
disambiguation problem as that of statistical prediction. Major contributions
of this thesis include: (1) formalization of the lexical knowledge acquisition
problem, (2) development of a number of learning methods for lexical knowledge
acquisition, and (3) development of a high-performance disambiguation method.


title: Training Reinforcement Neurocontrollers Using the Polytope Algorithm

abstract:
  A new training algorithm is presented for delayed reinforcement learning
problems that does not assume the existence of a critic model and employs the
polytope optimization algorithm to adjust the weights of the action network so
that a simple direct measure of the training performance is maximized.
Experimental results from the application of the method to the pole balancing
problem indicate improved training performance compared with critic-based and
genetic reinforcement approaches.


title:
Neural Network Methods for Boundary Value Problems Defined in
  Arbitrarily Shaped Domains

abstract:
  Partial differential equations (PDEs) with Dirichlet boundary conditions
defined on boundaries with simple geometry have been succesfuly treated using
sigmoidal multilayer perceptrons in previous works. This article deals with the
case of complex boundary geometry, where the boundary is determined by a number
of points that belong to it and are closely located, so as to offer a
reasonable representation. Two networks are employed: a multilayer perceptron
and a radial basis function network. The later is used to account for the
satisfaction of the boundary conditions. The method has been successfuly tested
on two-dimensional and three-dimensional PDEs and has yielded accurate
solutions.

categories: cs.NE cond-mat.dis-nn cs.NA math-ph math.MP math.NA physics.comp-ph


title: Name Strategy: Its Existence and Implications

abstract:
  It is argued that colour name strategy, object name strategy, and chunking
strategy in memory are all aspects of the same general phenomena, called
stereotyping. It is pointed out that the Berlin-Kay universal partial ordering
of colours and the frequency of traffic accidents classified by colour are
surprisingly similar. Some consequences of the existence of a name strategy for
the philosophy of language and mathematics are discussed. It is argued that
real valued quantities occur {\it ab initio}. The implication of real valued
truth quantities is that the {\bf Continuum Hypothesis} of pure mathematics is
side-stepped. The existence of name strategy shows that thought/sememes and
talk/phonemes can be separate, and this vindicates the assumption of thought
occurring before talk used in psycholinguistic speech production models.


title: Optimal Multi-Paragraph Text Segmentation by Dynamic Programming

abstract:
  There exist several methods of calculating a similarity curve, or a sequence
of similarity values, representing the lexical cohesion of successive text
constituents, e.g., paragraphs. Methods for deciding the locations of fragment
boundaries are, however, scarce. We propose a fragmentation method based on
dynamic programming. The method is theoretically sound and guaranteed to
provide an optimal splitting on the basis of a similarity curve, a preferred
fragment length, and a cost function defined. The method is especially useful
when control on fragment size is of importance.


title:
A High Quality Text-To-Speech System Composed of Multiple Neural
  Networks

abstract:
  While neural networks have been employed to handle several different
text-to-speech tasks, ours is the first system to use neural networks
throughout, for both linguistic and acoustic processing. We divide the
text-to-speech task into three subtasks, a linguistic module mapping from text
to a linguistic representation, an acoustic module mapping from the linguistic
representation to speech, and a video module mapping from the linguistic
representation to animated images. The linguistic module employs a
letter-to-sound neural network and a postlexical neural network. The acoustic
module employs a duration neural network and a phonetic neural network. The
visual neural network is employed in parallel to the acoustic module to drive a
talking head. The use of neural networks that can be retrained on the
characteristics of different voices and languages affords our system a degree
of adaptability and naturalness heretofore unavailable.


title: Minimum Cuts in Near-Linear Time

abstract:
  We significantly improve known time bounds for solving the minimum cut
problem on undirected graphs. We use a ``semi-duality'' between minimum cuts
and maximum spanning tree packings combined with our previously developed
random sampling techniques. We give a randomized algorithm that finds a minimum
cut in an m-edge, n-vertex graph with high probability in O(m log^3 n) time. We
also give a simpler randomized algorithm that finds all minimum cuts with high
probability in O(n^2 log n) time. This variant has an optimal RNC
parallelization. Both variants improve on the previous best time bound of O(n^2
log^3 n). Other applications of the tree-packing approach are new, nearly tight
bounds on the number of near minimum cuts a graph may have and a new data
structure for representing them in a space-efficient manner.


title: Approximate Graph Coloring by Semidefinite Programming

abstract:
  We consider the problem of coloring k-colorable graphs with the fewest
possible colors. We present a randomized polynomial time algorithm that colors
a 3-colorable graph on $n$ vertices with min O(Delta^{1/3} log^{1/2} Delta log
n), O(n^{1/4} log^{1/2} n) colors where Delta is the maximum degree of any
vertex. Besides giving the best known approximation ratio in terms of n, this
marks the first non-trivial approximation result as a function of the maximum
degree Delta. This result can be generalized to k-colorable graphs to obtain a
coloring using min O(Delta^{1-2/k} log^{1/2} Delta log n), O(n^{1-3/(k+1)}
log^{1/2} n) colors. Our results are inspired by the recent work of Goemans and
Williamson who used an algorithm for semidefinite optimization problems, which
generalize linear programs, to obtain improved approximations for the MAX CUT
and MAX 2-SAT problems. An intriguing outcome of our work is a duality
relationship established between the value of the optimum solution to our
semidefinite program and the Lovasz theta-function. We show lower bounds on the
gap between the optimum solution of our semidefinite program and the actual
chromatic number; by duality this also demonstrates interesting new facts about
the theta-function.


title:
Vocal Access to a Newspaper Archive: Design Issues and Preliminary
  Investigation

abstract:
  This paper presents the design and the current prototype implementation of an
interactive vocal Information Retrieval system that can be used to access
articles of a large newspaper archive using a telephone. The results of
preliminary investigation into the feasibility of such a system are also
presented.


title: Towards a computational theory of human daydreaming

abstract:
  This paper examines the phenomenon of daydreaming: spontaneously recalling or
imagining personal or vicarious experiences in the past or future. The
following important roles of daydreaming in human cognition are postulated:
plan preparation and rehearsal, learning from failures and successes, support
for processes of creativity, emotion regulation, and motivation.
  A computational theory of daydreaming and its implementation as the program
DAYDREAMER are presented. DAYDREAMER consists of 1) a scenario generator based
on relaxed planning, 2) a dynamic episodic memory of experiences used by the
scenario generator, 3) a collection of personal goals and control goals which
guide the scenario generator, 4) an emotion component in which daydreams
initiate, and are initiated by, emotional states arising from goal outcomes,
and 5) domain knowledge of interpersonal relations and common everyday
occurrences.
  The role of emotions and control goals in daydreaming is discussed. Four
control goals commonly used in guiding daydreaming are presented:
rationalization, failure/success reversal, revenge, and preparation. The role
of episodic memory in daydreaming is considered, including how daydreamed
information is incorporated into memory and later used. An initial version of
DAYDREAMER which produces several daydreams (in English) is currently running.


title: A nested transaction mechanism for LOCUS

abstract:
  A working implementation of nested transactions has been produced for LOCUS,
an integrated distributed operating system which provides a high degree of
network transparency. Several aspects of our mechanism are novel. First, the
mechanism allows a transaction to access objects directly without regard to the
location of the object. Second, processes running on behalf of a single
transaction may be located at many sites. Thus there is no need to invoke a new
transaction to perform processing or access objects at a remote site. Third,
unlike other environments, LOCUS allows replication of data objects at more
than one site in the network, and this capability is incorporated into the
transaction mechanism. If the copy of an object that is currently being
accessed becomes unavailable, it is possible to continue work by using another
one of the replicated copies. Finally, an efficient orphan removal algorithm is
presented, and the problem of providing continued operation during network
partitions is addressed in detail.


title:
Quantum simulations of classical random walks and undirected graph
  connectivity

abstract:
  It is not currently known if quantum Turing machines can efficiently simulate
probabilistic computations in the space-bounded case. In this paper we show
that space-bounded quantum Turing machines can efficiently simulate a limited
class of random processes: random walks on undirected graphs. By means of such
simulations, it is demonstrated that the undirected graph connectivity problem
for regular graphs can be solved by one-sided error quantum Turing machines
that run in logspace and halt absolutely. It follows that symmetric logspace is
contained in the quantum analogue of randomized logspace.


title: The Self-Organizing Symbiotic Agent

abstract:
  In [N. A. Baas, Emergence, Hierarchies, and Hyper-structures, in C.G. Langton
ed., Artificial Life III, Addison Wesley, 1994.] a general framework for the
study of Emergence and hyper-structure was presented. This approach is mostly
concerned with the description of such systems. In this paper we will try to
bring forth a different aspect of this model we feel will be useful in the
engineering of agent based solutions, namely the symbiotic approach. In this
approach a self-organizing method of dividing the more complex "main-problem"
to a hyper-structure of "sub-problems" with the aim of reducing complexity is
desired. A description of the general problem will be given along with some
instances of related work. This paper is intended to serve as an introductory
challenge for general solutions to the described problem.


title: An Adaptive Agent Oriented Software Architecture

abstract:
  A new approach to software design based on an agent-oriented architecture is
presented. Unlike current research, we consider software to be designed and
implemented with this methodology in mind. In this approach agents are
considered adaptively communicating concurrent modules which are divided into a
white box module responsible for the communications and learning, and a black
box which is the independent specialized processes of the agent. A distributed
Learning policy is also introduced for adaptability.


title:
Adaptive Interaction Using the Adaptive Agent Oriented Software
  Architecture (AAOSA)

abstract:
  User interfaces that adapt their characteristics to those of the user are
referred to as adaptive interfaces. We propose Adaptive Agent Oriented Software
Architecture (AAOSA) as a new way of designing adaptive interfaces. AAOSA is a
new approach to software design based on an agent-oriented architecture. In
this approach agents are considered adaptively communicating concurrent modules
which are divided into a white box module responsible for the communications
and learning, and a black box which is responsible for the independent
specialized processes of the agent. A distributed learning policy that makes
use of this architecture is used for purposes of system adaptability.


title: Making the most of electronic journals

abstract:
  As most electronic journals available today have been derived from print
originals, print journals have become a vital element in the broad development
of electronic journals publishing. Further dependence on the print publishing
model, however, will be a constraint on the continuing development of
e-journals, and a series of conflicts are likely to arise. Making the most of
e-journals requires that a distinctive new publishing model is developed. We
consider some of the issues that will be fundamental in this new model,
starting with user motivations and some reported publisher experiences, both of
which suggest a broadening desire for comprehensive linked archives. This leads
in turn to questions about the impact of rights assignment by authors, in
particular the common practice of giving exlusive rights to publishers for
individual works. Some non-prescriptive solutions are suggested, and four steps
towards optimum e-journals are proposed.


title:
A reusable iterative optimization software library to solve
  combinatorial problems with approximate reasoning

abstract:
  Real world combinatorial optimization problems such as scheduling are
typically too complex to solve with exact methods. Additionally, the problems
often have to observe vaguely specified constraints of different importance,
the available data may be uncertain, and compromises between antagonistic
criteria may be necessary. We present a combination of approximate reasoning
based constraints and iterative optimization based heuristics that help to
model and solve such problems in a framework of C++ software libraries called
StarFLIP++. While initially developed to schedule continuous caster units in
steel plants, we present in this paper results from reusing the library
components in a shift scheduling system for the workforce of an industrial
production plant.


title: A Flexible Shallow Approach to Text Generation

abstract:
  In order to support the efficient development of NL generation systems, two
orthogonal methods are currently pursued with emphasis: (1) reusable, general,
and linguistically motivated surface realization components, and (2) simple,
task-oriented template-based techniques. In this paper we argue that, from an
application-oriented perspective, the benefits of both are still limited. In
order to improve this situation, we suggest and evaluate shallow generation
methods associated with increased flexibility. We advise a close connection
between domain-motivated and linguistic ontologies that supports the quick
adaptation to new tasks and domains, rather than the reuse of general
resources. Our method is especially designed for generating reports with
limited linguistic variations.


title: Symmetries and transitions of bounded Turing machines

abstract:
  We consider the structures given by repeatedly generalising the definition of
finite state automata by symmetry considerations, and constructing analogues of
transition monoids at each step. This approach first gives us non-deterministic
automata, then (non-deterministic) two-way automata and bounded Turing machines
--- that is, Turing machines where the read / write head is unable to move past
the end of the input word.
  In the case of two-way automata, the transition monoids generalise to
endomorphism monoids in compact closed categories. These use Girard's
resolution formula (from the Geometry of Interaction representation of linear
logic) to construct the images of singleton words.
  In the case of bounded Turing machines, the transition homomorphism
generalises to a monoid homomorphism from the natural numbers to a monoid
constructed from the union of endomorphism monoids of a compact closed
category, together with an appropriate composition. These use Girard's
execution formula (also from the Geometry of Interaction representation of
linear logic) to construct images of singletons.


title:
The Computing Research Repository: Promoting the Rapid Dissemination and
  Archiving of Computer Science Research

abstract:
  We describe the Computing Research Repository (CoRR), a new electronic
archive for rapid dissemination and archiving of computer science research
results. CoRR was initiated in September 1998 through the cooperation of ACM,
LANL (Los Alamos National Laboratory) e-Print archive, and NCSTRL (Networked
Computer Science Technical Research Library. Through its implementation of the
Dienst protocol, CoRR combines the open and extensible architecture of NCSTRL
with the reliable access and well-established management practices of the LANL
XXX e-Print repository. This architecture will allow integration with other
e-Print archives and provides a foundation for a future broad-based scholarly
digital library. We describe the decisions that were made in creating CoRR, the
architecture of the CoRR/NCSTRL interoperation, and issues that have arisen
during the operation of CoRR.


title: Forgetting Exceptions is Harmful in Language Learning

abstract:
  We show that in language learning, contrary to received wisdom, keeping
exceptional training instances in memory can be beneficial for generalization
accuracy. We investigate this phenomenon empirically on a selection of
benchmark natural language processing tasks: grapheme-to-phoneme conversion,
part-of-speech tagging, prepositional-phrase attachment, and base noun phrase
chunking. In a first series of experiments we combine memory-based learning
with training set editing techniques, in which instances are edited based on
their typicality and class prediction strength. Results show that editing
exceptional instances (with low typicality or low class prediction strength)
tends to harm generalization accuracy. In a second series of experiments we
compare memory-based learning and decision-tree learning methods on the same
selection of tasks, and find that decision-tree learning often performs worse
than memory-based learning. Moreover, the decrease in performance can be linked
to the degree of abstraction from exceptions (i.e., pruning or eagerness). We
provide explanations for both results in terms of the properties of the natural
language processing tasks and the learning algorithms.


title: Hypertree Decompositions and Tractable Queries

abstract:
  Several important decision problems on conjunctive queries (CQs) are
NP-complete in general but become tractable, and actually highly
parallelizable, if restricted to acyclic or nearly acyclic queries. Examples
are the evaluation of Boolean CQs and query containment. These problems were
shown tractable for conjunctive queries of bounded treewidth and of bounded
degree of cyclicity. The so far most general concept of nearly acyclic queries
was the notion of queries of bounded query-width introduced by Chekuri and
Rajaraman (1997). While CQs of bounded query width are tractable, it remained
unclear whether such queries are efficiently recognizable. Chekuri and
Rajaraman stated as an open problem whether for each constant k it can be
determined in polynomial time if a query has query width less than or equal to
k. We give a negative answer by proving this problem NP-complete (specifically,
for k=4). In order to circumvent this difficulty, we introduce the new concept
of hypertree decomposition of a query and the corresponding notion of hypertree
width. We prove: (a) for each k, the class of queries with query width bounded
by k is properly contained in the class of queries whose hypertree width is
bounded by k; (b) unlike query width, constant hypertree-width is efficiently
recognizable; (c) Boolean queries of constant hypertree width can be
efficiently evaluated.


title: Virtual Kathakali : Gesture Driven Metamorphosis

abstract:
  Training in motor skills such as athletics, dance, or gymnastics is not
possible today except in the direct presence of the coach/instructor. This
paper describes a computer vision based gesture recognition system which is
used to metamorphose the user into a Virtual person, e.g. as a Kathakali
dancer, which is graphically recreated at a near or diatant location. Thus this
can be seen by an off-site coach using low-bandwidth joint-motion data which
permits real time animation. The metamorphosis involves altering the appearance
and identity of the user and also creating a specific environment possibly in
interaction with other virtual creatures.
  A robust vision module is used to identify the user, based on very simple
binary image processing in real time which also manages to resolve
self-occlusion, correct for clothing/colour and other variations among users.
Gestures are identified by locating key points at the shoulder, elbow and wrist
joint, which are then recreated in an articulated humanoid model, which in this
instance, representes a Kathakali dancer in elaborate traditional dress. Unlike
glove based or other and movement tracking systems, this application requires
the user to wear no hardwire devices and is aimed at making gesture tracking
simpler, cheaper, and more user friendly.


title:
TDLeaf(lambda): Combining Temporal Difference Learning with Game-Tree
  Search

abstract:
  In this paper we present TDLeaf(lambda), a variation on the TD(lambda)
algorithm that enables it to be used in conjunction with minimax search. We
present some experiments in both chess and backgammon which demonstrate its
utility and provide comparisons with TD(lambda) and another less radical
variant, TD-directed(lambda). In particular, our chess program, ``KnightCap,''
used TDLeaf(lambda) to learn its evaluation function while playing on the Free
Internet Chess Server (FICS, fics.onenet.net). It improved from a 1650 rating
to a 2100 rating in just 308 games. We discuss some of the reasons for this
success and the relationship between our results and Tesauro's results in
backgammon.


title:
KnightCap: A chess program that learns by combining TD(lambda) with
  game-tree search

abstract:
  In this paper we present TDLeaf(lambda), a variation on the TD(lambda)
algorithm that enables it to be used in conjunction with game-tree search. We
present some experiments in which our chess program ``KnightCap'' used
TDLeaf(lambda) to learn its evaluation function while playing on the Free
Internet Chess Server (FICS, fics.onenet.net). The main success we report is
that KnightCap improved from a 1650 rating to a 2150 rating in just 308 games
and 3 days of play. As a reference, a rating of 1650 corresponds to about level
B human play (on a scale from E (1000) to A (1800)), while 2150 is human master
level. We discuss some of the reasons for this success, principle among them
being the use of on-line, rather than self-play.


title: Fixpoint 3-valued semantics for autoepistemic logic

abstract:
  The paper presents a constructive fixpoint semantics for autoepistemic logic
(AEL). This fixpoint characterizes a unique but possibly three-valued belief
set of an autoepistemic theory. It may be three-valued in the sense that for a
subclass of formulas F, the fixpoint may not specify whether F is believed or
not. The paper presents a constructive 3-valued semantics for autoepistemic
logic (AEL). We introduce a derivation operator and define the semantics as its
least fixpoint. The semantics is 3-valued in the sense that, for some formulas,
the least fixpoint does not specify whether they are believed or not. We show
that complete fixpoints of the derivation operator correspond to Moore's stable
expansions. In the case of modal representations of logic programs our least
fixpoint semantics expresses well-founded semantics or 3-valued Fitting-Kunen
semantics (depending on the embedding used). We show that, computationally, our
semantics is simpler than the semantics proposed by Moore (assuming that the
polynomial hierarchy does not collapse).


title:
On the geometry of similarity search: dimensionality curse and
  concentration of measure

abstract:
  We suggest that the curse of dimensionality affecting the similarity-based
search in large datasets is a manifestation of the phenomenon of concentration
of measure on high-dimensional structures. We prove that, under certain
geometric assumptions on the query domain $\Omega$ and the dataset $X$, if
$\Omega$ satisfies the so-called concentration property, then for most query
points $x^\ast$ the ball of radius $(1+\e)d_X(x^\ast)$ centred at $x^\ast$
contains either all points of $X$ or else at least $C_1\exp(-C_2\e^2n)$ of
them. Here $d_X(x^\ast)$ is the distance from $x^\ast$ to the nearest neighbour
in $X$ and $n$ is the dimension of $\Omega$.


title: An Empirical Approach to Temporal Reference Resolution (journal version)

abstract:
  Scheduling dialogs, during which people negotiate the times of appointments,
are common in everyday life. This paper reports the results of an in-depth
empirical investigation of resolving explicit temporal references in scheduling
dialogs. There are four phases of this work: data annotation and evaluation,
model development, system implementation and evaluation, and model evaluation
and analysis. The system and model were developed primarily on one set of data,
and then applied later to a much more complex data set, to assess the
generalizability of the model for the task being performed. Many different
types of empirical methods are applied to pinpoint the strengths and weaknesses
of the approach. Detailed annotation instructions were developed and an
intercoder reliability study was performed, showing that naive annotators can
reliably perform the targeted annotations. A fully automatic system has been
developed and evaluated on unseen test data, with good results on both data
sets. We adopt a pure realization of a recency-based focus model to identify
precisely when it is and is not adequate for the task being addressed. In
addition to system results, an in-depth evaluation of the model itself is
presented, based on detailed manual annotations. The results are that few
errors occur specifically due to the model of focus being used, and the set of
anaphoric relations defined in the model are low in ambiguity for both data
sets.


title: Object Oriented and Functional Programming for Symbolic Manipulation

abstract:
  The advantages of mixed approach with using different kinds of programming
techniques for symbolic manipulation are discussed. The main purpose of
approach offered is merge the methods of object oriented programming that
convenient for presentation data and algorithms for user with advantages of
functional languages for data manipulation, internal presentation, and
portability of software.


title: Universal Object Oriented Languages and Computer Algebra

abstract:
  The universal object oriented languages made programming more simple and
efficient. In the article is considered possibilities of using similar methods
in computer algebra. A clear and powerful universal language is useful if
particular problem was not implemented in standard software packages like
REDUCE, MATHEMATICA, etc. and if the using of internal programming languages of
the packages looks not very efficient.
  Functional languages like LISP had some advantages and traditions for
algebraic and symbolic manipulations. Functional and object oriented
programming are not incompatible ones. An extension of the model of an object
for manipulation with pure functions and algebraic expressions is considered.


title:
Fast Computational Algorithms for the Discrete Wavelet Transform and
  Applications of Localized Orthonormal Bases in Signal Classification

abstract:
  We construct an algorithm for implementing the discrete wavelet transform by
means of matrices in SO_2(R) for orthonormal compactly supported wavelets and
matrices in SL_m(R), m > = 2, for compactly supported biorthogonal wavelets. We
show that in 1 dimension the total operation count using this algorithm can be
reduced to about 50% of the conventional convolution and downsampling by
2-operation for both orthonormal and biorthogonal filters. In the special case
of biorthogonal symmetric odd-odd filters, we show an implementation yielding a
total operation count of about 38% of the conventional method. In 2 dimensions
we show an implementation of this algorithm yielding a reduction in the total
operation count of about 70% when the filters are orthonormal, a reduction of
about 62% for general biorthogonal filters, and a reduction of about 70% if the
filters are symmetric odd-odd length filters. We further extend these results
to 3 dimensions. We also show how the SO_2(R)-method for implementing the
discrete wavelet transform may be exploited to compute short FIR filters, and
we construct edge mappings where we try to improve upon the degree of
preservation of regularity in the conventional methods. We also consider a
two-class waveform discrimination problem. A statistical space-frequency
analysis is performed on a training data set using the LDB-algorithm of N.Saito
and R.Coifman. The success of the algorithm on this particular problem is
evaluated on a disjoint test data set.


title:
Competition and cooperation: Libraries and publishers in the transition
  to electronic scholarly journals

abstract:
  The conversion of scholarly journals to digital format is proceeding rapidly,
especially for those from large commercial and learned society publishers. This
conversion offers the best hope for survival for such publishers. The infamous
"journal crisis" is more of a library cost crisis than a publisher pricing
problem, with internal library costs much higher than the amount spent on
purchasing books and journals. Therefore publishers may be able to retain or
even increase their revenues and profits, while at the same time providing a
superior service. To do this, they will have to take over many of the function
of libraries, and they can do that only in the digital domain. This paper
examines publishers' strategies, how they are likely to evolve, and how they
will affect libraries.


title: Average-Case Complexity of Shellsort

abstract:
  We prove a general lower bound on the average-case complexity of Shellsort:
the average number of data-movements (and comparisons) made by a $p$-pass
Shellsort for any incremental sequence is $\Omega (pn^{1 + 1/p)$ for all $p
\leq \log n$. Using similar arguments, we analyze the average-case complexity
of several other sorting algorithms.


title: A Brief History of the Internet

abstract:
  The Internet has revolutionized the computer and communications world like
nothing before. The invention of the telegraph, telephone, radio, and computer
set the stage for this unprecedented integration of capabilities. The Internet
is at once a world-wide broadcasting capability, a mechanism for information
dissemination, and a medium for collaboration and interaction between
individuals and their computers without regard for geographic location.
  In this paper, several of us involved in the development and evolution of the
Internet share our views of its origins and history. This is intended to be a
brief, necessarily cursory and incomplete history. This history revolves around
four distinct aspects. There is the technological evolution that began with
early research on packet switching and the ARPANET (and related technologies),
and where current research continues to expand the horizons of the
infrastructure along several dimensions, such as scale, performance, and higher
level functionality. There is the operations and management aspect of a global
and complex operational infrastructure. There is the social aspect, which
resulted in a broad community of Internauts working together to create and
evolve the technology. And there is the commercialization aspect, resulting in
an extremely effective transition of research results into a broadly deployed
and available information infrastructure.