title: Extremal problems in logic programming and stable model computation

abstract:
  We study the following problem: given a class of logic programs C, determine
the maximum number of stable models of a program from C. We establish the
maximum for the class of all logic programs with at most n clauses, and for the
class of all logic programs of size at most n. We also characterize the
programs for which the maxima are attained. We obtain similar results for the
class of all disjunctive logic programs with at most n clauses, each of length
at most m, and for the class of all disjunctive logic programs of size at most
n. Our results on logic programs have direct implication for the design of
algorithms to compute stable models. Several such algorithms, similar in spirit
to the Davis-Putnam procedure, are described in the paper. Our results imply
that there is an algorithm that finds all stable models of a program with n
clauses after considering the search space of size O(3^{n/3}) in the worst
case. Our results also provide some insights into the question of
representability of families of sets as families of stable models of logic
programs.


title:
Analysis of approximate nearest neighbor searching with clustered point
  sets

abstract:
  We present an empirical analysis of data structures for approximate nearest
neighbor searching. We compare the well-known optimized kd-tree splitting
method against two alternative splitting methods. The first, called the
sliding-midpoint method, which attempts to balance the goals of producing
subdivision cells of bounded aspect ratio, while not producing any empty cells.
The second, called the minimum-ambiguity method is a query-based approach. In
addition to the data points, it is also given a training set of query points
for preprocessing. It employs a simple greedy algorithm to select the splitting
plane that minimizes the average amount of ambiguity in the choice of the
nearest neighbor for the training points. We provide an empirical analysis
comparing these two methods against the optimized kd-tree construction for a
number of synthetically generated data and query sets. We demonstrate that for
clustered data and query sets, these algorithms can provide significant
improvements over the standard kd-tree construction for approximate nearest
neighbor searching.


title:
Minimum Description Length Induction, Bayesianism, and Kolmogorov
  Complexity

abstract:
  The relationship between the Bayesian approach and the minimum description
length approach is established. We sharpen and clarify the general modeling
principles MDL and MML, abstracted as the ideal MDL principle and defined from
Bayes's rule by means of Kolmogorov complexity. The basic condition under which
the ideal principle should be applied is encapsulated as the Fundamental
Inequality, which in broad terms states that the principle is valid when the
data are random, relative to every contemplated hypothesis and also these
hypotheses are random relative to the (universal) prior. Basically, the ideal
principle states that the prior probability associated with the hypothesis
should be given by the algorithmic universal probability, and the sum of the
log universal probability of the model plus the log of the probability of the
data given the model should be minimized. If we restrict the model class to the
finite sets then application of the ideal principle turns into Kolmogorov's
minimal sufficient statistic. In general we show that data compression is
almost always the best strategy, both in hypothesis identification and
prediction.

categories: cs.LG cs.AI cs.CC cs.IT cs.LO math.IT math.PR physics.data-an


title: PSPACE has 2-round quantum interactive proof systems

abstract:
  In this paper we consider quantum interactive proof systems, i.e.,
interactive proof systems in which the prover and verifier may perform quantum
computations and exchange quantum messages. It is proved that every language in
PSPACE has a quantum interactive proof system that requires only two rounds of
communication between the prover and verifier, while having exponentially small
(one-sided) probability of error. It follows that quantum interactive proof
systems are strictly more powerful than classical interactive proof systems in
the constant-round case unless the polynomial time hierarchy collapses to the
second level.


title: Representation Theory for Default Logic

abstract:
  Default logic can be regarded as a mechanism to represent families of belief
sets of a reasoning agent. As such, it is inherently second-order. In this
paper, we study the problem of representability of a family of theories as the
set of extensions of a default theory. We give a complete solution to the
representability by means of normal default theories. We obtain partial results
on representability by arbitrary default theories. We construct examples of
denumerable families of non-including theories that are not representable. We
also study the concept of equivalence between default theories.


title: Compacting the Penn Treebank Grammar

abstract:
  Treebanks, such as the Penn Treebank (PTB), offer a simple approach to
obtaining a broad coverage grammar: one can simply read the grammar off the
parse trees in the treebank. While such a grammar is easy to obtain, a
square-root rate of growth of the rule set with corpus size suggests that the
derived grammar is far from complete and that much more treebanked text would
be required to obtain a complete grammar, if one exists at some limit. However,
we offer an alternative explanation in terms of the underspecification of
structures within the treebank. This hypothesis is explored by applying an
algorithm to compact the derived grammar by eliminating redundant rules --
rules whose right hand sides can be parsed by other rules. The size of the
resulting compacted grammar, which is significantly less than that of the full
treebank grammar, is shown to approach a limit. However, such a compacted
grammar does not yield very good performance figures. A version of the
compaction algorithm taking rule probabilities into account is proposed, which
is argued to be more linguistically motivated. Combined with simple
thresholding, this method can be used to give a 58% reduction in grammar size
without significant change in parsing performance, and can produce a 69%
reduction with some gain in recall, but a loss in precision.


title:
Automatic Identification of Subjects for Textual Documents in Digital
  Libraries

abstract:
  The amount of electronic documents in the Internet grows very quickly. How to
effectively identify subjects for documents becomes an important issue. In
past, the researches focus on the behavior of nouns in documents. Although
subjects are composed of nouns, the constituents that determine which nouns are
subjects are not only nouns. Based on the assumption that texts are
well-organized and event-driven, nouns and verbs together contribute the
process of subject identification. This paper considers four factors: 1) word
importance, 2) word frequency, 3) word co-occurrence, and 4) word distance and
proposes a model to identify subjects for textual documents. The preliminary
experiments show that the performance of the proposed model is close to that of
human beings.


title:
MyLibrary: A Model for Implementing a User-centered, Customizable
  Interface to a Library's Collection of Information Resources

abstract:
  The paper describes an extensible model for implementing a user-centered,
customizable interface to a library's collection of information resources. This
model, called MyLibrary, integrates the principles of librarianship
(collection, organization, dissemination, and evaluation) with globally
networked computing resources creating a dynamic, customer-driven front-end to
any library's set of materials. The model supports a framework for libraries to
provide enhanced access to local and remote sets of data, information, and
knowledge. At the same, the model does not overwhelm its users with too much
information because the users control exactly how much information is displayed
to them at any given time. The model is active and not passive; direct human
interaction, computer mediated guidance and communication technologies, as well
as current awareness services all play indispensable roles in this system.


title:
The Alex Catalogue, A Collection of Digital Texts with Automatic Methods
  for Acquisition and Cataloging, User-Defined Typography, Cross-searching of
  Indexed Content, and a Sense of Community

abstract:
  This paper describes the Alex Catalogue of Electronic Texts, the only
Internet-accessible collection of digital documents allowing the user to 1)
dynamically create customized, typographically readable documents on demand, 2)
search the content of one or more documents from the collection simultaneously,
3) create sets of documents from the collection for review and annotation, and
4) publish these sets of annotated documents in turn fostering a sense of
community around the Catalogue. More than a just a collection of links that
will break over time, Alex is an archive of electronic texts providing
unprecedented access to its content and features allowing it to meet the needs
of a wide variety of users and settings. Furthermore, the process of
maintaining the Catalogue is streamlined with tools for automatic acquisition
and cataloging making it possible to sustain the service with a minimum of
personnel.


title: Mutual Search

abstract:
  We introduce a search problem called ``mutual search'' where $k$ \agents,
arbitrarily distributed over $n$ sites, are required to locate one another by
posing queries of the form ``Anybody at site $i$?''. We ask for the least
number of queries that is necessary and sufficient. For the case of two \agents
using deterministic protocols we obtain the following worst-case results: In an
oblivious setting (where all pre-planned queries are executed) there is no
savings: $n-1$ queries are required and are sufficient. In a nonoblivious
setting we can exploit the paradigm of ``no news is also news'' to obtain
significant savings: in the synchronous case $0.586n$ queries suffice and
$0.536n$ queries are required; in the asynchronous case $0.896n$ queries
suffice and a fortiori 0.536 queries are required; for $o(\sqrt{n})$ \agents
using a deterministic protocol less than $n$ queries suffice; there is a simple
randomized protocol for two \agents with worst-case expected $0.5n$ queries and
all randomized protocols require at least $0.125n$ worst-case expected queries.
The graph-theoretic framework we formulate for expressing and analyzing
algorithms for this problem may be of independent interest.


title: A Discipline of Evolutionary Programming

abstract:
  Genetic fitness optimization using small populations or small population
updates across generations generally suffers from randomly diverging
evolutions. We propose a notion of highly probable fitness optimization through
feasible evolutionary computing runs on small size populations. Based on
rapidly mixing Markov chains, the approach pertains to most types of
evolutionary genetic algorithms, genetic programming and the like. We establish
that for systems having associated rapidly mixing Markov chains and appropriate
stationary distributions the new method finds optimal programs (individuals)
with probability almost 1. To make the method useful would require a structured
design methodology where the development of the program and the guarantee of
the rapidly mixing property go hand in hand. We analyze a simple example to
show that the method is implementable. More significant examples require
theoretical advances, for example with respect to the Metropolis filter.


title: KEA: Practical Automatic Keyphrase Extraction

abstract:
  Keyphrases provide semantic metadata that summarize and characterize
