title: Optimized Flooding Protocol for Ad hoc Networks

abstract:
  Flooding provides important control and route establishment functionality for
a number of unicast and multicast protocols in Mobile Ad Hoc Networks.
Considering its wide use as a building block for other network layer protocols,
the flooding methodology should deliver a packet from one node to all other
network nodes using as few messages as possible. In this paper, we propose the
Optimized Flooding Protocol (OFP), based on a variation of The Covering Problem
that is encountered in geometry, to minimize the unnecessary transmissions
drastically and still be able to cover the whole region. OFP does not need
hello messages and hence OFP saves a significant amount of wireless bandwidth
and incurs lesser overhead. We present simulation results to show the
efficiency of OFP in both ideal cases and randomly distributed networks.
Moreover, OFP is scalable with respect to density; in fact OFP requires lesser
number of transmissions at higher densities. OFP is also resilient to
transmission errors.


title:
Optimality of Universal Bayesian Sequence Prediction for General Loss
  and Alphabet

abstract:
  Various optimality properties of universal sequence predictors based on
Bayes-mixtures in general, and Solomonoff's prediction scheme in particular,
will be studied. The probability of observing $x_t$ at time $t$, given past
observations $x_1...x_{t-1}$ can be computed with the chain rule if the true
generating distribution $\mu$ of the sequences $x_1x_2x_3...$ is known. If
$\mu$ is unknown, but known to belong to a countable or continuous class $\M$
one can base ones prediction on the Bayes-mixture $\xi$ defined as a
$w_\nu$-weighted sum or integral of distributions $\nu\in\M$. The cumulative
expected loss of the Bayes-optimal universal prediction scheme based on $\xi$
is shown to be close to the loss of the Bayes-optimal, but infeasible
prediction scheme based on $\mu$. We show that the bounds are tight and that no
other predictor can lead to significantly smaller bounds. Furthermore, for
various performance measures, we show Pareto-optimality of $\xi$ and give an
Occam's razor argument that the choice $w_\nu\sim 2^{-K(\nu)}$ for the weights
is optimal, where $K(\nu)$ is the length of the shortest program describing
$\nu$. The results are applied to games of chance, defined as a sequence of
bets, observations, and rewards. The prediction schemes (and bounds) are
compared to the popular predictors based on expert advice. Extensions to
infinite alphabets, partial, delayed and probabilistic prediction,
classification, and more active systems are briefly discussed.


title: Make search become the internal function of Internet

abstract:
  Domain Resource Integrated System (DRIS) is introduced in this paper. DRIS is
a distributed information retrieval system, which will solve problems like poor
coverage, long update interval in current web search system. The most distinct
character of DRIS is that it's a public opening system, and acts as an internal
component of Internet, but not the production of a company. The implementation
of DRIS is also represented.


title: Generic and Efficient Program Monitoring by trace analysis

abstract:
  Program execution monitoring consists of checking whole executions for given
properties in order to collect global run-time information.
  Monitoring is very useful to maintain programs. However, application
developers face the following dilemma: either they use existing tools which
never exactly fit their needs, or they invest a lot of effort to implement
monitoring code.
  In this article we argue that, when an event-oriented tracer exists, the
compiler developers can enable the application developers to easily code their
own, relevant, monitors which will run efficiently.
  We propose a high-level operator, called foldt, which operates on execution
traces. One of the key advantages of our approach is that it allows a clean
separation of concerns; the definition of monitors is neither intertwined in
the user source code nor in the language compiler.
  We give a number of applications of the foldt operator to compute monitors
for Mercury program executions: execution profiles, graphical abstract views,
and two test coverage measurements. Each example is implemented by a few simple
lines of Mercury.
  Detailed measurements show acceptable performance of the basic mechanism of
foldt for executions of several millions of execution events.


title: 2 P2P or Not 2 P2P?

abstract:
  In the hope of stimulating discussion, we present a heuristic decision tree
that designers can use to judge the likely suitability of a P2P architecture
for their applications. It is based on the characteristics of a wide range of
P2P systems from the literature, both proposed and deployed.


title: Ackermann Encoding, Bisimulations, and OBDDs

abstract:
  We propose an alternative way to represent graphs via OBDDs based on the
observation that a partition of the graph nodes allows sharing among the
employed OBDDs. In the second part of the paper we present a method to compute
at the same time the quotient w.r.t. the maximum bisimulation and the OBDD
representation of a given graph. The proposed computation is based on an
OBDD-rewriting of the notion of Ackermann encoding of hereditarily finite sets
into natural numbers.


title:
Replay Debugging of Complex Real-Time Systems: Experiences from Two
  Industrial Case Studies

abstract:
  Deterministic replay is a method for allowing complex multitasking real-time
systems to be debugged using standard interactive debuggers. Even though
several replay techniques have been proposed for parallel, multi-tasking and
real-time systems, the solutions have so far lingered on a prototype academic
level, with very little results to show from actual state-of-the-practice
commercial applications. This paper describes a major deterministic replay
debugging case study performed on a full-scale industrial robot control system,
as well as a minor replay instrumentation case study performed on a military
aircraft radar system. In this article, we will show that replay debugging is
feasible in complex multi-million lines of code software projects running on
top of off-the-shelf real-time operating systems. Furthermore, we will discuss
how replay debugging can be introduced in existing systems without
impracticable analysis efforts. In addition, we will present benchmarking
results from both studies, indicating that the instrumentation overhead is
acceptable and affordable.


title: An Optimal Algorithm for the Maximum-Density Segment Problem

abstract:
  We address a fundamental problem arising from analysis of biomolecular
sequences. The input consists of two numbers $w_{\min}$ and $w_{\max}$ and a
sequence $S$ of $n$ number pairs $(a_i,w_i)$ with $w_i>0$. Let {\em segment}
$S(i,j)$ of $S$ be the consecutive subsequence of $S$ between indices $i$ and
$j$. The {\em density} of $S(i,j)$ is
$d(i,j)=(a_i+a_{i+1}+...+a_j)/(w_i+w_{i+1}+...+w_j)$. The {\em maximum-density
segment problem} is to find a maximum-density segment over all segments
$S(i,j)$ with $w_{\min}\leq w_i+w_{i+1}+...+w_j \leq w_{\max}$. The best
previously known algorithm for the problem, due to Goldwasser, Kao, and Lu,
runs in $O(n\log(w_{\max}-w_{\min}+1))$ time. In the present paper, we solve
the problem in O(n) time. Our approach bypasses the complicated {\em right-skew
decomposition}, introduced by Lin, Jiang, and Chao. As a result, our algorithm
has the capability to process the input sequence in an online manner, which is
an important feature for dealing with genome-scale sequences. Moreover, for a
type of input sequences $S$ representable in $O(m)$ space, we show how to
exploit the sparsity of $S$ and solve the maximum-density segment problem for
$S$ in $O(m)$ time.


title: LCG-1 Deployment and usage experience

abstract:
  LCG-1 is the second release of the software framework for the LHC Computing
Grid project. In our work we describe the installation process, arising
problems and their solutions, and configuration tuning details of the complete
LCG-1 site, including all LCG elements required for the self-sufficient site.


title: Temporalized logics and automata for time granularity

abstract:
  Suitable extensions of the monadic second-order theory of k successors have
been proposed in the literature to capture the notion of time granularity. In
this paper, we provide the monadic second-order theories of downward unbounded
layered structures, which are infinitely refinable structures consisting of a
coarsest domain and an infinite number of finer and finer domains, and of
upward unbounded layered structures, which consist of a finest domain and an
infinite number of coarser and coarser domains, with expressively complete and
elementarily decidable temporal logic counterparts.
  We obtain such a result in two steps. First, we define a new class of
combined automata, called temporalized automata, which can be proved to be the
automata-theoretic counterpart of temporalized logics, and show that relevant
properties, such as closure under Boolean operations, decidability, and
expressive equivalence with respect to temporal logics, transfer from component
automata to temporalized ones. Then, we exploit the correspondence between
temporalized logics and automata to reduce the task of finding the temporal
logic counterparts of the given theories of time granularity to the easier one
of finding temporalized automata counterparts of them.


title: The Chameleon Type Debugger (Tool Demonstration)

abstract:
  In this tool demonstration, we give an overview of the Chameleon type
debugger. The type debugger's primary use is to identify locations within a
source program which are involved in a type error. By further examining these
(potentially) problematic program locations, users gain a better understanding
of their program and are able to work towards the actual mistake which was the
cause of the type error. The debugger is interactive, allowing the user to
provide additional information to narrow down the search space. One of the
novel aspects of the debugger is the ability to explain erroneous-looking
types. In the event that an unexpected type is inferred, the debugger can
highlight program locations which contributed to that result. Furthermore, due
to the flexible constraint-based foundation that the debugger is built upon, it
can naturally handle advanced type system features such as Haskell's type
classes and functional dependencies.


title: Logic-Based Specification Languages for Intelligent Software Agents

abstract:
  The research field of Agent-Oriented Software Engineering (AOSE) aims to find
abstractions, languages, methodologies and toolkits for modeling, verifying,
validating and prototyping complex applications conceptualized as Multiagent
Systems (MASs). A very lively research sub-field studies how formal methods can
be used for AOSE. This paper presents a detailed survey of six logic-based
executable agent specification languages that have been chosen for their
potential to be integrated in our ARPEGGIO project, an open framework for
specifying and prototyping a MAS. The six languages are ConGoLog, Agent-0, the
IMPACT agent programming language, DyLog, Concurrent METATEM and Ehhf. For each
executable language, the logic foundations are described and an example of use
is shown. A comparison of the six languages and a survey of similar approaches
complete the paper, together with considerations of the advantages of using
logic-based languages in MAS modeling and prototyping.


title:
Fine-Grained Authorization for Job Execution in the Grid: Design and
  Implementation

abstract:
  In this paper we describe our work on enabling fine-grained authorization for