documents. This paper describes Kea, an algorithm for automatically extracting
keyphrases from text. Kea identifies candidate keyphrases using lexical
methods, calculates feature values for each candidate, and uses a
machine-learning algorithm to predict which candidates are good keyphrases. The
machine learning scheme first builds a prediction model using training
documents with known keyphrases, and then uses the model to find keyphrases in
new documents. We use a large test corpus to evaluate Kea's effectiveness in
terms of how many author-assigned keyphrases are correctly identified. The
system is simple, robust, and publicly available.


title: Managing Object-Oriented Integration and Regression Testing

abstract:
  Systematic testing of object-oriented software turned out to be much more
complex than testing conventional software. Especially the highly incremental
and iterative development cycle demands both many more changes and partially
implemented resp. re-implemented classes. Much more integration and regression
testing has to be done to reach stable stages during the development. In this
presentation we propose a diagram capturing all possible dependencies and
interactions in an object-oriented program. Then we give algorithms and
coverage criteria to identify integration resp. regression test strategys and
all test cases to be executed after some implementation resp. modification
activities. Finally, we summarize some practical experiences and heuristics.


title: Quality of OCR for Degraded Text Images

abstract:
  Commercial OCR packages work best with high-quality scanned images. They
often produce poor results when the image is degraded, either because the
original itself was poor quality, or because of excessive photocopying. The
ability to predict the word failure rate of OCR from a statistical analysis of
the image can help in making decisions in the trade-off between the success
rate of OCR and the cost of human correction of errors. This paper describes an
investigation of OCR of degraded text images using a standard OCR engine (Adobe
Capture). The documents were selected from those in the archive at Los Alamos
National Laboratory. By introducing noise in a controlled manner into perfect
documents, we show how the quality of OCR can be predicted from the nature of
the noise. The preliminary results show that a simple noise model can give good
prediction of the number of OCR errors.


title:
Multiparty computation unconditionally secure against Q^2 adversary
  structures

abstract:
  We present here a generalization of the work done by Rabin and Ben-Or. We
give a protocol for multiparty computation which tolerates any Q^2 active
adversary structure based on the existence of a broadcast channel, secure
communication between each pair of participants, and a monotone span program
with multiplication tolerating the structure. The secrecy achieved is
unconditional although we allow an exponentially small probability of error.
This is possible due to a protocol for computing the product of two values
already shared by means of a homomorphic commitment scheme which appeared
originally in a paper of Chaum, Evertse and van de Graaf.


title: Content-Based Book Recommending Using Learning for Text Categorization

abstract:
  Recommender systems improve access to relevant products and information by
making personalized suggestions based on previous examples of a user's likes
and dislikes. Most existing recommender systems use social filtering methods
that base recommendations on other users' preferences. By contrast,
content-based methods use information about an item itself to make suggestions.
This approach has the advantage of being able to recommended previously unrated
items to users with unique interests and to provide explanations for its
recommendations. We describe a content-based book recommending system that
utilizes information extraction and a machine-learning algorithm for text
categorization. Initial experimental results demonstrate that this approach can
produce accurate recommendations.


title: Digital Library Technology for Locating and Accessing Scientific Data

abstract:
  In this paper we describe our efforts to bring scientific data into the
digital library. This has required extension of the standard WWW, and also the
extension of metadata standards far beyond the Dublin Core. Our system
demonstrates this technology for real scientific data from astronomy.


title: Use and usability in a digital library search system

abstract:
  Digital libraries must reach out to users from all walks of life, serving
information needs at all levels. To do this, they must attain high standards of
usability over an extremely broad audience. This paper details the evolution of
one important digital library component as it has grown in functionality and
usefulness over several years of use by a live, unrestricted community. Central
to its evolution have been user studies, analysis of use patterns, and
formative usability evaluation. We extrapolate that all three components are
necessary in the production of successful digital library systems.


title:
Proceedings from Critical Infrastructure: The Path Ahead (XIWT Symposium
  on Cross-Industry Activities for Information Infrastructure Robustness)

abstract:
  The Cross-Industry Working Team (XIWT), with the support of the Stanford
University Consortium for Research on Information Security and Policy (CRISP),
sponsored a symposium on cross-industry activities aimed at improving the
reliability, dependability, and robustness of the information infrastructure.
Held 3-4 November 1998 in Crystal City, Virginia, the symposium engaged
representatives from industry, academia, and government in discussion of
current and potential cross-industry, cross-sector activities including
information exchange, collaborative operations, and cooperative research and
development. This proceedings summarizes the discussions and results of the
meeting.


title: Resource Discovery in Trilogy

abstract:
  Trilogy is a collaborative project whose key aim is the development of an
integrated virtual laboratory to support research training within each
institution and collaborative projects between the partners. In this paper, the
architecture and underpinning platform of the system is described with
particular emphasis being placed on the structure and the integration of the
distributed database. A key element is the ontology that provides the
multi-agent system with a conceptualisation specification of the domain; this
ontology is explained, accompanied by a discussion how such a system is
integrated and used within the virtual laboratory. Although in this paper,
Telecommunications and in particular Broadband networks are used as exemplars,
the underlying system principles are applicable to any domain where a
combination of experimental and literature-based resources are required.


title:
Multimedia Description Framework (MDF) for Content Description of
  Audio/Video Documents

abstract:
  MPEG is undertaking a new initiative to standardize content description of
audio and video data/documents. When it is finalized in 2001, MPEG-7 is
expected to provide standardized description schemes for concise and
unambiguous content description of data/documents of complex media types.
Meanwhile, other meta-data or description schemes, such as Dublin Core, XML,
etc., are becoming popular in different application domains. In this paper, we
propose the Multimedia Description Framework (MDF), which is designated to
accommodate multiple description (meta-data) schemes, both MPEG-7 and
non-MPEG-7, into integrated architecture. We will use examples to show how MDF
description makes use of combined strength of different description schemes to
enhance its expression power and flexibility. We conclude the paper with
discussion of using MDF description of a movie video to search/retrieve
required scene clips from the movie, on the MDF prototype system we have
implemented.


title: Not Available

abstract: withdrawn by author


title: ZBroker: A Query Routing Broker for Z39.50 Databases

abstract:
  A query routing broker is a software agent that determines from a large set
of accessing information sources the ones most relevant to a user's information
need. As the number of information sources on the Internet increases
dramatically, future users will have to rely on query routing brokers to decide
a small number of information sources to query without incurring too much query
processing overheads. In this paper, we describe a query routing broker known
as ZBroker developed for bibliographic database servers that support the Z39.50
protocol. ZBroker samples the content of each bibliographic database by using
training queries and their results, and summarizes the bibliographic database
content into a knowledge base. We present the design and implementation of
ZBroker and describe its Web-based user interface.


title: Multimodal Surrogates for Video Browsing

abstract:
  Three types of video surrogates - visual (keyframes), verbal
(keywords/phrases), and combination of the two - were designed and studied in a
qualitative investigation of user cognitive processes. The results favor the
combined surrogates in which verbal information and images reinforce each
other, lead to better comprehension, and may actually require less processing
time. The results also highlight image features users found most helpful. These
findings will inform the interface design and video representation for video
retrieval and browsing.


title:
Using Query Mediators for Distributed Searching in Federated Digital
  Libraries

abstract:
  We describe an architecture and investigate the characteristics of
distributed searching in federated digital libraries. We introduce the notion
of a query mediator as a digital library service responsible for selecting
among available search engines, routing queries to those search engines, and
aggregating results. We examine operational data from the NCSTRL distributed
digital library that reveals a number of characteristics of distributed
resource discovery. These include availability and response time of indexers
and the distinction between the query mediator view of these characteristics
and the indexer view.


title: Visualization of Retrieved Documents using a Presentation Server

abstract:
  In any search-based digital library (DL) systems dealing with a non-trivial
number of documents, users are often required to go through a long list of
short document descriptions in order to identify what they are looking for. To
tackle the problem, a variety of document organization algorithms and/or
visualization techniques have been used to guide users in selecting relevant
documents. Since these techniques require heavy computations, however, we
developed a presentation server designed to serve as an intermediary between
retrieval servers and clients equipped with a visualization interface. In
addition, we designed our own visual interface by which users can view a set of
documents from different perspectives through layers of document maps. We
finally ran experiments to show that the visual interface, in conjunction with
the presentation server, indeed helps users in selecting relevant documents
from the retrieval results.


title: Semi-Automatic Indexing of Multilingual Documents

abstract:
  With the growing significance of digital libraries and the Internet, more and
more electronic texts become accessible to a wide and geographically disperse
public. This requires adequate tools to facilitate indexing, storage, and
retrieval of documents written in different languages. We present a method for
semi-automatic indexing of electronic documents and construction of a
multilingual thesaurus, which can be used for query formulation and information
retrieval. We use special dictionaries and user interaction in order to solve
ambiguities and find adequate canonical terms in the language and adequate
abstract language-independent terms. The abstract thesaurus is updated
incrementally by new indexed documents and is used to search document
concerning terms in a query to the document base.


title: A New Ranking Principle for Multimedia Information Retrieval

abstract:
  A theoretic framework for multimedia information retrieval is introduced
which guarantees optimal retrieval effectiveness. In particular, a Ranking
Principle for Distributed Multimedia-Documents (RPDM) is described together
with an algorithm that satisfies this principle. Finally, the RPDM is shown to
be a generalization of the Probability Ranking principle (PRP) which guarantees
optimal retrieval effectiveness in the case of text document retrieval. The PRP
justifies theoretically the relevance ranking adopted by modern search engines.
In contrast to the classical PRP, the new RPDM takes into account transmission
and inspection time, and most importantly, aspectual recall rather than simple
recall.