resource usage and management. We address the need of virtual organizations to
enforce their own polices in addition to those of the resource owners, in
regard to both resource consumption and job management. To implement this
design, we propose changes and extensions to the Globus Toolkit's version 2
resource management mechanism. We describe the prototype and the policy
language that we designed to express fine-grained policies, and we present an
analysis of our solution.


title:
Great Expectations. Part I: On the Customizability of Generalized
  Expected Utility

abstract:
  We propose a generalization of expected utility that we call generalized EU
(GEU), where a decision maker's beliefs are represented by plausibility
measures, and the decision maker's tastes are represented by general (i.e.,not
necessarily real-valued) utility functions. We show that every agent,
``rational'' or not, can be modeled as a GEU maximizer. We then show that we
can customize GEU by selectively imposing just the constraints we want. In
particular, we show how each of Savage's postulates corresponds to constraints
on GEU.


title:
Great Expectations. Part II: Generalized Expected Utility as a Universal
  Decision Rule

abstract:
  Many different rules for decision making have been introduced in the
literature. We show that a notion of generalized expected utility proposed in
Part I of this paper is a universal decision rule, in the sense that it can
represent essentially all other decision rules.


title: Using Counterfactuals in Knowledge-Based Programming

abstract:
  This paper adds counterfactuals to the framework of knowledge-based programs
of Fagin, Halpern, Moses, and Vardi. The use of counterfactuals is illustrated
by designing a protocol in which an agent stops sending messages once it knows
that it is safe to do so. Such behavior is difficult to capture in the original
framework because it involves reasoning about counterfactual executions,
including ones that are not consistent with the protocol. Attempts to formalize
these notions without counterfactuals are shown to lead to rather
counterintuitive behavior.


title: Staging Transformations for Multimodal Web Interaction Management

abstract:
  Multimodal interfaces are becoming increasingly ubiquitous with the advent of
mobile devices, accessibility considerations, and novel software technologies
that combine diverse interaction media. In addition to improving access and
delivery capabilities, such interfaces enable flexible and personalized dialogs
with websites, much like a conversation between humans. In this paper, we
present a software framework for multimodal web interaction management that
supports mixed-initiative dialogs between users and websites. A
mixed-initiative dialog is one where the user and the website take turns
changing the flow of interaction. The framework supports the functional
specification and realization of such dialogs using staging transformations --
a theory for representing and reasoning about dialogs based on partial input.
It supports multiple interaction interfaces, and offers sessioning, caching,
and co-ordination functions through the use of an interaction manager. Two case
studies are presented to illustrate the promise of this approach.


title:
Set K-Cover Algorithms for Energy Efficient Monitoring in Wireless
  Sensor Networks

abstract:
  Wireless sensor networks (WSNs) are emerging as an effective means for
environment monitoring. This paper investigates a strategy for energy efficient
monitoring in WSNs that partitions the sensors into covers, and then activates
the covers iteratively in a round-robin fashion. This approach takes advantage
of the overlap created when many sensors monitor a single area. Our work builds
upon previous work in "Power Efficient Organization of Wireless Sensor
Networks" by Slijepcevic and Potkonjak, where the model is first formulated. We
have designed three approximation algorithms for a variation of the SET K-COVER
problem, where the objective is to partition the sensors into covers such that
the number of covers that include an area, summed over all areas, is maximized.
The first algorithm is randomized and partitions the sensors, in expectation,
within a fraction 1 - 1/e (~.63) of the optimum. We present two other
deterministic approximation algorithms. One is a distributed greedy algorithm
with a 1/2 approximation ratio and the other is a centralized greedy algorithm
with a 1 - 1/e approximation ratio. We show that it is NP-Complete to guarantee
better than 15/16 of the optimal coverage, indicating that all three algorithms
perform well with respect to the best approximation algorithm possible.
Simulations indicate that in practice, the deterministic algorithms perform far
above their worst case bounds, consistently covering more than 72% of what is
covered by an optimum solution. Simulations also indicate that the increase in
longevity is proportional to the amount of overlap amongst the sensors. The
algorithms are fast, easy to use, and according to simulations, significantly
increase the longevity of sensor networks. The randomized algorithm in
particular seems quite practical.


title:
Towards an Intelligent Database System Founded on the SP Theory of
  Computing and Cognition

abstract:
  The SP theory of computing and cognition, described in previous publications,
is an attractive model for intelligent databases because it provides a simple
but versatile format for different kinds of knowledge, it has capabilities in
artificial intelligence, and it can also function like established database
models when that is required.
  This paper describes how the SP model can emulate other models used in
database applications and compares the SP model with those other models. The
artificial intelligence capabilities of the SP model are reviewed and its
relationship with other artificial intelligence systems is described. Also
considered are ways in which current prototypes may be translated into an
'industrial strength' working system.


title: A Very Short Self-Interpreter

abstract:
  In this paper we would like to present a very short (possibly the shortest)
self-interpreter, based on a simplistic Turing-complete imperative language.
This interpreter explicitly processes the statements of the language, which
means the interpreter constitutes a description of the language inside that
same language. The paper does not require any specific knowledge; however,
experience in programming and a vivid imagination are beneficial.


title:
The Rank-Frequency Analysis for the Functional Style Corpora in the
  Ukrainian Language

abstract:
  We use the rank-frequency analysis for the estimation of Kernel Vocabulary
size within specific corpora of Ukrainian. The extrapolation of high-rank
behaviour is utilized for estimation of the total vocabulary size.


title:
Visualization of variations in human brain morphology using
  differentiating reflection functions

abstract:
  Conventional visualization media such as MRI prints and computer screens are
inherently two dimensional, making them incapable of displaying true 3D volume
data sets. By applying only transparency or intensity projection, and ignoring
light-matter interaction, results will likely fail to give optimal results.
Little research has been done on using reflectance functions to visually
separate the various segments of a MRI volume. We will explore if applying
specific reflectance functions to individual anatomical structures can help in
building an intuitive 2D image from a 3D dataset. We will test our hypothesis
by visualizing a statistical analysis of the genetic influences on variations
in human brain morphology because it inherently contains complex and many
different types of data making it a good candidate for our approach


title: Improving TCP/IP Performance over Wireless IEEE 802.11 Link

abstract:
  Cellular phones, wireless laptops, personal portable devices that supports
both voice and data access are all examples of communicating devices that uses
wireless communication. Sine TCP/IP (and UDP) is the dominant technology in use
in the internet, it is expected that they will be used (and they are currently)
over wireless connections. In this paper, we investigate the performance of the
TCP (and UDP) over IEEE802.11 wireless MAC protocol. We investigate the
performance of the TCP and UDP assuming three different traffic patterns. First
bulk transmission where the main concern is the throughput. Second real-time
audio (using UDP) in the existence of bulk TCP transmission where the main
concern is the packet loss for audio traffic. Finally web traffic where the
main concern is the response time. We also investigate the effect of using
forward Error Correction (FEC) technique and the MAC sublayer parameters on the
throughput and response time.


title: Measuring the Functional Load of Phonological Contrasts

abstract:
  Frequency counts are a measure of how much use a language makes of a
linguistic unit, such as a phoneme or word. However, what is often important is
not the units themselves, but the contrasts between them. A measure is
therefore needed for how much use a language makes of a contrast, i.e. the
functional load (FL) of the contrast. We generalize previous work in
linguistics and speech recognition and propose a family of measures for the FL
of several phonological contrasts, including phonemic oppositions, distinctive
features, suprasegmentals, and phonological rules. We then test it for
robustness to changes of corpora. Finally, we provide examples in Cantonese,
Dutch, English, German and Mandarin, in the context of historical linguistics,
language acquisition and speech recognition. More information can be found at
http://dinoj.info/research/fload


title:
DUCT: An Interactive Define-Use Chain Navigation Tool for Relative
  Debugging

abstract:
  This paper describes an interactive tool that facilitates following
define-use chains in large codes. The motivation for the work is to support
relative debugging, where it is necessary to iteratively refine a set of
asser-tions between different versions of a program. DUCT is novel because it
exploits the Microsoft Intermediate Language (MSIL) that underpins the .NET
Framework. Accordingly, it works on a wide range of programming languages
without any modification. The paper describes the design and implementation of
DUCT, and then illustrates its use with a small case study.


title:
XPath-Logic and XPathLog: A Logic-Programming Style XML Data
  Manipulation Language

abstract:
  We define XPathLog as a Datalog-style extension of XPath. XPathLog provides a
clear, declarative language for querying and manipulating XML whose
perspectives are especially in XML data integration. In our characterization,
the formal semantics is defined wrt. an edge-labeled graph-based model which
covers the XML data model. We give a complete, logic-based characterization of
XML data and the main language concept for XML, XPath. XPath-Logic extends the
XPath language with variable bindings and embeds it into first-order logic.
XPathLog is then the Horn fragment of XPath-Logic, providing a Datalog-style,
rule-based language for querying and manipulating XML data. The model-theoretic
semantics of XPath-Logic serves as the base of XPathLog as a logic-programming
language, whereas also an equivalent answer-set semantics for evaluating
XPathLog queries is given. In contrast to other approaches, the XPath syntax
and semantics is also used for a declarative specification how the database
should be updated: when used in rule heads, XPath filters are interpreted as
specifications of elements and properties which should be added to the
database.


title: Quantum m-out-of-n Oblivious Transfer

abstract:
  In the m-out-of-n oblivious transfer (OT) model, one party Alice sends n bits
to another party Bob, Bob can get only m bits from the n bits. However, Alice
cannot know which m bits Bob received. Y.Mu[MJV02]} and Naor[Naor01] presented
classical m-out-of-n oblivious transfer based on discrete logarithm. As the
work of Shor [Shor94], the discrete logarithm can be solved in polynomial time
by quantum computers, so such OTs are unsafe to the quantum computer. In this
paper, we construct a quantum m-out-of-n OT (QOT) scheme based on the
transmission of polarized light and show that the scheme is robust to general
attacks, i.e. the QOT scheme satisfies statistical correctness and statistical
privacy.