title:
Algorithms of Two-Level Parallelization for DSMC of Unsteady Flows in
  Molecular Gasdynamics

abstract:
  The general scheme of two-level parallelization (TLP) for direct simulation
Monte Carlo of unsteady gas flows on shared memory multiprocessor computers has
been described. The high efficient algorithm of parallel independent runs is
used on the first level. The data parallelization is employed for the second
one. Two versions of TLP algorithm are elaborated with static and dynamic load
balancing. The method of dynamic processor reallocation is used for dynamic
load balancing. Two gasdynamic unsteady problems were used to study speedup and
efficiency of the algorithms. The conditions of efficient application field for
the algorithms have been determined.


title: An Efficient Mean Field Approach to the Set Covering Problem

abstract:
  A mean field feedback artificial neural network algorithm is developed and
explored for the set covering problem. A convenient encoding of the inequality
constraints is achieved by means of a multilinear penalty function. An
approximate energy minimum is obtained by iterating a set of mean field
equations, in combination with annealing. The approach is numerically tested
against a set of publicly available test problems with sizes ranging up to
5x10^3 rows and 10^6 columns. When comparing the performance with exact results
for sizes where these are available, the approach yields results within a few
percent from the optimal solutions. Comparisons with other approximate methods
also come out well, in particular given the very low CPU consumption required
-- typically a few seconds. Arbitrary problems can be processed using the
algorithm via a public domain server.


title: Probabilistic Inductive Inference:a Survey

abstract:
  Inductive inference is a recursion-theoretic theory of learning, first
developed by E. M. Gold (1967). This paper surveys developments in
probabilistic inductive inference. We mainly focus on finite inference of
recursive functions, since this simple paradigm has produced the most
interesting (and most complex) results.


title: Autocatalytic Theory of Meaning

abstract:
  Recently it has been argued that autocatalytic theory could be applied to the
origin of culture. Here possible application to a theory of meaning in the
philosophy of language, called radical interpretation, is commented upon and
compared to previous applications.


title: A Scrollbar-based Visualization for Document Navigation

abstract:
  We are interested in questions of improving user control in best-match
text-retrieval systems, specifically questions as to whether simple
visualizations that nonetheless go beyond the minimal ones generally available
can significantly help users. Recently, we have been investigating ways to help
users decide-given a set of documents retrieved by a query-which documents and
passages are worth closer examination. We built a document viewer incorporating
a visualization centered around a novel content-displaying scrollbar and color
term highlighting, and studied whether the visualization is helpful to
non-expert searchers. Participants' reaction to the visualization was very
positive, while the objective results were inconclusive.


title: The "Fodor"-FODOR fallacy bites back

abstract:
  The paper argues that Fodor and Lepore are misguided in their attack on
Pustejovsky's Generative Lexicon, largely because their argument rests on a
traditional, but implausible and discredited, view of the lexicon on which it
is effectively empty of content, a view that stands in the long line of
explaining word meaning (a) by ostension and then (b) explaining it by means of
a vacuous symbol in a lexicon, often the word itself after typographic
transmogrification. (a) and (b) both share the wrong belief that to a word must
correspond a simple entity that is its meaning. I then turn to the semantic
rules that Pustejovsky uses and argue first that, although they have novel
features, they are in a well-established Artificial Intelligence tradition of
explaining meaning by reference to structures that mention other structures
assigned to words that may occur in close proximity to the first. It is argued
that Fodor and Lepore's view that there cannot be such rules is without
foundation, and indeed systems using such rules have proved their practical
worth in computational systems. Their justification descends from line of
argument, whose high points were probably Wittgenstein and Quine that meaning
is not to be understood by simple links to the world, ostensive or otherwise,
but by the relationship of whole cultural representational structures to each
other and to the world as a whole.


title: Is Word Sense Disambiguation just one more NLP task?

abstract:
  This paper compares the tasks of part-of-speech (POS) tagging and
word-sense-tagging or disambiguation (WSD), and argues that the tasks are not
related by fineness of grain or anything like that, but are quite different
kinds of task, particularly becuase there is nothing in POS corresponding to
sense novelty. The paper also argues for the reintegration of sub-tasks that
are being separated for evaluation


title: Introduction to the RSA algorithm and modular arithmetic

abstract:
  These notes are a brief introduction to the RSA algorithm and modular
arithmetic. They are intended for an undergraduate audience.


title:
An Algebraic Programming Style for Numerical Software and its
  Optimization

abstract:
  The abstract mathematical theory of partial differential equations (PDEs) is
formulated in terms of manifolds, scalar fields, tensors, and the like, but
these algebraic structures are hardly recognizable in actual PDE solvers. The
general aim of the Sophus programming style is to bridge the gap between theory
and practice in the domain of PDE solvers. Its main ingredients are a library
of abstract datatypes corresponding to the algebraic structures used in the
mathematical theory and an algebraic expression style similar to the expression
style used in the mathematical theory. Because of its emphasis on abstract
datatypes, Sophus is most naturally combined with object-oriented languages or
other languages supporting abstract datatypes. The resulting source code
patterns are beyond the scope of current compiler optimizations, but are
sufficiently specific for a dedicated source-to-source optimizer. The limited,
domain-specific, character of Sophus is the key to success here. This kind of
optimization has been tested on computationally intensive Sophus style code
with promising results. The general approach may be useful for other styles and
in other application domains as well.


title: A Formal Framework for Linguistic Annotation

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


title: A Flit Level Simulator for Wormhole Routing

abstract:
  Wormhole routing, the latest switching technique to be utilized by massively
parallel computers, enjoys the distinct advantage of a low latency when
compared to other switching techniques. This low latency is due to the nearly
distance insensitive routing traits in the absence of channel contention. The
low latency of wormhole routing brings about a liability of this switching
technique, a chance of deadlock. Deadlock is a concern in wormhole routed
networks due to the fact a message does not release its allocated resources
until all flits of a message have completely traversed the router in which
these resources are associated. The deadlock condition is addressed in the
routing algorithm. Simulation tools are currently needed that will aid in the
size and number of resources necessary to obtain the optimum utilization of
network resources for an algorithm. Some of these resources include the
topology of the network along with the number of nodes for the topology, the
size of the message, and the number and size of buffers at each router.


title: Numeration systems on a regular language

abstract:
  Generalizations of linear numeration systems in which the set of natural
numbers is recognizable by finite automata are obtained by describing an
arbitrary infinite regular language following the lexicographic ordering. For
these systems of numeration, we show that ultimately periodic sets are
recognizable. We also study the translation and the multiplication by constants
as well as the order dependence of the recognizability.


title: Designing SAT for HCP

abstract:
  For arbitrary undirected graph $G$, we are designing SATISFIABILITY problem
(SAT) for HCP, using tools of Boolean algebra only. The obtained SAT be the
logic formulation of conditions for Hamiltonian cycle existence, and use $m$
Boolean variables, where $m$ is the number of graph edges. This Boolean
expression is true if and only if an initial graph is Hamiltonian. That is,
each satisfying assignment of the Boolean variables determines a Hamiltonian
cycle of $G$, and each Hamiltonian cycle of $G$ corresponds to a satisfying
assignment of the Boolean variables. In common case, the obtained Boolean
expression may has an exponential length (the number of Boolean literals).


title: Some Remarks on the Geometry of Grammar

abstract:
  This paper, following (Dymetman:1998), presents an approach to grammar
description and processing based on the geometry of cancellation diagrams, a
concept which plays a central role in combinatorial group theory
(Lyndon-Schuppe:1977). The focus here is on the geometric intuitions and on
relating group-theoretical diagrams to the traditional charts associated with
context-free grammars and type-0 rewriting systems. The paper is structured as
follows. We begin in Section 1 by analyzing charts in terms of constructs
called cells, which are a geometrical counterpart to rules. Then we move in
Section 2 to a presentation of cancellation diagrams and show how they can be
used computationally. In Section 3 we give a formal algebraic presentation of
the concept of group computation structure, which is based on the standard
notions of free group and conjugacy. We then relate in Section 4 the geometric
and the algebraic views of computation by using the fundamental theorem of
combinatorial group theory (Rotman:1994). In Section 5 we study in more detail
the relationship between the two views on the basis of a simple grammar stated
as a group computation structure. In section 6 we extend this grammar to handle
non-local constructs such as relative pronouns and quantifiers. We conclude in
Section 7 with some brief notes on the differences between normal submonoids
and normal subgroups, group computation versus rewriting systems, and the use
of group morphisms to study the computational complexity of parsing and
generation.


title: Empirically Evaluating an Adaptable Spoken Dialogue System

abstract:
  Recent technological advances have made it possible to build real-time,
interactive spoken dialogue systems for a wide variety of applications.
However, when users do not respect the limitations of such systems, performance
typically degrades. Although users differ with respect to their knowledge of
system limitations, and although different dialogue strategies make system
limitations more apparent to users, most current systems do not try to improve
performance by adapting dialogue behavior to individual users. This paper
presents an empirical evaluation of TOOT, an adaptable spoken dialogue system
for retrieving train schedules on the web. We conduct an experiment in which 20
users carry out 4 tasks with both adaptable and non-adaptable versions of TOOT,
resulting in a corpus of 80 dialogues. The values for a wide range of
evaluation measures are then extracted from this corpus. Our results show that
adaptable TOOT generally outperforms non-adaptable TOOT, and that the utility
of adaptation depends on TOOT's initial dialogue strategies.