title: Idempotent I/O for safe time travel

abstract:
  Debuggers for logic programming languages have traditionally had a capability
most other debuggers did not: the ability to jump back to a previous state of
the program, effectively travelling back in time in the history of the
computation. This ``retry'' capability is very useful, allowing programmers to
examine in detail a part of the computation that they previously stepped over.
Unfortunately, it also creates a problem: while the debugger may be able to
restore the previous values of variables, it cannot restore the part of the
program's state that is affected by I/O operations. If the part of the
computation being jumped back over performs I/O, then the program will perform
these I/O operations twice, which will result in unwanted effects ranging from
the benign (e.g. output appearing twice) to the fatal (e.g. trying to close an
already closed file). We present a simple mechanism for ensuring that every I/O
action called for by the program is executed at most once, even if the
programmer asks the debugger to travel back in time from after the action to
before the action. The overhead of this mechanism is low enough and can be
controlled well enough to make it practical to use it to debug computations
that do significant amounts of I/O.


title: S-ToPSS: Semantic Toronto Publish/Subscribe System

abstract:
  The increase in the amount of data on the Internet has led to the development
of a new generation of applications based on selective information
dissemination where, data is distributed only to interested clients. Such
applications require a new middleware architecture that can efficiently match
user interests with available information. Middleware that can satisfy this
requirement include event-based architectures such as publish-subscribe
systems. In this demonstration paper we address the problem of semantic
matching. We investigate how current publish/subscribe systems can be extended
with semantic capabilities. Our main contribution is the development and
validation (through demonstration) of a semantic pub/sub system prototype
S-ToPSS (Semantic Toronto Publish/Subscribe System).


title: Toward Attribute Efficient Learning Algorithms

abstract:
  We make progress on two important problems regarding attribute efficient
learnability.
  First, we give an algorithm for learning decision lists of length $k$ over
$n$ variables using $2^{\tilde{O}(k^{1/3})} \log n$ examples and time
$n^{\tilde{O}(k^{1/3})}$. This is the first algorithm for learning decision
lists that has both subexponential sample complexity and subexponential running
time in the relevant parameters. Our approach establishes a relationship
between attribute efficient learning and polynomial threshold functions and is
based on a new construction of low degree, low weight polynomial threshold
functions for decision lists. For a wide range of parameters our construction
matches a 1994 lower bound due to Beigel for the ODDMAXBIT predicate and gives
an essentially optimal tradeoff between polynomial threshold function degree
and weight.
  Second, we give an algorithm for learning an unknown parity function on $k$
out of $n$ variables using $O(n^{1-1/k})$ examples in time polynomial in $n$.
For $k=o(\log n)$ this yields a polynomial time algorithm with sample
complexity $o(n)$. This is the first polynomial time algorithm for learning
parity on a superconstant number of variables with sublinear sample complexity.


title:
Combining Logic Programs and Monadic Second Order Logics by Program
  Transformation

abstract:
  We present a program synthesis method based on unfold/fold transformation
rules which can be used for deriving terminating definite logic programs from
formulas of the Weak Monadic Second Order theory of one successor (WS1S). This
synthesis method can also be used as a proof method which is a decision
procedure for closed formulas of WS1S. We apply our synthesis method for
translating CLP(WS1S) programs into logic programs and we use it also as a
proof method for verifying safety properties of infinite state systems.


title:
Derivation of Efficient Logic Programs by Specialization and Reduction
  of Nondeterminism

abstract:
  Program specialization is a program transformation methodology which improves
program efficiency by exploiting the information about the input data which are
available at compile time. We show that current techniques for program
specialization based on partial evaluation do not perform well on
nondeterministic logic programs. We then consider a set of transformation rules
which extend the ones used for partial evaluation, and we propose a strategy
for guiding the application of these extended rules so to derive very efficient
specialized programs. The efficiency improvements which sometimes are
exponential, are due to the reduction of nondeterminism and to the fact that
the computations which are performed by the initial programs in different
branches of the computation trees, are performed by the specialized programs
within single branches. In order to reduce nondeterminism we also make use of
mode information for guiding the unfolding process. To exemplify our technique,
we show that we can automatically derive very efficient matching programs and
parsers for regular languages. The derivations we have performed could not have
been done by previously known partial evaluation techniques.


title:
Unsupervised Grammar Induction in a Framework of Information Compression
  by Multiple Alignment, Unification and Search

abstract:
  This paper describes a novel approach to grammar induction that has been
developed within a framework designed to integrate learning with other aspects
of computing, AI, mathematics and logic. This framework, called "information
compression by multiple alignment, unification and search" (ICMAUS), is founded
on principles of Minimum Length Encoding pioneered by Solomonoff and others.
Most of the paper describes SP70, a computer model of the ICMAUS framework that
incorporates processes for unsupervised learning of grammars. An example is
presented to show how the model can infer a plausible grammar from appropriate
input. Limitations of the current model and how they may be overcome are
briefly discussed.


title: Algebras for Agent Norm-Regulation

abstract:
  An abstract architecture for idealized multi-agent systems whose behaviour is
regulated by normative systems is developed and discussed. Agent choices are
determined partially by the preference ordering of possible states and
partially by normative considerations: The agent chooses that act which leads
to the best outcome of all permissible actions. If an action is non-permissible
depends on if the result of performing that action leads to a state satisfying
a condition which is forbidden, according to the norms regulating the
multi-agent system. This idea is formalized by defining set-theoretic
predicates characterizing multi-agent systems. The definition of the predicate
uses decision theory, the Kanger-Lindahl theory of normative positions, and an
algebraic representation of normative systems.


title:
I know what you mean: semantic issues in Internet-scale
  publish/subscribe systems

abstract:
  In recent years, the amount of information on the Internet has increased
exponentially developing great interest in selective information dissemination
systems. The publish/subscribe paradigm is particularly suited for designing
systems for routing information and requests according to their content
throughout wide-area network of brokers. Current publish/subscribe systems use
limited syntax-based content routing but since publishers and subscribers are
anonymous and decoupled in time, space and location, often over wide-area
network boundary, they do not necessarily speak the same language.
Consequently, adding semantics to current publish/subscribe systems is
important. In this paper we identify and examine the issues in developing
semantic-based content routing for publish/subscribe broker networks.


title: Turning CARTwheels: An Alternating Algorithm for Mining Redescriptions

abstract:
  We present an unusual algorithm involving classification trees where two
trees are grown in opposite directions so that they are matched at their
leaves. This approach finds application in a new data mining task we formulate,
called "redescription mining". A redescription is a shift-of-vocabulary, or a
different way of communicating information about a given subset of data; the
goal of redescription mining is to find subsets of data that afford multiple
descriptions. We highlight the importance of this problem in domains such as
bioinformatics, which exhibit an underlying richness and diversity of data
descriptors (e.g., genes can be studied in a variety of ways). Our approach
helps integrate multiple forms of characterizing datasets, situates the
knowledge gained from one dataset in the context of others, and harnesses
high-level abstractions for uncovering cryptic and subtle features of data.
Algorithm design decisions, implementation details, and experimental results
are presented.


title: Performance of TCP/UDP under Ad Hoc IEEE802.11

abstract:
  TCP is the De facto standard for connection oriented transport layer
protocol, while UDP is the De facto standard for transport layer protocol,
which is used with real time traffic for audio and video. Although there have
been many attempts to measure and analyze the performance of the TCP protocol
in wireless networks, very few research was done on the UDP or the interaction
between TCP and UDP traffic over the wireless link. In this paper, we tudy the
performance of TCP and UDP over IEEE802.11 ad hoc network. We used two
topologies, a string and a mesh topology. Our work indicates that IEEE802.11 as
a ad-hoc network is not very suitable for bulk transfer using TCP. It also
indicates that it is much better for real-time audio. Although one has to be
careful here since real-time audio does require much less bandwidth than the
wireless link bandwidth. Careful and detailed studies are needed to further
clarify that issue.


title:
Data mining and Privacy in Public Sector using Intelligent Agents
  (discussion paper)

abstract:
  The public sector comprises government agencies, ministries, education
institutions, health providers and other types of government, commercial and
not-for-profit organisations. Unlike commercial enterprises, this environment
is highly heterogeneous in all aspects. This forms a complex network which is
not always optimised. A lack of optimisation and communication hinders
information sharing between the network nodes limiting the flow of information.
Another limiting aspect is privacy of personal information and security of
operations of some nodes or segments of the network. Attempts to reorganise the
network or improve communications to make more information available for
sharing and analysis may be hindered or completely halted by public concerns
over privacy, political agendas, social and technological barriers. This paper
discusses a technical solution for information sharing while addressing the
privacy concerns with no need for reorganisation of the existing public sector
infrastructure . The solution is based on imposing an additional layer of
Intelligent Software Agents and Knowledge Bases for data mining and analysis.


title:
Integrating existing cone-shaped and projection-based cardinal direction
  relations and a TCSP-like decidable generalisation

abstract:
  We consider the integration of existing cone-shaped and projection-based
calculi of cardinal direction relations, well-known in QSR. The more general,
integrating language we consider is based on convex constraints of the
qualitative form $r(x,y)$, $r$ being a cone-shaped or projection-based cardinal
direction atomic relation, or of the quantitative form $(\alpha ,\beta)(x,y)$,
with $\alpha ,\beta\in [0,2\pi)$ and $(\beta -\alpha)\in [0,\pi ]$: the meaning
of the quantitative constraint, in particular, is that point $x$ belongs to the
(convex) cone-shaped area rooted at $y$, and bounded by angles $\alpha$ and
$\beta$. The general form of a constraint is a disjunction of the form
$[r_1\vee...\vee r_{n_1}\vee (\alpha_1,\beta_1)\vee...\vee (\alpha
_{n_2},\beta_{n_2})](x,y)$, with $r_i(x,y)$, $i=1... n_1$, and $(\alpha
_i,\beta_i)(x,y)$, $i=1... n_2$, being convex constraints as described above:
the meaning of such a general constraint is that, for some $i=1... n_1$,
$r_i(x,y)$ holds, or, for some $i=1... n_2$, $(\alpha_i,\beta_i)(x,y)$ holds. A
conjunction of such general constraints is a $\tcsp$-like CSP, which we will
refer to as an $\scsp$ (Spatial Constraint Satisfaction Problem). An effective
solution search algorithm for an $\scsp$ will be described, which uses (1)
constraint propagation, based on a composition operation to be defined, as the
filtering method during the search, and (2) the Simplex algorithm, guaranteeing
completeness, at the leaves of the search tree. The approach is particularly
suited for large-scale high-level vision, such as, e.g., satellite-like
surveillance of a geographic area.


title:
A Situation Calculus-based Approach To Model Ubiquitous Information
  Services

abstract:
  This paper presents an augmented situation calculus-based approach to model
autonomous computing paradigm in ubiquitous information services. To make it
practical for commercial development and easier to support autonomous paradigm
imposed by ubiquitous information services, we made improvements based on
Reiter's standard situation calculus. First we explore the inherent
relationship between fluents and evolution: since not all fluents contribute to
systems' evolution and some fluents can be derived from some others, we define
those fluents that are sufficient and necessary to determine evolutional
potential as decisive fluents, and then we prove that their successor states
wrt to deterministic complex actions satisfy Markov property. Then, within the
calculus framework we build, we introduce validity theory to model the
autonomous services with application-specific validity requirements, including:
validity fluents to axiomatize validity requirements, heuristic multiple
alternative service choices ranging from complete acceptance, partial
acceptance, to complete rejection, and validity-ensured policy to comprise such
alternative service choices into organic, autonomously-computable services. Our
approach is demonstrated by a ubiquitous calendaring service, ACS, throughout
the paper.


title: Weak Bezout inequality for D-modules

abstract:
  Let $\{w_{i,j}\}_{1\leq i\leq n, 1\leq j\leq s} \subset
L_m=F(X_1,...,X_m)[{\partial \over \partial X_1},..., {\partial \over \partial
X_m}]$ be linear partial differential operators of orders with respect to
${\partial \over \partial X_1},..., {\partial \over \partial X_m}$ at most $d$.
We prove an upper bound n(4m^2d\min\{n,s\})^{4^{m-t-1}(2(m-t))} on the leading
coefficient of the Hilbert-Kolchin polynomial of the left $L_m$-module
$<\{w_{1,j}, ..., w_{n,j}\}_{1\leq j \leq s} > \subset L_m^n$ having the
differential type $t$ (also being equal to the degree of the Hilbert-Kolchin
polynomial). The main technical tool is the complexity bound on solving systems
of linear equations over {\it algebras of fractions} of the form
$$L_m(F[X_1,..., X_m, {\partial \over \partial X_1},..., {\partial \over
\partial X_k}])^{-1}.$$


title: Copyright and Creativity: Authors and Photographers

abstract:
  The history of the occupations "author" and "photographer" provides an
insightful perspective on copyright and creativity. The concept of the romantic
author, associated with personal creative genius, gained prominence in the
eighteenth century. However, in the U.S. in 1900 only about three thousand
persons professed their occupation to be "author." Self-professed
"photographers" were then about ten times as numerous as authors. Being a
photographer was associated with manufacturing and depended only on mastering
technical skills and making a living. Being an author, in contrast, was an
elite status associated with science and literature. Across the twentieth
century, the number of writers and authors grew much more rapidly than the
number of photographers. The relative success of writers and authors in
creating jobs seems to have depended not on differences in copyright or
possibilities for self-production, but on greater occupational innovation.
Creativity in organizing daily work is an important form of creativity.


title: The concept of strong and weak virtual reality

abstract:
  We approach the virtual reality phenomenon by studying its relationship to
set theory, and we investigate the case where this is done using the
wellfoundedness property of sets. Our hypothesis is that non-wellfounded sets
(hypersets) give rise to a different quality of virtual reality than do
familiar wellfounded sets. We initially provide an alternative approach to
virtual reality based on Sommerhoff's idea of first and second order
self-awareness; both categories of self-awareness are considered as necessary
conditions for consciousness in terms of higher cognitive functions. We then
introduce a representation of first and second order self-awareness through
sets, and assume that these sets, which we call events, originally form a
collection of wellfounded sets. Strong virtual reality characterizes virtual
reality environments which have the limited capacity to create only events
associated with wellfounded sets. In contrast, the more general concept of weak
virtual reality characterizes collections of virtual reality mediated events
altogether forming an entirety larger than any collection of wellfounded sets.
By giving reference to Aczel's hyperset theory we indicate that this definition
is not empty, because hypersets encompass wellfounded sets already. Moreover,
we argue that weak virtual reality could be realized in human history through
continued progress in computer technology. Finally, we reformulate our
characterization into a more general framework, and use Baltag's Structural
Theory of Sets (STS) to show that within this general hyperset theory
Sommerhoff's first and second order self-awareness as well as both concepts of
virtual reality admit a consistent mathematical representation.


title: On Structuring Proof Search for First Order Linear Logic

abstract:
  Full first order linear logic can be presented as an abstract logic
programming language in Miller's system Forum, which yields a sensible
operational interpretation in the 'proof search as computation' paradigm.
However, Forum still has to deal with syntactic details that would normally be
ignored by a reasonable operational semantics. In this respect, Forum improves
on Gentzen systems for linear logic by restricting the language and the form of
inference rules. We further improve on Forum by restricting the class of
formulae allowed, in a system we call G-Forum, which is still equivalent to
full first order linear logic. The only formulae allowed in G-Forum have the
same shape as Forum sequents: the restriction does not diminish expressiveness
and makes G-Forum amenable to proof theoretic analysis. G-Forum consists of two
(big) inference rules, for which we show a cut elimination procedure. This does
not need to appeal to finer detail in formulae and sequents than is provided by
G-Forum, thus successfully testing the internal symmetries of our system.


title: Hybrid LQG-Neural Controller for Inverted Pendulum System

abstract:
  The paper presents a hybrid system controller, incorporating a neural and an
LQG controller. The neural controller has been optimized by genetic algorithms
directly on the inverted pendulum system. The failure free optimization process
stipulated a relatively small region of the asymptotic stability of the neural
controller, which is concentrated around the regulation point. The presented
hybrid controller combines benefits of a genetically optimized neural
controller and an LQG controller in a single system controller. High quality of
the regulation process is achieved through utilization of the neural
controller, while stability of the system during transient processes and a wide
range of operation are assured through application of the LQG controller. The
hybrid controller has been validated by applying it to a simulation model of an
inherently unstable system of inverted pendulum.


title:
Improving spam filtering by combining Naive Bayes with simple k-nearest
  neighbor searches

abstract:
  Using naive Bayes for email classification has become very popular within the
last few months. They are quite easy to implement and very efficient. In this
paper we want to present empirical results of email classification using a
combination of naive Bayes and k-nearest neighbor searches. Using this
technique we show that the accuracy of a Bayes filter can be improved slightly
for a high number of features and significantly for a small number of features.


title: A Cartography for 2x2 Symmetric Games

abstract:
  A bidimensional representation of the space of 2x2 Symmetric Games in the
strategic representation is proposed. This representation provides a tool for
the classification of 2x2 symmetric games, quantification of the fraction of
them having a certain feature, and predictions of changes in the
characteristics of a game when a change in done on the payoff matrix that
defines it.


title:
Benchmarking and Implementation of Probability-Based Simulations on
  Programmable Graphics Cards

abstract:
  The latest Graphics Processing Units (GPUs) are reported to reach up to
  200 billion floating point operations per second (200 Gflops) and to have
price performance of 0.1 cents per M flop. These facts raise great interest in
the plausibility of extending the GPUs' use to non-graphics applications, in
particular numerical simulations on structured grids (lattice).
  We review previous work on using GPUs for non-graphics applications,
implement probability-based simulations on the GPU, namely the
  Ising and percolation models, implement vector operation benchmarks for the
GPU, and finally compare the CPU's and GPU's performance.
  A general conclusion from the results obtained is that moving computations
from the CPU to the GPU is feasible, yielding good time and price performance,
for certain lattice computations.
  Preliminary results also show that it is feasible to use them in parallel


title:
Counting complexity classes for numeric computations II: algebraic and
  semialgebraic sets

abstract:
  We define counting classes #P_R and #P_C in the Blum-Shub-Smale setting of