title:
Space-Efficient Routing Tables for Almost All Networks and the
  Incompressibility Method

abstract:
  We use the incompressibility method based on Kolmogorov complexity to
determine the total number of bits of routing information for almost all
network topologies. In most models for routing, for almost all labeled graphs
$\Theta (n^2)$ bits are necessary and sufficient for shortest path routing. By
`almost all graphs' we mean the Kolmogorov random graphs which constitute a
fraction of $1-1/n^c$ of all graphs on $n$ nodes, where $c > 0$ is an arbitrary
fixed constant. There is a model for which the average case lower bound rises
to $\Omega(n^2 \log n)$ and another model where the average case upper bound
drops to $O(n \log^2 n)$. This clearly exposes the sensitivity of such bounds
to the model under consideration. If paths have to be short, but need not be
shortest (if the stretch factor may be larger than 1), then much less space is
needed on average, even in the more demanding models. Full-information routing
requires $\Theta (n^3)$ bits on average. For worst-case static networks we
prove a $\Omega(n^2 \log n)$ lower bound for shortest path routing and all
stretch factors $<2$ in some networks where free relabeling is not allowed.


title:
A class of problems of NP to be worth to search an efficient solving
  algorithm

abstract:
  We examine possibility to design an efficient solving algorithm for problems
of the class \np. It is introduced a classification of \np problems by the
property that a partial solution of size $k$ can be extended into a partial
solution of size $k+1$ in polynomial time. It is defined an unique class
problems to be worth to search an efficient solving algorithm. The problems,
which are outside of this class, are inherently exponential. We show that the
Hamiltonian cycle problem is inherently exponential.


title: A complete anytime algorithm for balanced number partitioning

abstract:
  Given a set of numbers, the balanced partioning problem is to divide them
into two subsets, so that the sum of the numbers in each subset are as nearly
equal as possible, subject to the constraint that the cardinalities of the
subsets be within one of each other. We combine the balanced largest
differencing method (BLDM) and Korf's complete Karmarkar-Karp algorithm to get
a new algorithm that optimally solves the balanced partitioning problem. For
numbers with twelve significant digits or less, the algorithm can optimally
solve balanced partioning problems of arbitrary size in practice. For numbers
with greater precision, it first returns the BLDM solution, then continues to
find better solutions as time allows.


title:
Formalization of the class of problems solvable by a nondeterministic
  Turing machine

abstract:
  The objective of this article is to formalize the definition of NP problems.
  We construct a mathematical model of discrete problems as independence
systems with weighted elements. We introduce two auxiliary sets that
characterize the solution of the problem: the adjoint set, which contains the
elements from the original set none of which can be adjoined to the already
chosen solution elements; and the residual set, in which every element can be
adjoined to previously chosen solution elements.
  In a problem without lookahead, every adjoint set can be generated by the
solution algorithm effectively, in polynomial time.
  The main result of the study is the assertion that the NP class is identical
with the class of problems without lookahead. Hence it follows that if we fail
to find an effective (polynomial-time) solution algorithm for a given problem,
then we need to look for an alternative formulation of the problem in set of
problems without lookahead.


title: The Impact of Net Culture on Mainstream Societies: a Global Analysis

abstract:
  In this work the impact of the Internet culture on standard mainstream
societies has been analyzed. After analytically establishing the fact that the
Net can be viewed as a pan-societal superstructure which supports its own
distinct culture, an ethnographic analysis is provided to find out the key
aspects of this culture. The elements of this culture which have an empowering
impacts on the standard mainstream societies, as well as the elements in it
which can cause discouraging social effects are then discussed by a global
investigation of the present status of various fundamental aspects (e,g,
education, economics, politics, entertainment etc) of the mainstream societies
as well as their links with the Net culture. Though immensely potential for
providing various prominent positive impacts, the key findings of this work
indicate that misuse of Internet can create tremendous harm to the members of
the mainstream societies by generating a set of morally crippled people as well
as a future generation completely void of principles and ethics. This
structured diagnostic approach to the social problems caused by the manhandling
of Internet leads to a concrete effort of providing the measures that can be
taken to enhance or to overcome the supporting and limiting effects of the Net
culture respectively with the intent to benefit our society and to protect the
teratoidation of certain ethical values.


title:
Perpetual Adaptation of Software to Hardware: An Extensible Architecture
  for Providing Code Optimization as a Central System Service

abstract:
  We present an open architecture for just-in-time code generation and dynamic
code optimization that is flexible, customizable, and extensible. While
previous research has primarily investigated functional aspects of such a
system, architectural aspects have so far remained unexplored. In this paper,
we argue that these properties are important to generate optimal code for a
variety of hardware architectures and different processor generations within
processor families. These properties are also important to make system-level
code generation useful in practice.


title: Scholarly Communication and the Continuum of Electronic Publishing

abstract:
  Electronic publishing opportunities, manifested today in a variety of
electronic journals and Web-based compendia, have captured the imagination of
many scholars. These opportunities have also destabilized norms about the
character of legitimate scholarly publishing in some fields. Unfortunately,
much of the literature about scholarly e-publishing homogenizes the character
of publishing. This article provides an analytical approach for evaluating
disciplinary conventions and for proposing policies about scholarly
e-publishing. We characterize three dimensions of scholarly publishing as a
communicative practice -- publicity, access, and trustworthiness, and examine
several forms of paper and electronic publications in this framework. This
analysis shows how the common claim that e-publishing "substantially expands
access" is over-simplified. It also indicates how peer-reviewing (whether in
paper or electronically) provides valuable functions for scholarly
communication that are not effectively replaced by self-posting articles in
electronic media.


title: Modeling Belief in Dynamic Systems, Part II: Revision and Update

abstract:
  The study of belief change has been an active area in philosophy and AI. In
recent years two special cases of belief change, belief revision and belief
update, have been studied in detail. In a companion paper (Friedman & Halpern,
1997), we introduce a new framework to model belief change. This framework
combines temporal and epistemic modalities with a notion of plausibility,
allowing us to examine the change of beliefs over time. In this paper, we show
how belief revision and belief update can be captured in our framework. This
allows us to compare the assumptions made by each method, and to better
understand the principles underlying them. In particular, it shows that Katsuno
and Mendelzon's notion of belief update (Katsuno & Mendelzon, 1991a) depends on
several strong assumptions that may limit its applicability in artificial
intelligence. Finally, our analysis allow us to identify a notion of minimal
change that underlies a broad range of belief change operations including
revision and update.


title: SIMMUNE, a tool for simulating and analyzing immune system behavior

abstract:
  We present a new approach to the simulation and analysis of immune system
behavior. The simulations that can be done with our software package called
SIMMUNE are based on immunological data that describe the behavior of immune
system agents (cells, molecules) on a microscopial (i.e. agent-agent
interaction) scale by defining cellular stimulus-response mechanisms. Since the
behavior of the agents in SIMMUNE can be very flexibly configured, its
application is not limited to immune system simulations. We outline the
principles of SIMMUNE's multiscale analysis of emergent structure within the
simulated immune system that allow the identification of immunological contexts
using minimal a priori assumptions about the higher level organization of the
immune system.


title: LuaJava - A Scripting Tool for Java

abstract:
  Scripting languages are becoming more and more important as a tool for
software development, as they provide great flexibility for rapid prototyping
and for configuring componentware applications. In this paper we present
LuaJava, a scripting tool for Java. LuaJava adopts Lua, a dynamically typed
interpreted language, as its script language. Great emphasis is given to the
transparency of the integration between the two languages, so that objects from
one language can be used inside the other like native objects. The final result
of this integration is a tool that allows the construction of configurable Java
applications, using off-the-shelf components, in a high abstraction level.


title:
Workflow Automation with Lotus Notes for the Governmental Administrative
  Information System

abstract:
  The paper presents an introductory overview of the workflow automation area,
outlining the main types, basic technologies, the essential features of
workflow applications. Two sorts of process models for the definition of
workflows (according to the conversation-based and activity-based
methodologies) are sketched. Later on, the nature of Lotus Notes and its
capabilities (as an environment for workflow management systems development)
are indicated. Concluding, the experience of automating administrative
workflows (developing a Subsystem of Inter-institutional Document Management of
the VADIS project) is briefly outlined.


title: Tiling with bars under tomographic constraints

abstract:
  We wish to tile a rectangle or a torus with only vertical and horizontal bars
of a given length, such that the number of bars in every column and row equals
given numbers. We present results for particular instances and for a more
general problem, while leaving open the initial problem.


title:
A Proposal for the Establishment of Review Boards - a flexible approach
  to the selection of academic knowledge

abstract:
  Paper journals use a small number of trusted academics to select information
on behalf of all their readers. This inflexibility in the selection was
justified due to the expense of publishing. The advent of cheap distribution
via the internet allows a new trade-off between time and expense and the
flexibility of the selection process. This paper explores one such possible
process one where the role of mark-up and archiving is separated from that of
review. The idea is that authors publish their papers on their own web pages or
in a public paper archive, a board of reviewers judge that paper on a number of
different criteria. The detailed results of the reviews are stored in such a
way as to enable readers to use these judgements to find the papers they want
using search engines on the web. Thus instead of journals using generic
selection criteria readers can set their own to suit their needs. The resulting
system might be even cheaper than web-journals to implement.


title: A geometric framework for modelling similarity search

abstract:
  The aim of this paper is to propose a geometric framework for modelling
similarity search in large and multidimensional data spaces of general nature,
which seems to be flexible enough to address such issues as analysis of
complexity, indexability, and the `curse of dimensionality.' Such a framework
is provided by the concept of the so-called similarity workload, which is a
probability metric space $\Omega$ (query domain) with a distinguished finite
subspace $X$ (dataset), together with an assembly of concepts, techniques, and
results from metric geometry. They include such notions as metric transform,
$\e$-entropy, and the phenomenon of concentration of measure on
high-dimensional structures. In particular, we discuss the relevance of the
latter to understanding the curse of dimensionality. As some of those concepts
and techniques are being currently reinvented by the database community, it
seems desirable to try and bridge the gap between database research and the
relevant work already done in geometry and analysis.