computations over the real or complex numbers, respectively. The problems of
counting the number of solutions of systems of polynomial inequalities over R,
or of systems of polynomial equalities over C, respectively, turn out to be
natural complete problems in these classes. We investigate to what extent the
new counting classes capture the complexity of computing basic topological
invariants of semialgebraic sets (over R) and algebraic sets (over C). We prove
that the problem of computing the (modified) Euler characteristic of
semialgebraic sets is FP_R^{#P_R}-complete, and that the problem of computing
the geometric degree of complex algebraic sets is FP_C^{#P_C}-complete. We also
define new counting complexity classes in the classical Turing model via taking
Boolean parts of the classes above, and show that the problems to compute the
Euler characteristic and the geometric degree of (semi)algebraic sets given by
integer polynomials are complete in these classes. We complement the results in
the Turing model by proving, for all k in N, the FPSPACE-hardness of the
problem of computing the k-th Betti number of the zet of real zeros of a given
integer polynomial. This holds with respect to the singular homology as well as
for the Borel-Moore homology.


title:
Embedding Web-based Statistical Translation Models in Cross-Language
  Information Retrieval

abstract:
  Although more and more language pairs are covered by machine translation
services, there are still many pairs that lack translation resources.
Cross-language information retrieval (CLIR) is an application which needs
translation functionality of a relatively low level of sophistication since
current models for information retrieval (IR) are still based on a
bag-of-words. The Web provides a vast resource for the automatic construction
of parallel corpora which can be used to train statistical translation models
automatically. The resulting translation models can be embedded in several ways
in a retrieval model. In this paper, we will investigate the problem of
automatically mining parallel texts from the Web and different ways of
integrating the translation models within the retrieval process. Our
experiments on standard test collections for CLIR show that the Web-based
translation models can surpass commercial MT systems in CLIR tasks. These
results open the perspective of constructing a fully automatic query
translation device for CLIR at a very low cost.


title:
Failure-Free Genetic Algorithm Optimization of a System Controller Using
  SAFE/LEARNING Controllers in Tandem

abstract:
  The paper presents a method for failure free genetic algorithm optimization
of a system controller. Genetic algorithms present a powerful tool that
facilitates producing near-optimal system controllers. Applied to such methods
of computational intelligence as neural networks or fuzzy logic, these methods
are capable of combining the non-linear mapping capabilities of the latter with
learning the system behavior directly, that is, without a prior model. At the
same time, genetic algorithms routinely produce solutions that lead to the
failure of the controlled system. Such solutions are generally unacceptable for
applications where safe operation must be guaranteed. We present here a method
of design, which allows failure-free application of genetic algorithms through
utilization of SAFE and LEARNING controllers in tandem, where the SAFE
controller recovers the system from dangerous states while the LEARNING
controller learns its behavior. The method has been validated by applying it to
an inherently unstable system of inverted pendulum.


title: Designing of a Community-based Translation Center

abstract:
  Interfaces that support multi-lingual content can reach a broader community.
We wish to extend the reach of CITIDEL, a digital library for computing
education materials, to support multiple languages. By doing so, we hope that
it will increase the number of users, and in turn the number of resources. This
paper discusses three approaches to translation (automated translation,
developer-based, and community-based), and a brief evaluation of these
approaches. It proposes a design for an online community translation center
where volunteers help translate interface components and educational materials
available in CITIDEL.


title: Constraint Optimization and Statistical Mechanics

abstract:
  In these lectures I will present an introduction to the results that have
been recently obtained in constraint optimization of random problems using
statistical mechanics techniques. After presenting the general results, in
order to simplify the presentation I will describe in details only the problems
related to the coloring of a random graph.


title: Methods to Model-Check Parallel Systems Software

abstract:
  We report on an effort to develop methodologies for formal verification of
parts of the Multi-Purpose Daemon (MPD) parallel process management system. MPD
is a distributed collection of communicating processes. While the individual
components of the collection execute simple algorithms, their interaction leads
to unexpected errors that are difficult to uncover by conventional means. Two
verification approaches are discussed here: the standard model checking
approach using the software model checker SPIN and the nonstandard use of a
general-purpose first-order resolution-style theorem prover OTTER to conduct
the traditional state space exploration. We compare modeling methodology and
analyze performance and scalability of the two methods with respect to
verification of MPD.


title: Fuzziness versus probability again

abstract:
  A construction of a fuzzy logic controller based on an analogy between fuzzy
conditional rule of inference and marginal probability in terms of the
conditional probability function has been proposed.


title: Logical Characterizations of Heap Abstractions

abstract:
  Shape analysis concerns the problem of determining "shape invariants" for
programs that perform destructive updating on dynamically allocated storage. In
recent work, we have shown how shape analysis can be performed, using an
abstract interpretation based on 3-valued first-order logic. In that work,
concrete stores are finite 2-valued logical structures, and the sets of stores
that can possibly arise during execution are represented (conservatively) using
a certain family of finite 3-valued logical structures. In this paper, we show
how 3-valued structures that arise in shape analysis can be characterized using
formulas in first-order logic with transitive closure.
  We also define a non-standard ("supervaluational") semantics for 3-valued
first-order logic that is more precise than a conventional 3-valued semantics,
and demonstrate that the supervaluational semantics can be effectively
implemented using existing theorem provers.


title: Soft lambda-calculus: a language for polynomial time computation

abstract:
  Soft linear logic ([Lafont02]) is a subsystem of linear logic characterizing
the class PTIME. We introduce Soft lambda-calculus as a calculus typable in the
intuitionistic and affine variant of this logic. We prove that the (untyped)
terms of this calculus are reducible in polynomial time. We then extend the
type system of Soft logic with recursive types. This allows us to consider
non-standard types for representing lists. Using these datatypes we examine the
concrete expressivity of Soft lambda-calculus with the example of the insertion
sort algorithm.


title:
Taking the Initiative with Extempore: Exploring Out-of-Turn Interactions
  with Websites

abstract:
  We present the first study to explore the use of out-of-turn interaction in
websites. Out-of-turn interaction is a technique which empowers the user to
supply unsolicited information while browsing. This approach helps flexibly
bridge any mental mismatch between the user and the website, in a manner
fundamentally different from faceted browsing and site-specific search tools.
We built a user interface (Extempore) which accepts out-of-turn input via voice
or text; and employed it in a US congressional website, to determine if users
utilize out-of-turn interaction for information-finding tasks, and their
rationale for doing so. The results indicate that users are adept at discerning
when out-of-turn interaction is necessary in a particular task, and actively
interleaved it with browsing. However, users found cascading information across
information-finding subtasks challenging. Therefore, this work not only
improves our understanding of out-of-turn interaction, but also suggests
further opportunities to enrich browsing experiences for users.


title: An Exploratory Study of Mobile Computing Use by Knowledge Workers

abstract:
  This paper describes some preliminary results from a 20-week study on the use
of Compaq iPAQ Personal Digital Assistants (PDAs) by 10 senior developers,
analysts, technical managers, and senior organisational managers. The goal of
the study was to identify what applications were used, how and where they were
used, the problems and issues that arose, and how use of the iPAQs changed over
the study period. The paper highlights some interesting uses of the iPAQs, and
identifies some of the characteristics of successful mobile applications.


title: Mapping Subsets of Scholarly Information

abstract:
  We illustrate the use of machine learning techniques to analyze, structure,
maintain, and evolve a large online corpus of academic literature. An emerging
field of research can be identified as part of an existing corpus, permitting
the implementation of a more coherent community structure for its
practitioners.


title: Verification of recursive parallel systems

abstract:
  In this paper we consider the problem of proving properties of infinite
behaviour of formalisms suitable to describe (infinite state) systems with
recursion and parallelism. As a formal setting, we consider the framework of
Process Rewriting Systems (PRSs). For a meaningfull fragment of PRSs, allowing
to accommodate both Pushdown Automata and Petri Nets, we state decidability
results for a class of properties about infinite derivations (infinite term
rewritings). The given results can be exploited for the automatic verification
of some classes of linear time properties of infinite state systems described
by PRSs. In order to exemplify the assessed results, we introduce a meaningful
automaton based formalism which allows to express both recursion and
multi--treading.


title: Modeling Object Oriented Constraint Programs in Z

abstract:
  Object oriented constraint programs (OOCPs) emerge as a leading evolution of
constraint programming and artificial intelligence, first applied to a range of
industrial applications called configuration problems. The rich variety of
technical approaches to solving configuration problems (CLP(FD), CC(FD), DCSP,
Terminological systems, constraint programs with set variables ...) is a source
of difficulty. No universally accepted formal language exists for communicating
about OOCPs, which makes the comparison of systems difficult. We present here a
Z based specification of OOCPs which avoids the falltrap of hidden object
semantics. The object system is part of the specification, and captures all of
the most advanced notions from the object oriented modeling standard UML. The
paper illustrates these issues and the conciseness and precision of Z by the
specification of a working OOCP that solves an historical AI problem : parsing
a context free grammar. Being written in Z, an OOCP specification also supports
formal proofs. The whole builds the foundation of an adaptative and evolving
framework for communicating about constrained object models and programs.


title: ICT-based planning and the missing educational link

abstract:
  The past century ended with an unexpected explosion of Information and
Communication Technologies (ICT), both in planning/managing public policies,
and in exchanging knowledge. However, the extent to which ICT-based tools
increase the level of public knowledge, or help decision makers is still
uncertain. Although indirectly, the overload of unfiltered Web-based
information seems able to hamper the knowledge growth of people, particularly
in some developing communities, whereas Decision Support Systems (DSS) and
Geographical Information Systems (GIS) prove to be ineffective if managed by
unskilled planning bodies. Given such warns, this paper outlines how the
different social and cultural awareness of local communities can affect the
outcomes of ICT-based tools. It further explores the impacts of ICT-based tools
on community development and spatial planning, emphasizing the role of proper
literacy and education for effective management.


title:
GridEmail: A Case for Economically Regulated Internet-based
  Interpersonal Communications

abstract:
  Email has emerged as a dominant form of electronic communication between
people. Spam is a major problem for email users, with estimates of up to 56% of
email falling into that category. Control of Spam is being attempted with
technical and legislative methods. In this paper we look at email and spam from
a supply-demand perspective. We propose Gridemail, an email system based on an
economy of communicating parties, where participants? motivations are
represented as pricing policies and profiles. This system is expected to help
people regulate their personal communications to suit their conditions, and
help in removing unwanted messages.


title:
Inferring Termination Conditions for Logic Programs using Backwards
  Analysis

abstract:
  This paper focuses on the inference of modes for which a logic program is
guaranteed to terminate. This generalises traditional termination analysis
where an analyser tries to verify termination for a specified mode. Our
contribution is a methodology in which components of traditional termination
analysis are combined with backwards analysis to obtain an analyser for
termination inference. We identify a condition on the components of the
analyser which guarantees that termination inference will infer all modes which
can be checked to terminate. The application of this methodology to enhance a
traditional termination analyser to perform also termination inference is
demonstrated.


title: Evolution: Google vs. DRIS

abstract:
  This paper gives an absolute new search system that builds the information
retrieval infrastructure for Internet. Now most search engine companies are
mainly concerned with how to make profit from company users by advertisement
and ranking prominence, but never consider what its real customers will feel.
Few web search engines can sell billions dollars just at the cost of
inconvenience of most Internet users, but not its high quality of search
service. When we have to bear the bothersome advertisements in the awful
results and have no choices, Internet as the kind of public good will surely be
undermined. If current Internet can't fully ensure our right to know, it may
need some sound improvements or a revolution.


title: Soft Constraint Programming to Analysing Security Protocols

abstract:
  Security protocols stipulate how the remote principals of a computer network
should interact in order to obtain specific security goals. The crucial goals
of confidentiality and authentication may be achieved in various forms, each of
different strength. Using soft (rather than crisp) constraints, we develop a
uniform formal notion for the two goals. They are no longer formalised as mere
yes/no properties as in the existing literature, but gain an extra parameter,
the security level. For example, different messages can enjoy different levels
of confidentiality, or a principal can achieve different levels of
authentication with different principals.
  The goals are formalised within a general framework for protocol analysis
that is amenable to mechanisation by model checking. Following the application
of the framework to analysing the asymmetric Needham-Schroeder protocol, we
have recently discovered a new attack on that protocol as a form of retaliation
by principals who have been attacked previously. Having commented on that
attack, we then demonstrate the framework on a bigger, largely deployed
protocol consisting of three phases, Kerberos.


title: Speedup of Logic Programs by Binarization and Partial Deduction

abstract:
  Binary logic programs can be obtained from ordinary logic programs by a
binarizing transformation. In most cases, binary programs obtained this way are
less efficient than the original programs. (Demoen, 1992) showed an interesting
example of a logic program whose computational behaviour was improved when it
was transformed to a binary program and then specialized by partial deduction.
The class of B-stratifiable logic programs is defined. It is shown that for
every B-stratifiable logic program, binarization and subsequent partial
deduction produce a binary program which does not contain variables for
continuations introduced by binarization. Such programs usually have a better
computational behaviour than the original ones. Both binarization and partial
deduction can be easily automated. A comparison with other related approaches
to program transformation is given.


title: An Open Ended Tree

abstract:
  An open ended list is a well known data structure in Prolog programs. It is
frequently used to represent a value changing over time, while this value is
referred to from several places in the data structure of the application. A
weak point in this technique is that the time complexity is linear in the
number of updates to the value represented by the open ended list. In this
programming pearl we present a variant of the open ended list, namely an open
ended tree, with an update and access time complexity logarithmic in the number
of updates to the value.


title:
Minimal founded semantics for disjunctive logic programs and deductive
  databases

abstract:
  In this paper, we propose a variant of stable model semantics for disjunctive
logic programming and deductive databases. The semantics, called minimal
founded, generalizes stable model semantics for normal (i.e. non disjunctive)
programs but differs from disjunctive stable model semantics (the extension of
stable model semantics for disjunctive programs). Compared with disjunctive
stable model semantics, minimal founded semantics seems to be more intuitive,
it gives meaning to programs which are meaningless under stable model semantics
and is no harder to compute. More specifically, minimal founded semantics
differs from stable model semantics only for disjunctive programs having
constraint rules or rules working as constraints. We study the expressive power
of the semantics and show that for general disjunctive datalog programs it has
the same power as disjunctive stable model semantics.


title: Strong Equivalence Made Easy: Nested Expressions and Weight Constraints

abstract:
  Logic programs P and Q are strongly equivalent if, given any program R,
programs P union R and Q union R are equivalent (that is, have the same answer
sets). Strong equivalence is convenient for the study of equivalent
transformations of logic programs: one can prove that a local change is correct
without considering the whole program. Lifschitz, Pearce and Valverde showed
that Heyting's logic of here-and-there can be used to characterize strong
equivalence for logic programs with nested expressions (which subsume the
better-known extended disjunctive programs). This note considers a simpler,
more direct characterization of strong equivalence for such programs, and shows
that it can also be applied without modification to the weight constraint
programs of Niemela and Simons. Thus, this characterization of strong
equivalence is convenient for the study of equivalent transformations of logic
programs written in the input languages of answer set programming systems dlv
and smodels. The note concludes with a brief discussion of results that can be
used to automate reasoning about strong equivalence, including a novel encoding
that reduces the problem of deciding the strong equivalence of a pair of weight
constraint programs to that of deciding the inconsistency of a weight
constraint program.


title:
CSIEC (Computer Simulator in Educational Communication): An Intelligent
  Web-Based Teaching System for Foreign Language Learning

abstract:
  In this paper we present an innovative intelligent web-based computer-aided
instruction system for foreign language learning: CSIEC (Computer Simulator in
Educational Communication). This system can not only grammatically understand
the sentences in English given from the users via Internet, but also reasonably
and individually speak with the users. At first the related works in this
research field are analyzed. Then we introduce the system goals and the system
framework, i.e., the natural language understanding mechanism (NLML, NLOMJ and
NLDB) and the communicational response (CR). Finally we give the syntactic and
semantic content of this instruction system, i.e. some important notations of
English grammar used in it and their relations with the NLOMJ.


title: Distributed WWW Programming using (Ciao-)Prolog and the PiLLoW library

abstract:
  We discuss from a practical point of view a number of issues involved in
writing distributed Internet and WWW applications using LP/CLP systems. We
describe PiLLoW, a public-domain Internet and WWW programming library for
LP/CLP systems that we have designed in order to simplify the process of
writing such applications. PiLLoW provides facilities for accessing documents
and code on the WWW; parsing, manipulating and generating HTML and XML
structured documents and data; producing HTML forms; writing form handlers and
CGI-scripts; and processing HTML/XML templates. An important contribution of
PiLLoW is to model HTML/XML code (and, thus, the content of WWW pages) as
terms. The PiLLoW library has been developed in the context of the Ciao Prolog
system, but it has been adapted to a number of popular LP/CLP systems,
supporting most of its functionality. We also describe the use of concurrency
and a high-level model of client-server interaction, Ciao Prolog's active
modules, in the context of WWW programming. We propose a solution for
client-side downloading and execution of Prolog code, using generic browsers.
Finally, we also provide an overview of related work on the topic.


title: Learning in a Compiler for MINSAT Algorithms

abstract:
  This paper describes learning in a compiler for algorithms solving classes of
the logic minimization problem MINSAT, where the underlying propositional
formula is in conjunctive normal form (CNF) and where costs are associated with
the True/False values of the variables. Each class consists of all instances
that may be derived from a given propositional formula and costs for True/False
values by fixing or deleting variables, and by deleting clauses. The learning
step begins once the compiler has constructed a solution algorithm for a given
class. The step applies that algorithm to comparatively few instances of the
class, analyses the performance of the algorithm on these instances, and
modifies the underlying propositional formula, with the goal that the algorithm
will perform much better on all instances of the class.


title: Using sensors in the web crawling process

abstract:
  This paper offers a short description of an Internet information field
monitoring system, which places a special module-sensor on the side of the
Web-server to detect changes in information resources and subsequently
reindexes only the resources signalized by the corresponding sensor. Concise
results of simulation research and an implementation attempt of the given
"sensors" concept are provided.


title: Sharing secret color images using cellular automata with memory

abstract:
  A {k,n}-threshold scheme based on two-dimensional memory cellular automata is
proposed to share images in a secret way. This method allows to encode an image
into n shared images so that only qualified subsets of k or more shares can
recover the secret image, but any k-1 or fewer of them gain no information
about the original image. The main characteristics of this new scheme are: each
shared image has the same size that the original one, and the recovered image
is exactly the same than the secret image; i.e., there is no loss of
resolution.


title:
Analysis of Implementation Hierocrypt-3 algorithm (and its comparison to
  Camellia algorithm) using ALTERA devices

abstract:
  Alghoritms: HIEROCRYPT-3, CAMELLIA and ANUBIS, GRAND CRU, NOEKEON, NUSH, Q,
RC6, SAFER++128, SC2000, SHACAL were requested for the submission of block
ciphers (high level block cipher) to NESSIE (New European Schemes for
Signatures, Integrity, and Encryption) project. The main purpose of this
project was to put forward a portfolio of strong cryptographic primitives of
various types. The NESSIE project was a three year long project and has been
divided into two phases. The first was finished in June 2001r. CAMELLIA, RC6,
SAFER++128 and SHACAL were accepted for the second phase of the evaluation
process. HIEROCRYPT-3 had key schedule problems, and there were attacks for up
to 3,5 rounds out of 6, at least hardware implementations of this cipher were
extremely slow [12]. HIEROCRYPT-3 was not selected to Phase II. CAMELLIA was
selected as an algorithm suggested for future standard. In the paper we present
the hardware implementations these two algorithms with 128-bit blocks and
128-bit keys, using ALTERA devices and their comparisons.


title: What Causes a System to Satisfy a Specification?

abstract:
  Even when a system is proven to be correct with respect to a specification,
there is still a question of how complete the specification is, and whether it
really covers all the behaviors of the system. Coverage metrics attempt to
check which parts of a system are actually relevant for the verification
process to succeed. Recent work on coverage in model checking suggests several
coverage metrics and algorithms for finding parts of the system that are not
covered by the specification. The work has already proven to be effective in
practice, detecting design errors that escape early verification efforts in
industrial settings. In this paper, we relate a formal definition of causality
given by Halpern and Pearl [2001] to coverage. We show that it gives
significant insight into unresolved issues regarding the definition of coverage
and leads to potentially useful extensions of coverage. In particular, we
introduce the notion of responsibility, which assigns to components of a system
a quantitative measure of their relevance to the satisfaction of the
specification.


title:
Characterizing and Reasoning about Probabilistic and Non-Probabilistic
  Expectation

abstract:
  Expectation is a central notion in probability theory. The notion of
expectation also makes sense for other notions of uncertainty. We introduce a
propositional logic for reasoning about expectation, where the semantics
depends on the underlying representation of uncertainty. We give sound and
complete axiomatizations for the logic in the case that the underlying
representation is (a) probability, (b) sets of probability measures, (c) belief
functions, and (d) possibility measures. We show that this logic is more
expressive than the corresponding logic for reasoning about likelihood in the
case of sets of probability measures, but equi-expressive in the case of
probability, belief, and possibility. Finally, we show that satisfiability for
these logics is NP-complete, no harder than satisfiability for propositional
logic.


title: Responsibility and blame: a structural-model approach

abstract:
  Causality is typically treated an all-or-nothing concept; either A is a cause
of B or it is not. We extend the definition of causality introduced by Halpern
and Pearl [2001] to take into account the degree of responsibility of A for B.
For example, if someone wins an election 11--0, then each person who votes for
him is less responsible for the victory than if he had won 6--5. We then define
a notion of degree of blame, which takes into account an agent's epistemic
state. Roughly speaking, the degree of blame of A for B is the expected degree
of responsibility of A for B, taken over the epistemic state of an agent.


title: Uniform test of algorithmic randomness over a general space

abstract:
  The algorithmic theory of randomness is well developed when the underlying
space is the set of finite or infinite sequences and the underlying probability
distribution is the uniform distribution or a computable distribution. These
restrictions seem artificial. Some progress has been made to extend the theory
to arbitrary Bernoulli distributions (by Martin-Loef), and to arbitrary
distributions (by Levin). We recall the main ideas and problems of Levin's
theory, and report further progress in the same framework.
  - We allow non-compact spaces (like the space of continuous functions,
underlying the Brownian motion).
  - The uniform test (deficiency of randomness) d_P(x) (depending both on the
outcome x and the measure P should be defined in a general and natural way.
  - We see which of the old results survive: existence of universal tests,
conservation of randomness, expression of tests in terms of description
complexity, existence of a universal measure, expression of mutual information
as "deficiency of independence.
  - The negative of the new randomness test is shown to be a generalization of
complexity in continuous spaces; we show that the addition theorem survives.
  The paper's main contribution is introducing an appropriate framework for
studying these questions and related ones (like statistics for a general family
of distributions).


title: Diagnostic reasoning with A-Prolog

abstract:
  In this paper we suggest an architecture for a software agent which operates
a physical device and is capable of making observations and of testing and
repairing the device's components. We present simplified definitions of the
notions of symptom, candidate diagnosis, and diagnosis which are based on the
theory of action language ${\cal AL}$. The definitions allow one to give a
simple account of the agent's behavior in which many of the agent's tasks are
reduced to computing stable models of logic programs.


title: Greedy Algorithms in Datalog

abstract:
  In the design of algorithms, the greedy paradigm provides a powerful tool for
solving efficiently classical computational problems, within the framework of
procedural languages. However, expressing these algorithms within the
declarative framework of logic-based languages has proven a difficult research
challenge. In this paper, we extend the framework of Datalog-like languages to
obtain simple declarative formulations for such problems, and propose effective
implementation techniques to ensure computational complexities comparable to
those of procedural formulations. These advances are achieved through the use
of the "choice" construct, extended with preference annotations to effect the
selection of alternative stable-models and nondeterministic fixpoints. We show
that, with suitable storage structures, the differential fixpoint computation
of our programs matches the complexity of procedural algorithms in classical
search and optimization problems.


title: Declarative Semantics for Active Rules

abstract:
  In this paper we analyze declarative deterministic and non-deterministic
semantics for active rules. In particular we consider several (partial) stable
model semantics, previously defined for deductive rules, such as well-founded,
max deterministic, unique total stable model, total stable model, and maximal
stable model semantics. The semantics of an active program AP is given by first
rewriting it into a deductive program P, then computing a model M defining the
declarative semantics of P and, finally, applying `consistent' updates
contained in M to the source database. The framework we propose permits a
natural integration of deductive and active rules and can also be applied to
queries with function symbols or to queries over infinite databases.


title: On A Theory of Probabilistic Deductive Databases

abstract:
  We propose a framework for modeling uncertainty where both belief and doubt
can be given independent, first-class status. We adopt probability theory as
the mathematical formalism for manipulating uncertainty. An agent can express
the uncertainty in her knowledge about a piece of information in the form of a
confidence level, consisting of a pair of intervals of probability, one for
each of her belief and doubt. The space of confidence levels naturally leads to
the notion of a trilattice, similar in spirit to Fitting's bilattices.
Intuitively, thep oints in such a trilattice can be ordered according to truth,
information, or precision. We develop a framework for probabilistic deductive
databases by associating confidence levels with the facts and rules of a
classical deductive database. While the trilattice structure offers a variety
of choices for defining the semantics of probabilistic deductive databases, our
choice of semantics is based on the truth-ordering, which we find to be closest
to the classical framework for deductive databases. In addition to proposing a
declarative semantics based on valuations and an equivalent semantics based on
fixpoint theory, we also propose a proof procedure and prove it sound and
complete. We show that while classical Datalog query programs have a polynomial
time data complexity, certain query programs in the probabilistic deductive
database framework do not even terminate on some input databases. We identify a
large natural class of query programs of practical interest in our framework,
and show that programs in this class possess polynomial time data complexity,
i.e., not only do they terminate on every input database, they are guaranteed
to do so in a number of steps polynomial in the input database size.


title: Clustering by compression

abstract:
  We present a new method for clustering based on compression. The method
doesn't use subject-specific features or background knowledge, and works as
follows: First, we determine a universal similarity distance, the normalized
compression distance or NCD, computed from the lengths of compressed data files
(singly and in pairwise concatenation). Second, we apply a hierarchical
clustering method. The NCD is universal in that it is not restricted to a
specific application area, and works across application area boundaries. A
theoretical precursor, the normalized information distance, co-developed by one
of the authors, is provably optimal but uses the non-computable notion of
Kolmogorov complexity. We propose precise notions of similarity metric, normal
compressor, and show that the NCD based on a normal compressor is a similarity
metric that approximates universality. To extract a hierarchy of clusters from
the distance matrix, we determine a dendrogram (binary tree) by a new quartet
method and a fast heuristic to implement it. The method is implemented and
available as public software, and is robust under choice of different
compressors. To substantiate our claims of universality and robustness, we
report evidence of successful application in areas as diverse as genomics,
virology, languages, literature, music, handwritten digits, astronomy, and
combinations of objects from completely different domains, using statistical,
dictionary, and block sorting compressors. In genomics we presented new
evidence for major questions in Mammalian evolution, based on
whole-mitochondrial genomic analysis: the Eutherian orders and the Marsupionta
hypothesis against the Theria hypothesis.

categories: cs.CV cond-mat.stat-mech cs.AI physics.data-an q-bio.GN q-bio.QM


title: Weight Constraints as Nested Expressions

abstract:
  We compare two recent extensions of the answer set (stable model) semantics
of logic programs. One of them, due to Lifschitz, Tang and Turner, allows the
bodies and heads of rules to contain nested expressions. The other, due to
Niemela and Simons, uses weight constraints. We show that there is a simple,
modular translation from the language of weight constraints into the language
of nested expressions that preserves the program's answer sets. Nested
expressions can be eliminated from the result of this translation in favor of
additional atoms. The translation makes it possible to compute answer sets for
some programs with weight constraints using satisfiability solvers, and to
prove the strong equivalence of programs with weight constraints using the
logic of here-and there.


title:
On the Abductive or Deductive Nature of Database Schema Validation and
  Update Processing Problems

abstract:
  We show that database schema validation and update processing problems such
as view updating, materialized view maintenance, integrity constraint checking,
integrity constraint maintenance or condition monitoring can be classified as
problems of either abductive or deductive nature, according to the reasoning
paradigm that inherently suites them. This is done by performing abductive and
deductive reasoning on the event rules [Oli91], a set of rules that define the
difference between consecutive database states In this way, we show that it is
possible to provide methods able to deal with all these problems as a whole. We
also show how some existing general deductive and abductive procedures may be
used to reason on the event rules. In this way, we show that these procedures
can deal with all database schema validation and update processing problems
considered in this paper.


title: Mapping weblog communities

abstract:
  Websites of a particular class form increasingly complex networks, and new
tools are needed to map and understand them. A way of visualizing this complex
network is by mapping it. A map highlights which members of the community have
similar interests, and reveals the underlying social network. In this paper, we
will map a network of websites using Kohonen's self-organizing map (SOM), a
neural-net like method generally used for clustering and visualization of
complex data sets. The set of websites considered has been the Blogalia weblog
hosting site (based at http://www.blogalia.com/), a thriving community of
around 200 members, created in January 2002. In this paper we show how SOM
discovers interesting community features, its relation with other
community-discovering algorithms, and the way it highlights the set of
communities formed over the network.


title: Representation Dependence in Probabilistic Inference

abstract:
  Non-deductive reasoning systems are often {\em representation dependent}:
representing the same situation in two different ways may cause such a system
to return two different answers. Some have viewed this as a significant
problem. For example, the principle of maximum entropy has been subjected to
much criticism due to its representation dependence. There has, however, been
almost no work investigating representation dependence. In this paper, we
formalize this notion and show that it is not a problem specific to maximum
entropy. In fact, we show that any representation-independent probabilistic
inference procedure that ignores irrelevant information is essentially
entailment, in a precise sense. Moreover, we show that representation
independence is incompatible with even a weak default assumption of
independence. We then show that invariance under a restricted class of
representation changes can form a reasonable compromise between representation
independence and other desiderata, and provide a construction of a family of
inference procedures that provides such restricted representation independence,
using relative entropy.


title: Using virtual processors for SPMD parallel programs

abstract:
  In this paper I describe some results on the use of virtual processors
technology for parallelize some SPMD computational programs. The tested
technology is the INTEL Hyper Threading on real processors, and the programs
are MATLAB scripts for floating points computation. The conclusions of the work
concern on the utility and limits of the used approach. The main result is that
using virtual processors is a good technique for improving parallel programs
not only for memory-based computations, but in the case of massive disk-storage
operations too.


title: A Flexible Pragmatics-driven Language Generator for Animated Agents

abstract:
  This paper describes the NECA MNLG; a fully implemented Multimodal Natural
Language Generation module. The MNLG is deployed as part of the NECA system
which generates dialogues between animated agents. The generation module
supports the seamless integration of full grammar rules, templates and canned
text. The generator takes input which allows for the specification of
syntactic, semantic and pragmatic constraints on the output.


title:
Towards Automated Generation of Scripted Dialogue: Some Time-Honoured
  Strategies

abstract:
  The main aim of this paper is to introduce automated generation of scripted
dialogue as a worthwhile topic of investigation. In particular the fact that
scripted dialogue involves two layers of communication, i.e., uni-directional
communication between the author and the audience of a scripted dialogue and
bi-directional pretended communication between the characters featuring in the
dialogue, is argued to raise some interesting issues. Our hope is that the
combined study of the two layers will forge links between research in text
generation and dialogue processing. The paper presents a first attempt at
creating such links by studying three types of strategies for the automated
generation of scripted dialogue. The strategies are derived from examples of
human-authored and naturally occurring dialogue.


title:
Dialogue as Discourse: Controlling Global Properties of Scripted
  Dialogue

abstract:
  This paper explains why scripted dialogue shares some crucial properties with
discourse. In particular, when scripted dialogues are generated by a Natural
Language Generation system, the generator can apply revision strategies that
cannot normally be used when the dialogue results from an interaction between
autonomous agents (i.e., when the dialogue is not scripted). The paper explains
that the relevant revision operators are best applied at the level of a
dialogue plan and discusses how the generator may decide when to apply a given
revision operator.


title: On the Expressibility of Stable Logic Programming

abstract:
  (We apologize for pidgin LaTeX) Schlipf \cite{sch91} proved that Stable Logic
Programming (SLP) solves all $\mathit{NP}$ decision problems. We extend
Schlipf's result to prove that SLP solves all search problems in the class
$\mathit{NP}$. Moreover, we do this in a uniform way as defined in \cite{mt99}.
Specifically, we show that there is a single $\mathrm{DATALOG}^{\neg}$ program
$P_{\mathit{Trg}}$ such that given any Turing machine $M$, any polynomial $p$
with non-negative integer coefficients and any input $\sigma$ of size $n$ over
a fixed alphabet $\Sigma$, there is an extensional database
$\mathit{edb}_{M,p,\sigma}$ such that there is a one-to-one correspondence
between the stable models of $\mathit{edb}_{M,p,\sigma} \cup P_{\mathit{Trg}}$
and the accepting computations of the machine $M$ that reach the final state in
at most $p(n)$ steps. Moreover, $\mathit{edb}_{M,p,\sigma}$ can be computed in
polynomial time from $p$, $\sigma$ and the description of $M$ and the decoding
of such accepting computations from its corresponding stable model of
$\mathit{edb}_{M,p,\sigma} \cup P_{\mathit{Trg}}$ can be computed in linear
time. A similar statement holds for Default Logic with respect to
$\Sigma_2^\mathrm{P}$-search problems\footnote{The proof of this result
involves additional technical complications and will be a subject of another
publication.}.


title: Partitioning schemes for quicksort and quickselect

abstract:
  We introduce several modifications of the partitioning schemes used in
Hoare's quicksort and quickselect algorithms, including ternary schemes which
identify keys less or greater than the pivot. We give estimates for the numbers
of swaps made by each scheme. Our computational experiments indicate that
ternary schemes allow quickselect to identify all keys equal to the selected
key at little additional cost.


title: Randomized selection with quintary partitions

abstract:
  We show that several versions of Floyd and Rivest's algorithm Select for
finding the $k$th smallest of $n$ elements require at most
$n+\min\{k,n-k\}+o(n)$ comparisons on average and with high probability. This
rectifies the analysis of Floyd and Rivest, and extends it to the case of
nondistinct elements. Our computational results confirm that Select may be the
best algorithm in practice.


title: The Geometric Thickness of Low Degree Graphs

abstract:
  We prove that the geometric thickness of graphs whose maximum degree is no
more than four is two. All of our algorithms run in O(n) time, where n is the
number of vertices in the graph. In our proofs, we present an embedding
algorithm for graphs with maximum degree three that uses an n x n grid and a
more complex algorithm for embedding a graph with maximum degree four. We also
show a variation using orthogonal edges for maximum degree four graphs that
also uses an n x n grid. The results have implications in graph theory, graph
drawing, and VLSI design.


title: Abduction in Well-Founded Semantics and Generalized Stable Models

abstract:
  Abductive logic programming offers a formalism to declaratively express and
solve problems in areas such as diagnosis, planning, belief revision and
hypothetical reasoning. Tabled logic programming offers a computational
mechanism that provides a level of declarativity superior to that of Prolog,
and which has supported successful applications in fields such as parsing,
program analysis, and model checking. In this paper we show how to use tabled
logic programming to evaluate queries to abductive frameworks with integrity
constraints when these frameworks contain both default and explicit negation.
The result is the ability to compute abduction over well-founded semantics with
explicit negation and answer sets. Our approach consists of a transformation
and an evaluation method. The transformation adjoins to each objective literal
$O$ in a program, an objective literal $not(O)$ along with rules that ensure
that $not(O)$ will be true if and only if $O$ is false. We call the resulting
program a {\em dual} program. The evaluation method, \wfsmeth, then operates on
the dual program. \wfsmeth{} is sound and complete for evaluating queries to
abductive frameworks whose entailment method is based on either the
well-founded semantics with explicit negation, or on answer sets. Further,
\wfsmeth{} is asymptotically as efficient as any known method for either class
of problems. In addition, when abduction is not desired, \wfsmeth{} operating
on a dual program provides a novel tabling method for evaluating queries to
ground extended programs whose complexity and termination properties are
similar to those of the best tabling methods for the well-founded semantics. A
publicly available meta-interpreter has been developed for \wfsmeth{} using the
XSB system.


title: Acquiring Lexical Paraphrases from a Single Corpus

abstract:
  This paper studies the potential of identifying lexical paraphrases within a
single corpus, focusing on the extraction of verb paraphrases. Most previous
approaches detect individual paraphrase instances within a pair (or set) of
comparable corpora, each of them containing roughly the same information, and
rely on the substantial level of correspondence of such corpora. We present a
novel method that successfully detects isolated paraphrase instances within a
single corpus without relying on any a-priori structure and information. A
comparison suggests that an instance-based approach may be combined with a
vector based approach in order to assess better the paraphrase likelihood for
many verb pairs.


title:
Polyhierarchical Classifications Induced by Criteria Polyhierarchies,
  and Taxonomy Algebra

abstract:
  A new approach to the construction of general persistent polyhierarchical
classifications is proposed. It is based on implicit description of category
polyhierarchy by a generating polyhierarchy of classification criteria.
Similarly to existing approaches, the classification categories are defined by
logical functions encoded by attributive expressions. However, the generating
hierarchy explicitly predefines domains of criteria applicability, and the
semantics of relations between categories is invariant to changes in the
universe composition, extending variety of criteria, and increasing their
cardinalities. The generating polyhierarchy is an independent, compact,
portable, and re-usable information structure serving as a template
classification. It can be associated with one or more particular sets of
objects, included in more general classifications as a standard component, or
used as a prototype for more comprehensive classifications. The approach
dramatically simplifies development and unplanned modifications of persistent
hierarchical classifications compared with tree, DAG, and faceted schemes. It
can be efficiently implemented in common DBMS, while considerably reducing
amount of computer resources required for storage, maintenance, and use of
complex polyhierarchies.


title: Part-of-Speech Tagging with Minimal Lexicalization

abstract:
  We use a Dynamic Bayesian Network to represent compactly a variety of
sublexical and contextual features relevant to Part-of-Speech (PoS) tagging.
The outcome is a flexible tagger (LegoTag) with state-of-the-art performance
(3.6% error on a benchmark corpus). We explore the effect of eliminating
redundancy and radically reducing the size of feature vocabularies. We find
that a small but linguistically motivated set of suffixes results in improved
cross-corpora generalization. We also show that a minimal lexicon limited to
function words is sufficient to ensure reasonable performance.


title:
Initial Experiences Re-Exporting Duplicate and Similarity Computation
  with an OAI-PMH aggregator

abstract:
  The proliferation of the Open Archive Initiative Protocol for Metadata
Harvesting (OAI-PMH) has resulted in the creation of a large number of service
providers, all harvesting from either data providers or aggregators. If data
were available regarding the similarity of metadata records, service providers
could track redundant records across harvests from multiple sources as well as
provide additional end-user services. Due to the large number of metadata
formats and the diverse mapping strategies employed by data providers,
similarity calculation requirements necessitate the use of information
retrieval strategies. We describe an OAI-PMH aggregator implementation that
uses the optional ``<about>'' container to re-export the results of similarity
calculations. Metadata records (3751) were harvested from a NASA data provider
and similarities for the records were computed. The results were useful for
detecting duplicates, similarities and metadata errors.


title: A Comparison of Cryptography Courses

abstract:
  The author taught two courses on cryptography, one at Duke University aimed
at non-mathematics majors and one at Rose-Hulman Institute of Technology aimed
at mathematics and computer science majors. Both tried to incorporate technical
and societal aspects of cryptography, with varying emphases. This paper will
discuss the strengths and weaknesses of both courses and compare the
differences in the author's approach.


title: Randomized selection with tripartitioning

abstract:
  We show that several versions of Floyd and Rivest's algorithm Select [Comm.\
ACM {\bf 18} (1975) 173] for finding the $k$th smallest of $n$ elements require
at most $n+\min\{k,n-k\}+o(n)$ comparisons on average, even when equal elements
occur. This parallels our recent analysis of another variant due to Floyd and
Rivest [Comm. ACM {\bf 18} (1975) 165--172]. Our computational results suggest
that both variants perform well in practice, and may compete with other
selection methods, such as Hoare's Find or quickselect with median-of-3 pivots.