title:
The Structure of Weighting Coefficient Matrices of Harmonic Differential
  Quadrature and Its Applications

abstract:
  The structure of weighting coefficient matrices of Harmonic Differential
Quadrature (HDQ) is found to be either centrosymmetric or skew centrosymmetric
depending on the order of the corresponding derivatives. The properties of both
matrices are briefly discussed in this paper. It is noted that the
computational effort of the harmonic quadrature for some problems can be
further reduced up to 75 per cent by using the properties of the
above-mentioned matrices.


title: Mixing Metaphors

abstract:
  Mixed metaphors have been neglected in recent metaphor research. This paper
suggests that such neglect is short-sighted. Though mixing is a more complex
phenomenon than straight metaphors, the same kinds of reasoning and knowledge
structures are required. This paper provides an analysis of both parallel and
serial mixed metaphors within the framework of an AI system which is already
capable of reasoning about straight metaphorical manifestations and argues that
the processes underlying mixing are central to metaphorical meaning. Therefore,
any theory of metaphors must be able to account for mixing.


title: Transport Level Security: a proof using the Gong-Needham-Yahalom Logic

abstract:
  This paper provides a proof of the proposed Internet standard Transport Level
Security protocol using the Gong-Needham-Yahalom logic. It is intended as a
teaching aid and hopes to show to students: the potency of a formal method for
protocol design; some of the subtleties of authenticating parties on a network
where all messages can be intercepted; the design of what should be a widely
accepted standard.


title:
Jacobian matrix: a bridge between linear and nonlinear polynomial-only
  problems

abstract:
  By using the Hadamard matrix product concept, this paper introduces two
generalized matrix formulation forms of numerical analogue of nonlinear
differential operators. The SJT matrix-vector product approach is found to be a
simple, efficient and accurate technique in the calculation of the Jacobian
matrix of the nonlinear discretization by finite difference, finite volume,
collocation, dual reciprocity BEM or radial functions based numerical methods.
We also present and prove simple underlying relationship (theorem (3.1))
between general nonlinear analogue polynomials and their corresponding Jacobian
matrices, which forms the basis of this paper. By means of theorem 3.1,
stability analysis of numerical solutions of nonlinear initial value problems
can be easily handled based on the well-known results for linear problems.
Theorem 3.1 also leads naturally to the straightforward extension of various
linear iterative algorithms such as the SOR, Gauss-Seidel and Jacobi methods to
nonlinear algebraic equations. Since an exact alternative of the quasi-Newton
equation is established via theorem 3.1, we derive a modified BFGS quasi-Newton
method. A simple formula is also given to examine the deviation between the
approximate and exact Jacobian matrices. Furthermore, in order to avoid the
evaluation of the Jacobian matrix and its inverse, the pseudo-Jacobian matrix
is introduced with a general applicability of any nonlinear systems of
equations. It should be pointed out that a large class of real-world nonlinear
problems can be modeled or numerically discretized polynomial-only algebraic
system of equations. The results presented here are in general applicable for
all these problems. This paper can be considered as a starting point in the
research of nonlinear computation and analysis from an innovative viewpoint.


title: The Study on the Nonlinear Computations of the DQ and DC Methods

abstract:
  This paper points out that the differential quadrature (DQ) and differential
cubature (DC) methods due to their global domain property are more efficient
for nonlinear problems than the traditional numerical techniques such as finite
element and finite difference methods. By introducing the Hadamard product of
matrices, we obtain an explicit matrix formulation for the DQ and DC solutions
of nonlinear differential and integro-differential equations. Due to its
simplicity and flexibility, the present Hadamard product approach makes the DQ
and DC methods much easier to be used. Many studies on the Hadamard product can
be fully exploited for the DQ and DC nonlinear computations. Furthermore, we
first present SJT product of matrix and vector to compute accurately and
efficiently the Frechet derivative matrix in the Newton-Raphson method for the
solution of the nonlinear formulations. We also propose a simple approach to
simplify the DQ or DC formulations for some nonlinear differential operators
and thus the computational efficiency of these methods is improved
significantly. We give the matrix multiplication formulas to compute
efficiently the weighting coefficient matrices of the DC method. The spherical
harmonics are suggested as the test functions in the DC method to handle the
nonlinear differential equations occurring in global and hemispheric weather
forecasting problems. Some examples are analyzed to demonstrate the simplicity
and efficiency of the presented techniques. It is emphasized that innovations
presented are applicable to the nonlinear computations of the other numerical
methods as well.


title: Transducers from Rewrite Rules with Backreferences

abstract:
  Context sensitive rewrite rules have been widely used in several areas of
natural language processing, including syntax, morphology, phonology and speech
processing. Kaplan and Kay, Karttunen, and Mohri & Sproat have given various
algorithms to compile such rewrite rules into finite-state transducers. The
present paper extends this work by allowing a limited form of backreferencing
in such rules. The explicit use of backreferencing leads to more elegant and
general solutions.


title: An ascription-based approach to speech acts

abstract:
  The two principal areas of natural language processing research in pragmatics
are belief modelling and speech act processing. Belief modelling is the
development of techniques to represent the mental attitudes of a dialogue
participant. The latter approach, speech act processing, based on speech act
theory, involves viewing dialogue in planning terms. Utterances in a dialogue
are modelled as steps in a plan where understanding an utterance involves
deriving the complete plan a speaker is attempting to achieve. However,
previous speech act based approaches have been limited by a reliance upon
relatively simplistic belief modelling techniques and their relationship to
planning and plan recognition. In particular, such techniques assume
precomputed nested belief structures. In this paper, we will present an
approach to speech act processing based on novel belief modelling techniques
where nested beliefs are propagated on demand.


title: Beyond Concern: Understanding Net Users' Attitudes About Online Privacy

abstract:
  People are concerned about privacy, particularly on the Internet. While many
studies have provided evidence of this concern, few have explored the nature of
the concern in detail, especially for the online environment. With this study,
we have tried to better understand the nature of online privacy concerns; we
look beyond the fact that people are concerned and attempt to understand how
they are concerned. We hope our results will help inform both policy decisions
as well as the development of technology tools that can assist Internet users
in protecting their privacy.
  We present results here from the analysis of 381 questionnaires completed
between November 6 and November 13, 1998 by American Internet users. The sample
was drawn from the FamilyPC magazine/Digital Research, Inc. Family Panel. While
this is not a statistically representative sample of US Internet users, our
respondents are heavy Internet users, and quite possibly lead innovators. As
such, we believe that this sample is important for understanding the future
Internet user population.


title: WebScript -- A Scripting Language for the Web

abstract:
  WebScript is a scripting language for processing Web documents. Designed as
an extension to Jacl, the Java implementation of Tcl, WebScript allows
programmers to manipulate HTML in the same way as Tcl manipulates text strings
and GUI elements. This leads to a completely new way of writing the next
generation of Web applications. This paper presents the motivation behind the
design and implementation of WebScript, an overview of its major features, as
well as some demonstrations of its power.


abstract:
  This paper introduces a novel algorithm, the Active Virtual Network
Management Protocol (AVNMP), for predictive network management. It explains how
the AVNMP facilitates the management of an active network by allowing future
predicted state information within an active network to be available to network
management algorithms. This is accomplished by coupling ideas from optimistic
discrete event simulation with active networking. The optimistic discrete event
simulation method used is a form of self-adjusting Time Warp. It is
self-adjusting because the system adjusts for predictions which are inaccurate
beyond a given tolerance. The concept of a streptichron and autoanaplasis are
introduced as mechanisms which take advantage of the enhanced flexibility and
intelligence of active packets. Finally, it is demonstrated that the AVNMP is a
feasible concept.


title: Network Management of Predictive Mobile Networks

abstract:
  There is a trend toward the use of predictive systems in communications
networks. At the systems and network management level predictive capabilities
are focused on anticipating network faults and performance degradation.
Simultaneously, mobile communication networks are being developed with
predictive location and tracking mechanisms. The interactions and synergies
between these systems present a new set of problems. A new predictive network
management framework is developed and examined. The interaction between a
predictive mobile network and the proposed network management system is
discussed. The Rapidly Deployable Radio Network is used as a specific example
to illustrate these interactions.


title: A Control and Management Network for Wireless ATM Systems

abstract:
  This paper describes the design of a control and management network
(orderwire) for a mobile wireless Asynchronous Transfer Mode (ATM) network.
This mobile wireless ATM network is part of the Rapidly Deployable Radio
Network (RDRN). The orderwire system consists of a packet radio network which
overlays the mobile wireless ATM network, each network element in this network
uses Global Positioning System (GPS) information to control a beamforming
antenna subsystem which provides for spatial reuse. This paper also proposes a
novel Virtual Network Configuration (VNC) algorithm for predictive network
configuration. A mobile ATM Private Network-Network Interface (PNNI) based on
VNC is also discussed. Finally, as a prelude to the system implementation,
results of a Maisie simulation of the orderwire system are discussed.


title: Mobile ATM Buffer Capacity Analysis

abstract:
  This paper extends a stochastic theory for buffer fill distribution for
multiple ``on'' and ``off'' sources to a mobile environment. Queue fill
distribution is described by a set of differential equations assuming sources
alternate asynchronously between exponentially distributed periods in ``on''
and ``off'' states. This paper includes the probabilities that mobile sources
have links to a given queue. The sources represent mobile user nodes, and the
queue represents the capacity of a switch. This paper presents a method of
analysis which uses mobile parameters such as speed, call rates per unit area,
cell area, and call duration and determines queue fill distribution at the ATM
cell level. The analytic results are compared with simulation results.


title: Brittle System Analysis

abstract:
  The goal of this paper is to define and analyze systems which exhibit brittle
behavior. This behavior is characterized by a sudden and steep decline in
performance as the system approaches the limits of tolerance. This can be due
to input parameters which exceed a specified input, or environmental conditions
which exceed specified operating boundaries. An analogy is made between brittle
commmunication systems in particular and materials science.


title: A Machine-Independent Debugger--Revisited

abstract:
  Most debuggers are notoriously machine-dependent, but some recent research
prototypes achieve varying degrees of machine-independence with novel designs.
Cdb, a simple source-level debugger for C, is completely independent of its
target architecture. This independence is achieved by embedding symbol tables
and debugging code in the target program, which costs both time and space. This
paper describes a revised design and implementation of cdb that reduces the
space cost by nearly one-half and the time cost by 13% by storing symbol tables
in external files. A symbol table is defined by a 31-line grammar in the
Abstract Syntax Description Language (ASDL). ASDL is a domain-specific language
for specifying tree data structures. The ASDL tools accept an ASDL grammar and
generate code to construct, read, and write these data structures. Using ASDL
automates implementing parts of the debugger, and the grammar documents the
symbol table concisely. Using ASDL also suggested simplifications to the
interface between the debugger and the target program. Perhaps most important,
ASDL emphasizes that symbol tables are data structures, not file formats. Many
of the pitfalls of working with low-level file formats can be avoided by
focusing instead on high-level data structures and automating the
implementation details.


title: A Computational Memory and Processing Model for Processing for Prosody

abstract:
  This paper links prosody to the information in a text and how it is processed
by the speaker. It describes the operation and output of LOQ, a text-to-speech
implementation that includes a model of limited attention and working memory.
Attentional limitations are key. Varying the attentional parameter in the
simulations varies in turn what counts as given and new in a text, and
therefore, the intonational contours with which it is uttered. Currently, the
system produces prosody in three different styles: child-like, adult
expressive, and knowledgeable. This prosody also exhibits differences within
each style -- no two simulations are alike. The limited resource approach
captures some of the stylistic and individual variety found in natural prosody.


title: Bounds for Small-Error and Zero-Error Quantum Algorithms

abstract:
  We present a number of results related to quantum algorithms with small error
probability and quantum algorithms that are zero-error. First, we give a tight
analysis of the trade-offs between the number of queries of quantum search
algorithms, their error probability, the size of the search space, and the
number of solutions in this space. Using this, we deduce new lower and upper
bounds for quantum versions of amplification problems. Next, we establish
nearly optimal quantum-classical separations for the query complexity of
monotone functions in the zero-error model (where our quantum zero-error model
is defined so as to be robust when the quantum gates are noisy). Also, we
present a communication complexity problem related to a total function for
which there is a quantum-classical communication complexity gap in the
zero-error model. Finally, we prove separations for monotone graph properties
in the zero-error and other error models which imply that the evasiveness
conjecture for such properties does not hold for quantum computers.


title:
ODP channel objects that provide services transparently for distributing
  processing systems

abstract:
  This paper describes an architecture for a distributing processing system
that would allow remote procedure calls to invoke other services as messages
are passed between clients and servers. It proposes that an additional class of
data processing objects be located in the software communications channel. The
objects in this channel would then be used to enforce protocols on
client-server applications without any additional effort by the application
programmers. For example, services such as key-management, time-stamping,
sequencing and encryption can be implemented at different levels of the
software communications stack to provide a complete authentication service. A
distributing processing environment could be used to control broadband network
data delivery. Architectures and invocation semantics are discussed, Example
classes and interfaces for channel objects are given in the Java programming
language.


title:
Hadamard product nonlinear formulation of Galerkin and finite element
  methods

abstract:
  A novel nonlinear formulation of the finite element and Galerkin methods is
presented here, which leads to the Hadamard product expression of the resultant
nonlinear algebraic analogue. The presented formulation attains the advantages
of weak formulation in the standard finite element and Galerkin schemes and
avoids the costly repeated numerical integration of the Jacobian matrix via the
recently developed SJT product approach. This also provides possibility of the
nonlinear decoupling computations.


title:
Supervised Grammar Induction Using Training Data with Limited
  Constituent Information

abstract:
  Corpus-based grammar induction generally relies on hand-parsed training data
to learn the structure of the language. Unfortunately, the cost of building
large annotated corpora is prohibitively expensive. This work aims to improve
the induction strategy when there are few labels in the training data. We show
that the most informative linguistic constituents are the higher nodes in the
parse trees, typically denoting complex noun phrases and sentential clauses.
They account for only 20% of all constituents. For inducing grammars from
sparsely labeled training data (e.g., only higher-level constituent labels), we
propose an adaptation strategy, which produces grammars that parse almost as
well as grammars induced from fully labeled corpora. Our results suggest that
for a partial parser to replace human annotators, it must be able to
automatically extract higher-level constituents rather than base noun phrases.


title: DRAFT : Task System and Item Architecture (TSIA)

abstract:
  During its execution, a task is independent of all other tasks. For an
application which executes in terms of tasks, the application definition can be
free of the details of the execution. Many projects have demonstrated that a
task system (TS) can provide such an application with a parallel, distributed,
heterogeneous, adaptive, dynamic, real-time, interactive, reliable, secure or
other execution. A task consists of items and thus the application is defined
in terms of items. An item architecture (IA) can support arrays, routines and
other structures of items, thus allowing for a structured application
definition. Taking properties from many projects, the support can extend
through to currying, application defined types, conditional items, streams and
other definition elements. A task system and item architecture (TSIA) thus
promises unprecedented levels of support for application execution and
definition.


title: Collective Choice Theory in Collaborative Computing

abstract:
  This paper presents some fundamental collective choice theory for information
system designers, particularly those working in the field of computer-supported
cooperative work. This paper is focused on a presentation of Arrow's
Possibility and Impossibility theorems which form the fundamental boundary on
the efficacy of collective choice: voting and selection procedures. It restates
the conditions that Arrow placed on collective choice functions in more
rigorous second-order logic, which could be used as a set of test conditions
for implementations, and a useful probabilistic result for analyzing votes on
issue pairs. It also describes some simple collective choice functions. There
is also some discussion of how enterprises should approach putting their
resources under collective control: giving an outline of a superstructure of
performative agents to carry out this function and what distributing processing
technology would be needed.


title: Using Collective Intelligence to Route Internet Traffic

abstract:
  A COllective INtelligence (COIN) is a set of interacting reinforcement
learning (RL) algorithms designed in an automated fashion so that their
collective behavior optimizes a global utility function. We summarize the
theory of COINs, then present experiments using that theory to design COINs to
control internet traffic routing. These experiments indicate that COINs
outperform all previously investigated RL-based, shortest path routing
algorithms.

categories: cs.LG adap-org cond-mat.stat-mech cs.DC cs.NI nlin.AO


title: General Principles of Learning-Based Multi-Agent Systems

abstract:
  We consider the problem of how to design large decentralized multi-agent
systems (MAS's) in an automated fashion, with little or no hand-tuning. Our
approach has each agent run a reinforcement learning algorithm. This converts
the problem into one of how to automatically set/update the reward functions
for each of the agents so that the global goal is achieved. In particular we do
not want the agents to ``work at cross-purposes'' as far as the global goal is
concerned. We use the term artificial COllective INtelligence (COIN) to refer
to systems that embody solutions to this problem. In this paper we present a
summary of a mathematical framework for COINs. We then investigate the
real-world applicability of the core concepts of that framework via two
computer experiments: we show that our COINs perform near optimally in a
difficult variant of Arthur's bar problem (and in particular avoid the tragedy
of the commons for that problem), and we also illustrate optimal performance
for our COINs in the leader-follower problem.

categories: cs.MA adap-org cond-mat.stat-mech cs.DC cs.LG nlin.AO


title:
The Design and Analysis of Virtual Network Configuration for a Wireless
  Mobile ATM Network

abstract:
  This research concentrates on the design and analysis of an algorithm
referred to as Virtual Network Configuration (VNC) which uses predicted future
states of a system for faster network configuration and management. VNC is
applied to the configuration of a wireless mobile ATM network. VNC is built on
techniques from parallel discrete event simulation merged with constraints from
real-time systems and applied to mobile ATM configuration and handoff.
  Configuration in a mobile network is a dynamic and continuous process.
Factors such as load, distance, capacity and topology are all constantly
changing in a mobile environment. The VNC algorithm anticipates configuration
changes and speeds the reconfiguration process by pre-computing and caching
results. VNC propagates local prediction results throughout the VNC enhanced
system. The Global Positioning System is an enabling technology for the use of
VNC in mobile networks because it provides location information and accurate
time for each node.
  This research has resulted in well defined structures for the encapsulation
of physical processes within Logical Processes and a generic library for
enhancing a system with VNC. Enhancing an existing system with VNC is straight
forward assuming the existing physical processes do not have side effects. The
benefit of prediction is gained at the cost of additional traffic and
processing. This research includes an analysis of VNC and suggestions for
optimization of the VNC algorithm and its parameters.


title:
An Efficient, Probabilistically Sound Algorithm for Segmentation and
  Word Discovery

abstract:
  This paper presents a model-based, unsupervised algorithm for recovering word
boundaries in a natural-language text from which they have been deleted. The
algorithm is derived from a probability model of the source that generated the
text. The fundamental structure of the model is specified abstractly so that
the detailed component models of phonology, word-order, and word frequency can
be replaced in a modular fashion. The model yields a language-independent,
prior probability distribution on all possible sequences of all possible words
over a given alphabet, based on the assumption that the input was generated by
concatenating words from a fixed but unknown lexicon. The model is unusual in
that it treats the generation of a complete corpus, regardless of length, as a
single event in the probability space. Accordingly, the algorithm does not
estimate a probability distribution on words; instead, it attempts to calculate
the prior probabilities of various word sequences that could underlie the
observed text. Experiments on phonemic transcripts of spontaneous speech by
parents to young children suggest that this algorithm is more effective than
other proposed algorithms, at least when utterance boundaries are given and the
text includes a substantial number of short utterances.
  Keywords: Bayesian grammar induction, probability models, minimum description
length (MDL), unsupervised learning, cognitive modeling, language acquisition,
segmentation


title: Inducing a Semantically Annotated Lexicon via EM-Based Clustering

abstract:
  We present a technique for automatic induction of slot annotations for
subcategorization frames, based on induction of hidden classes in the EM
framework of statistical estimation. The models are empirically evalutated by a
general decision test. Induction of slot labeling for subcategorization frames
is accomplished by a further application of EM, and applied experimentally on
frame observations derived from parsing large corpora. We outline an
interpretation of the learned representations as theoretical-linguistic
decompositional lexical entries.


title: Inside-Outside Estimation of a Lexicalized PCFG for German

abstract:
  The paper describes an extensive experiment in inside-outside estimation of a
lexicalized probabilistic context free grammar for German verb-final clauses.
Grammar and formalism features which make the experiment feasible are
described. Successive models are evaluated on precision and recall of phrase
markup.


title:
Statistical Inference and Probabilistic Modelling for Constraint-Based
  NLP

abstract:
  We present a probabilistic model for constraint-based grammars and a method
for estimating the parameters of such models from incomplete, i.e., unparsed
data. Whereas methods exist to estimate the parameters of probabilistic
context-free grammars from incomplete data (Baum 1970), so far for
probabilistic grammars involving context-dependencies only parameter estimation
techniques from complete, i.e., fully parsed data have been presented (Abney
1997). However, complete-data estimation requires labor-intensive, error-prone,
and grammar-specific hand-annotating of large language corpora. We present a
log-linear probability model for constraint logic programming, and a general
algorithm to estimate the parameters of such models from incomplete data by
extending the estimation algorithm of Della-Pietra, Della-Pietra, and Lafferty
(1997) to incomplete data settings.


title:
Ensembles of Radial Basis Function Networks for Spectroscopic Detection
  of Cervical Pre-Cancer

abstract:
  The mortality related to cervical cancer can be substantially reduced through
early detection and treatment. However, current detection techniques, such as
Pap smear and colposcopy, fail to achieve a concurrently high sensitivity and
specificity.
  In vivo fluorescence spectroscopy is a technique which quickly,
non-invasively and quantitatively probes the biochemical and morphological
changes that occur in pre-cancerous tissue.
  A multivariate statistical algorithm was used to extract clinically useful
information from tissue spectra acquired from 361 cervical sites from 95
patients at 337, 380 and 460 nm excitation wavelengths. The multivariate
statistical analysis was also employed to reduce the number of fluorescence
excitation-emission wavelength pairs required to discriminate healthy tissue
samples from pre-cancerous tissue samples. The use of connectionist methods
such as multi layered perceptrons, radial basis function networks, and
ensembles of such networks was investigated. RBF ensemble algorithms based on
fluorescence spectra potentially provide automated, and near real-time
implementation of pre-cancer detection in the hands of non-experts. The results
are more reliable, direct and accurate than those achieved by either human
experts or multivariate statistical algorithms.


title: Linear and Order Statistics Combiners for Pattern Classification

abstract:
  Several researchers have experimentally shown that substantial improvements
can be obtained in difficult pattern recognition problems by combining or
integrating the outputs of multiple classifiers. This chapter provides an
analytical framework to quantify the improvements in classification results due
to combining. The results apply to both linear combiners and order statistics
combiners. We first show that to a first order approximation, the error rate
obtained over and above the Bayes error rate, is directly proportional to the
variance of the actual decision boundaries around the Bayes optimum boundary.
Combining classifiers in output space reduces this variance, and hence reduces
the "added" error. If N unbiased classifiers are combined by simple averaging,
the added error rate can be reduced by a factor of N if the individual errors
in approximating the decision boundaries are uncorrelated. Expressions are then
derived for linear combiners which are biased or correlated, and the effect of
output correlations on ensemble performance is quantified. For order statistics
based non-linear combiners, we derive expressions that indicate how much the
median, the maximum and in general the ith order statistic can improve
classifier performance. The analysis presented here facilitates the
understanding of the relationships among error rates, classifier boundary
distributions, and combining in output space. Experimental results on several
public domain data sets are provided to illustrate the benefits of combining
and to support the analytical results.


title: Robust Combining of Disparate Classifiers through Order Statistics

abstract:
  Integrating the outputs of multiple classifiers via combiners or
meta-learners has led to substantial improvements in several difficult pattern
recognition problems. In the typical setting investigated till now, each
classifier is trained on data taken or resampled from a common data set, or
(almost) randomly selected subsets thereof, and thus experiences similar
quality of training data. However, in certain situations where data is acquired
and analyzed on-line at several geographically distributed locations, the
quality of data may vary substantially, leading to large discrepancies in
performance of individual classifiers. In this article we introduce and
investigate a family of classifiers based on order statistics, for robust
handling of such cases. Based on a mathematical modeling of how the decision
boundaries are affected by order statistic combiners, we derive expressions for
the reductions in error expected when such combiners are used. We show
analytically that the selection of the median, the maximum and in general, the
$i^{th}$ order statistic improves classification performance. Furthermore, we
introduce the trim and spread combiners, both based on linear combinations of
the ordered classifier outputs, and show that they are quite beneficial in
presence of outliers or uneven classifier performance. Experimental results on
several public domain data sets corroborate these findings.


title:
Hierarchical Reinforcement Learning with the MAXQ Value Function
  Decomposition

abstract:
  This paper presents the MAXQ approach to hierarchical reinforcement learning
based on decomposing the target Markov decision process (MDP) into a hierarchy
of smaller MDPs and decomposing the value function of the target MDP into an
additive combination of the value functions of the smaller MDPs. The paper
defines the MAXQ hierarchy, proves formal results on its representational
power, and establishes five conditions for the safe use of state abstractions.
The paper presents an online model-free learning algorithm, MAXQ-Q, and proves
that it converges wih probability 1 to a kind of locally-optimal policy known
as a recursively optimal policy, even in the presence of the five kinds of
state abstraction. The paper evaluates the MAXQ representation and MAXQ-Q
through a series of experiments in three domains and shows experimentally that
MAXQ-Q (with state abstractions) converges to a recursively optimal policy much
faster than flat Q learning. The fact that MAXQ learns a representation of the
value function has an important benefit: it makes it possible to compute and
execute an improved, non-hierarchical policy via a procedure similar to the
policy improvement step of policy iteration. The paper demonstrates the
effectiveness of this non-hierarchical execution experimentally. Finally, the
paper concludes with a comparison to related work and a discussion of the
design tradeoffs in hierarchical reinforcement learning.


title: State Abstraction in MAXQ Hierarchical Reinforcement Learning

abstract:
  Many researchers have explored methods for hierarchical reinforcement
learning (RL) with temporal abstractions, in which abstract actions are defined
that can perform many primitive actions before terminating. However, little is
known about learning with state abstractions, in which aspects of the state
space are ignored. In previous work, we developed the MAXQ method for
hierarchical RL. In this paper, we define five conditions under which state
abstraction can be combined with the MAXQ value function decomposition. We
prove that the MAXQ-Q learning algorithm converges under these conditions and
show experimentally that state abstraction is important for the successful
application of MAXQ-Q learning.


title:
Programs with Stringent Performance Objectives Will Often Exhibit
  Chaotic Behavior

abstract:
  Software for the resolution of certain kind of problems, those that rate high
in the Stringent Performance Objectives adjustment factor (IFPUG scheme), can
be described using a combination of game theory and autonomous systems. From
this description it can be shown that some of those problems exhibit chaotic
behavior, an important fact in understanding the functioning of the related
software. As a relatively simple example, it is shown that chess exhibits
chaotic behavior in its configuration space. This implies that static
evaluators in chess programs have intrinsic limitations.


title: On Bounded-Weight Error-Correcting Codes

abstract:
  This paper computationally obtains optimal bounded-weight, binary,
error-correcting codes for a variety of distance bounds and dimensions. We
compare the sizes of our codes to the sizes of optimal constant-weight, binary,
error-correcting codes, and evaluate the differences.


title: The Symbol Grounding Problem

abstract:
  How can the semantic interpretation of a formal symbol system be made
intrinsic to the system, rather than just parasitic on the meanings in our
heads? How can the meanings of the meaningless symbol tokens, manipulated
solely on the basis of their (arbitrary) shapes, be grounded in anything but
other meaningless symbols? The problem is analogous to trying to learn Chinese
from a Chinese/Chinese dictionary alone. A candidate solution is sketched:
Symbolic representations must be grounded bottom-up in nonsymbolic
representations of two kinds: (1) "iconic representations," which are analogs
of the proximal sensory projections of distal objects and events, and (2)
"categorical representations," which are learned and innate feature-detectors
that pick out the invariant features of object and event categories from their
sensory projections. Elementary symbols are the names of these object and event
categories, assigned on the basis of their (nonsymbolic) categorical
representations. Higher-order (3) "symbolic representations," grounded in these
elementary symbols, consist of symbol strings describing category membership
relations (e.g., "An X is a Y that is Z").


title: The syntactic processing of particles in Japanese spoken language

abstract:
  Particles fullfill several distinct central roles in the Japanese language.
They can mark arguments as well as adjuncts, can be functional or have semantic
funtions. There is, however, no straightforward matching from particles to
functions, as, e.g., GA can mark the subject, the object or an adjunct of a
sentence. Particles can cooccur. Verbal arguments that could be identified by
particles can be eliminated in the Japanese sentence. And finally, in spoken
language particles are often omitted. A proper treatment of particles is thus
necessary to make an analysis of Japanese sentences possible. Our treatment is
based on an empirical investigation of 800 dialogues. We set up a type
hierarchy of particles motivated by their subcategorizational and
modificational behaviour. This type hierarchy is part of the Japanese syntax in
VERBMOBIL.


title: Cascaded Grammatical Relation Assignment

abstract:
  In this paper we discuss cascaded Memory-Based grammatical relations
assignment. In the first stages of the cascade, we find chunks of several types
(NP,VP,ADJP,ADVP,PP) and label them with their adverbial function (e.g. local,
temporal). In the last stage, we assign grammatical relations to pairs of
chunks. We studied the effect of adding several levels to this cascaded
classifier and we found that even the less performing chunkers enhanced the
performance of the relation finder.


title: Memory-Based Shallow Parsing

abstract:
  We present a memory-based learning (MBL) approach to shallow parsing in which
POS tagging, chunking, and identification of syntactic relations are formulated
as memory-based modules. The experiments reported in this paper show
competitive results, the F-value for the Wall Street Journal (WSJ) treebank is:
93.8% for NP chunking, 94.7% for VP chunking, 77.1% for subject detection and
79.0% for object detection.


title: Learning Efficient Disambiguation

abstract:
  This dissertation analyses the computational properties of current
performance-models of natural language parsing, in particular Data Oriented
Parsing (DOP), points out some of their major shortcomings and suggests
suitable solutions. It provides proofs that various problems of probabilistic
disambiguation are NP-Complete under instances of these performance-models, and
it argues that none of these models accounts for attractive efficiency
properties of human language processing in limited domains, e.g. that frequent
inputs are usually processed faster than infrequent ones. The central
hypothesis of this dissertation is that these shortcomings can be eliminated by
specializing the performance-models to the limited domains. The dissertation
addresses "grammar and model specialization" and presents a new framework, the
Ambiguity-Reduction Specialization (ARS) framework, that formulates the
necessary and sufficient conditions for successful specialization. The
framework is instantiated into specialization algorithms and applied to
specializing DOP. Novelties of these learning algorithms are 1) they limit the
hypotheses-space to include only "safe" models, 2) are expressed as constrained
optimization formulae that minimize the entropy of the training tree-bank given
the specialized grammar, under the constraint that the size of the specialized
model does not exceed a predefined maximum, and 3) they enable integrating the
specialized model with the original one in a complementary manner. The
dissertation provides experiments with initial implementations and compares the
resulting Specialized DOP (SDOP) models to the original DOP models with
encouraging results.


title: MSO definable string transductions and two-way finite state transducers

abstract:
  String transductions that are definable in monadic second-order (mso) logic
(without the use of parameters) are exactly those realized by deterministic
two-way finite state transducers. Nondeterministic mso definable string
transductions (i.e., those definable with the use of parameters) correspond to
compositions of two nondeterministic two-way finite state transducers that have
the finite visit property. Both families of mso definable string transductions
are characterized in terms of Hennie machines, i.e., two-way finite state
transducers with the finite visit property that are allowed to rewrite their
input tape.


title: A Lower Bound on the 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 every
$p$. The proof method is an incompressibility argument based on Kolmogorov
complexity. Using similar techniques, the average-case complexity of several
other sorting algorithms is analyzed.


title: Cascaded Markov Models

abstract:
  This paper presents a new approach to partial parsing of context-free
structures. The approach is based on Markov Models. Each layer of the resulting
structure is represented by its own Markov Model, and output of a lower layer
is passed as input to the next higher layer. An empirical evaluation of the
method yields very good results for NP/PP chunking of German newspaper texts.


title: Predicate Logic with Definitions

abstract:
  Predicate Logic with Definitions (PLD or D-logic) is a modification of
first-order logic intended mostly for practical formalization of mathematics.
The main syntactic constructs of D-logic are terms, formulas and definitions. A
definition is a definition of variables, a definition of constants, or a
composite definition (D-logic has also abbreviation definitions called
abbreviations). Definitions can be used inside terms and formulas. This
possibility alleviates introducing new quantifier-like names. Composite
definitions allow constructing new definitions from existing ones.


title: A Newton method without evaluation of nonlinear function values

abstract:
  The present author recently proposed and proved a relationship theorem
between nonlinear polynomial equations and the corresponding Jacobian matrix.
By using this theorem, this paper derives a Newton iterative formula without
requiring the evaluation of nonlinear function values in the solution of
nonlinear polynomial-only problems.


title:
The application of special matrix product to differential quadrature
  solution of geometrically nonlinear bending of orthotropic rectangular plates

abstract:
  The Hadamard and SJT product of matrices are two types of special matrix
product. The latter was first defined by Chen. In this study, they are applied
to the differential quadrature (DQ) solution of geometrically nonlinear bending
of isotropic and orthotropic rectangular plates. By using the Hadamard product,
the nonlinear formulations are greatly simplified, while the SJT product
approach minimizes the effort to evaluate the Jacobian derivative matrix in the
Newton-Raphson method for solving the resultant nonlinear formulations. In
addition, the coupled nonlinear formulations for the present problems can
easily be decoupled by means of the Hadamard and SJT product. Therefore, the
size of the simultaneous nonlinear algebraic equations is reduced by two-thirds
and the computing effort and storage requirements are alleviated greatly. Two
recent approaches applying the multiple boundary conditions are employed in the
present DQ nonlinear computations. The solution accuracies are improved
obviously in comparison to the previously given by Bert et al. The numerical
results and detailed solution procedures are provided to demonstrate the superb
efficiency, accuracy and simplicity of the new approaches in applying DQ method
for nonlinear computations.


title: Combining Inclusion Polymorphism and Parametric Polymorphism

abstract:
  We show that the question whether a term is typable is decidable for type
systems combining inclusion polymorphism with parametric polymorphism provided
the type constructors are at most unary. To prove this result we first reduce
the typability problem to the problem of solving a system of type inequations.
The result is then obtained by showing that the solvability of the resulting
system of type inequations is decidable.


title: Evaluation of the NLP Components of the OVIS2 Spoken Dialogue System

abstract:
  The NWO Priority Programme Language and Speech Technology is a 5-year
research programme aiming at the development of spoken language information
systems. In the Programme, two alternative natural language processing (NLP)
modules are developed in parallel: a grammar-based (conventional, rule-based)
module and a data-oriented (memory-based, stochastic, DOP) module. In order to
compare the NLP modules, a formal evaluation has been carried out three years
after the start of the Programme. This paper describes the evaluation procedure
and the evaluation results. The grammar-based component performs much better
than the data-oriented one in this comparison.


title: Learning Transformation Rules to Find Grammatical Relations

abstract:
  Grammatical relationships are an important level of natural language
processing. We present a trainable approach to find these relationships through
transformation sequences and error-driven learning. Our approach finds
grammatical relationships between core syntax groups and bypasses much of the
parsing phase. On our training and test set, our procedure achieves 63.6%
recall and 77.3% precision (f-score = 69.8).


title: Automatically Selecting Useful Phrases for Dialogue Act Tagging

abstract:
  We present an empirical investigation of various ways to automatically
identify phrases in a tagged corpus that are useful for dialogue act tagging.
We found that a new method (which measures a phrase's deviation from an
optimally-predictive phrase), enhanced with a lexical filtering mechanism,
produces significantly better cues than manually-selected cue phrases, the
exhaustive set of phrases in a training corpus, and phrases chosen by
traditional metrics, like mutual information and information gain.


title:
Generalization of automatic sequences for numeration systems on a
  regular language

abstract:
  Let L be an infinite regular language on a totally ordered alphabet (A,<).
Feeding a finite deterministic automaton (with output) with the words of L
enumerated lexicographically with respect to < leads to an infinite sequence
over the output alphabet of the automaton. This process generalizes the concept
of k-automatic sequence for abstract numeration systems on a regular language
(instead of systems in base k). Here, I study the first properties of these
sequences and their relations with numeration systems.