title: Analysis of Polymorphically Typed Logic Programs Using ACI-Unification

abstract:
  Analysis of (partial) groundness is an important application of abstract
interpretation. There are several proposals for improving the precision of such
an analysis by exploiting type information, icluding our own work with Hill and
King, where we had shown how the information present in the type declarations
of a program can be used to characterise the degree of instantiation of a term
in a precise and yet inherently finite way. This approach worked for
polymorphically typed programs as in Goedel or HAL. Here, we recast this
approach following works by Codish, Lagoon and Stuckey. To formalise which
properties of terms we want to characterise, we use labelling functions, which
are functions that extract subterms from a term along certain paths. An
abstract term collects the results of all labelling functions of a term. For
the analysis, programs are executed on abstract terms instead of the concrete
ones, and usual unification is replaced by unification modulo an equality
theory which includes the well-known ACI-theory. Thus we generalise the works
by Codish, Lagoon and Stuckey w.r.t. the type systems considered and relate the
works among each other.


title: Applying Slicing Technique to Software Architectures

abstract:
  Software architecture is receiving increasingly attention as a critical
design level for software systems. As software architecture design resources
(in the form of architectural specifications) are going to be accumulated, the
development of techniques and tools to support architectural understanding,
testing, reengineering, maintenance, and reuse will become an important issue.
This paper introduces a new form of slicing, named architectural slicing, to
aid architectural understanding and reuse. In contrast to traditional slicing,
architectural slicing is designed to operate on the architectural specification
of a software system, rather than the source code of a program. Architectural
slicing provides knowledge about the high-level structure of a software system,
rather than the low-level implementation details of a program. In order to
compute an architectural slice, we present the architecture information flow
graph which can be used to represent information flows in a software
architecture. Based on the graph, we give a two-phase algorithm to compute an
architectural slice.


title: Using Dependence Analysis to Support Software Architecture Understanding

abstract:
  Software architecture is receiving increasingly attention as a critical
design level for software systems. As software architecture design resources
(in the form of architectural descriptions) are going to be accumulated, the
development of techniques and tools to support architectural understanding,
testing, reengineering, maintaining, and reusing will become an important
issue. In this paper we introduce a new dependence analysis technique, named
architectural dependence analysis to support software architecture development.
In contrast to traditional dependence analysis, architectural dependence
analysis is designed to operate on an architectural description of a software
system, rather than the source code of a conventional program. Architectural
dependence analysis provides knowledge of dependences for the high-level
architecture of a software system, rather than the low-level implementation
details of a conventional program.


title: On Assessing the Complexity of Software Architectures

abstract:
  This paper proposes some new architectural metrics which are appropriate for
evaluating the architectural attributes of a software system. The main feature
of our approach is to assess the complexity of a software architecture by
analyzing various types of architectural dependences in the architecture.


title: Component Programming and Interoperability in Constraint Solver Design

abstract:
  Prolog was once the main host for implementing constraint solvers.
  It seems that it is no longer so. To be useful, constraint solvers have to be
integrable into industrial applications written in imperative or
object-oriented languages; to be efficient, they have to interact with other
solvers. To meet these requirements, many solvers are now implemented in the
form of extensible object-oriented libraries. Following Pfister and Szyperski,
we argue that ``objects are not enough,'' and we propose to design solvers as
component-oriented libraries. We illustrate our approach by the description of
the architecture of a prototype, and we assess its strong points and
weaknesses.


title: Joint and conditional estimation of tagging and parsing models

abstract:
  This paper compares two different ways of estimating statistical language
models. Many statistical NLP tagging and parsing models are estimated by
maximizing the (joint) likelihood of the fully-observed training data. However,
since these applications only require the conditional probability
distributions, these distributions can in principle be learnt by maximizing the
conditional likelihood of the training data. Perhaps somewhat surprisingly,
models estimated by maximizing the joint were superior to models estimated by
maximizing the conditional, even though some of the latter models intuitively
had access to ``more information''.


title: Dijkstra's Self-Stabilizing Algorithm in Unsupportive Environments

abstract:
  The first self-stabilizing algorithm [Dij73] assumed the existence of a
central daemon, that activates one processor at time to change state as a
function of its own state and the state of a neighbor. Subsequent research has
reconsidered this algorithm without the assumption of a central daemon, and
under different forms of communication, such as the model of link registers. In
all of these investigations, one common feature is the atomicity of
communication, whether by shared variables or read/write registers. This paper
weakens the atomicity assumptions for the communication model, proposing
versions of [Dij73] that tolerate various weaker forms of atomicity. First, a
solution for the case of regular registers is presented. Then the case of safe
registers is considered, with both negative and positive results presented. The
paper also presents an implementation of [Dij73] based on registers that have
probabilistically correct behavior, which requires a notion of weak
stabilization.


title:
Errata and supplements to: Orthonormal RBF Wavelet and Ridgelet-like
  Series and Transforms for High-Dimensional Problems

abstract:
  In recent years some attempts have been done to relate the RBF with wavelets
in handling high dimensional multiscale problems. To the author's knowledge,
however, the orthonormal and bi-orthogonal RBF wavelets are still missing in
the literature. By using the nonsingular general solution and singular
fundamental solution of differential operator, recently the present author,
refer. 3, made some substantial headway to derive the orthonormal RBF wavelets
series and transforms. The methodology can be generalized to create the RBF
wavelets by means of the orthogonal convolution kernel function of various
integral operators. In particular, it is stressed that the presented RBF
wavelets does not apply the tensor product to handle multivariate problems at
all.
  This note is to correct some errata in reference 3 and also to supply a few
latest advances in the study of orthornormal RBF wavelet transforms.


title: The alldifferent Constraint: A Survey

abstract:
  The constraint of difference is known to the constraint programming community
since Lauriere introduced Alice in 1978. Since then, several solving strategies
have been designed for this constraint. In this paper we give both a practical
overview and an abstract comparison of these different strategies.


title: Probabilistic top-down parsing and language modeling

abstract:
  This paper describes the functioning of a broad-coverage probabilistic
top-down parser, and its application to the problem of language modeling for
speech recognition. The paper first introduces key notions in language modeling
and probabilistic parsing, and briefly reviews some previous approaches to
using syntactic structure for language modeling. A lexicalized probabilistic
top-down parser is then presented, which performs very well, in terms of both
the accuracy of returned parses and the efficiency with which they are found,
relative to the best broad-coverage statistical parsers. A new language model
which utilizes probabilistic top-down parsing is then outlined, and empirical
results show that it improves upon previous work in test corpus perplexity.
Interpolation with a trigram model yields an exceptional improvement relative
to the improvement observed by other models, demonstrating the degree to which
the information captured by our parsing model is orthogonal to that captured by
a trigram model. A small recognition experiment also demonstrates the utility
of the model.


title: Optimization Over Zonotopes and Training Support Vector Machines

abstract:
  We make a connection between classical polytopes called zonotopes and Support
Vector Machine (SVM) classifiers. We combine this connection with the ellipsoid
method to give some new theoretical results on training SVMs. We also describe
some special properties of soft margin C-SVMs as parameter C goes to infinity.


title: HTTP Cookies: Standards, Privacy, and Politics

abstract:
  How did we get from a world where cookies were something you ate and where
"non-techies" were unaware of "Netscape cookies" to a world where cookies are a
hot-button privacy issue for many computer users? This paper will describe how
HTTP "cookies" work, and how Netscape's original specification evolved into an
IETF Proposed Standard. I will also offer a personal perspective on how what
began as a straightforward technical specification turned into a political
flashpoint when it tried to address non-technical issues such as privacy.


title: Robust Probabilistic Predictive Syntactic Processing

abstract:
  This thesis presents a broad-coverage probabilistic top-down parser, and its
application to the problem of language modeling for speech recognition. The
parser builds fully connected derivations incrementally, in a single pass from
left-to-right across the string. We argue that the parsing approach that we
have adopted is well-motivated from a psycholinguistic perspective, as a model
that captures probabilistic dependencies between lexical items, as part of the
process of building connected syntactic structures. The basic parser and
conditional probability models are presented, and empirical results are
provided for its parsing accuracy on both newspaper text and spontaneous
telephone conversations. Modifications to the probability model are presented
that lead to improved performance. A new language model which uses the output
of the parser is then defined. Perplexity and word error rate reduction are
demonstrated over trigram models, even when the trigram is trained on
significantly more data. Interpolation on a word-by-word basis with a trigram
model yields additional improvements.


title: A Logical Framework for Convergent Infinite Computations

abstract:
  Classical computations can not capture the essence of infinite computations
very well. This paper will focus on a class of infinite computations called
convergent infinite computations}. A logic for convergent infinite computations
is proposed by extending first order theories using Cauchy sequences, which has
stronger expressive power than the first order logic. A class of fixed points
characterizing the logical properties of the limits can be represented by means
of infinite-length terms defined by Cauchy sequences. We will show that the
limit of sequence of first order theories can be defined in terms of distance,
similar to the $\epsilon-N$ style definition of limits in real analysis. On the
basis of infinitary terms, a computation model for convergent infinite
computations is proposed. Finally, the interpretations of logic programs are
extended by introducing real Herbrand models of logic programs and a sufficient
condition for computing a real Herbrand model of Horn logic programs using
convergent infinite computation is given.


title:
Solving Composed First-Order Constraints from Discrete-Time Robust
  Control

abstract:
  This paper deals with a problem from discrete-time robust control which
requires the solution of constraints over the reals that contain both universal
and existential quantifiers. For solving this problem we formulate it as a
program in a (fictitious) constraint logic programming language with explicit
quantifier notation. This allows us to clarify the special structure of the
problem, and to extend an algorithm for computing approximate solution sets of
first-order constraints over the reals to exploit this structure. As a result
we can deal with inputs that are clearly out of reach for current symbolic
solvers.


title: Multi-Channel Parallel Adaptation Theory for Rule Discovery

abstract:
  In this paper, we introduce a new machine learning theory based on
multi-channel parallel adaptation for rule discovery. This theory is
distinguished from the familiar parallel-distributed adaptation theory of
neural networks in terms of channel-based convergence to the target rules. We
show how to realize this theory in a learning system named CFRule. CFRule is a
parallel weight-based model, but it departs from traditional neural computing
in that its internal knowledge is comprehensible. Furthermore, when the model
converges upon training, each channel converges to a target rule. The model
adaptation rule is derived by multi-level parallel weight optimization based on
gradient descent. Since, however, gradient descent only guarantees local
optimization, a multi-channel regression-based optimization strategy is
developed to effectively deal with this problem. Formally, we prove that the
CFRule model can explicitly and precisely encode any given rule set. Also, we
prove a property related to asynchronous parallel convergence, which is a
critical element of the multi-channel parallel adaptation theory for rule
learning. Thanks to the quantizability nature of the CFRule model, rules can be
extracted completely and soundly via a threshold-based mechanism. Finally, the
practical application of the theory is demonstrated in DNA promoter recognition
and hepatitis prognosis prediction.


title:
Generating a 3D Simulation of a Car Accident from a Written Description
  in Natural Language: the CarSim System

abstract:
  This paper describes a prototype system to visualize and animate 3D scenes
from car accident reports, written in French. The problem of generating such a
3D simulation can be divided into two subtasks: the linguistic analysis and the
virtual scene generation. As a means of communication between these two
modules, we first designed a template formalism to represent a written accident
report. The CarSim system first processes written reports, gathers relevant
information, and converts it into a formal description. Then, it creates the
corresponding 3D scene and animates the vehicles.


title: Constraint Propagation in Presence of Arrays

abstract:
  We describe the use of array expressions as constraints, which represents a
consequent generalisation of the "element" constraint. Constraint propagation
for array constraints is studied theoretically, and for a set of domain
reduction rules the local consistency they enforce, arc-consistency, is proved.
An efficient algorithm is described that encapsulates the rule set and so
inherits the capability to enforce arc-consistency from the rules.


title: Market-Based Reinforcement Learning in Partially Observable Worlds

abstract:
  Unlike traditional reinforcement learning (RL), market-based RL is in
principle applicable to worlds described by partially observable Markov
Decision Processes (POMDPs), where an agent needs to learn short-term memories
of relevant previous events in order to execute optimal actions. Most previous
work, however, has focused on reactive settings (MDPs) instead of POMDPs. Here
we reimplement a recent approach to market-based RL and for the first time
evaluate it in a toy POMDP setting.


title: Toward Natural Gesture/Speech Control of a Large Display

abstract:
  In recent years because of the advances in computer vision research, free
hand gestures have been explored as means of human-computer interaction (HCI).
Together with improved speech processing technology it is an important step
toward natural multimodal HCI. However, inclusion of non-predefined continuous
gestures into a multimodal framework is a challenging problem. In this paper,
we propose a structured approach for studying patterns of multimodal language
in the context of a 2D-display control. We consider systematic analysis of
gestures from observable kinematical primitives to their semantics as pertinent
to a linguistic structure. Proposed semantic classification of co-verbal
gestures distinguishes six categories based on their spatio-temporal deixis. We
discuss evolution of a computational framework for gesture and speech
integration which was used to develop an interactive testbed (iMAP). The
testbed enabled elicitation of adequate, non-sequential, multimodal patterns in
a narrative mode of HCI. Conducted user studies illustrate significance of
accounting for the temporal alignment of gesture and speech parts in semantic
mapping. Furthermore, co-occurrence analysis of gesture/speech production
suggests syntactic organization of gestures at the lexical level.


title: Bounds on sample size for policy evaluation in Markov environments

abstract:
  Reinforcement learning means finding the optimal course of action in
Markovian environments without knowledge of the environment's dynamics.
Stochastic optimization algorithms used in the field rely on estimates of the
value of a policy. Typically, the value of a policy is estimated from results
of simulating that very policy in the environment. This approach requires a
large amount of simulation as different points in the policy space are
considered. In this paper, we develop value estimators that utilize data
gathered when using one policy to estimate the value of using another policy,
resulting in much more data-efficient algorithms. We consider the question of
accumulating a sufficient experience and give PAC-style bounds.


title: When being Weak is Brave: Privacy in Recommender Systems

abstract:
  We explore the conflict between personalization and privacy that arises from
the existence of weak ties. A weak tie is an unexpected connection that
provides serendipitous recommendations. However, information about weak ties
could be used in conjunction with other sources of data to uncover identities
and reveal other personal information. In this article, we use a
graph-theoretic model to study the benefit and risk from weak ties.


title: Coloring k-colorable graphs using relatively small palettes

abstract:
  We obtain the following new coloring results:
  * A 3-colorable graph on $n$ vertices with maximum degree~$\Delta$ can be
colored, in polynomial time, using $O((\Delta \log\Delta)^{1/3} \cdot\log{n})$
colors. This slightly improves an $O((\Delta^{{1}/{3}}
\log^{1/2}\Delta)\cdot\log{n})$ bound given by Karger, Motwani and Sudan. More
generally, $k$-colorable graphs with maximum degree $\Delta$ can be colored, in
polynomial time, using $O((\Delta^{1-{2}/{k}}\log^{1/k}\Delta) \cdot\log{n})$
colors.
  * A 4-colorable graph on $n$ vertices can be colored, in polynomial time,
using $\Ot(n^{7/19})$ colors. This improves an $\Ot(n^{2/5})$ bound given again
by Karger, Motwani and Sudan. More generally, $k$-colorable graphs on $n$
vertices can be colored, in polynomial time, using $\Ot(n^{\alpha_k})$ colors,
where $\alpha_5=97/207$, $\alpha_6=43/79$, $\alpha_7=1391/2315$,
$\alpha_8=175/271$, ...
  The first result is obtained by a slightly more refined probabilistic
analysis of the semidefinite programming based coloring algorithm of Karger,
Motwani and Sudan. The second result is obtained by combining the coloring
algorithm of Karger, Motwani and Sudan, the combinatorial coloring algorithms
of Blum and an extension of a technique of Alon and Kahale (which is based on
the Karger, Motwani and Sudan algorithm) for finding relatively large
independent sets in graphs that are guaranteed to have very large independent
sets. The extension of the Alon and Kahale result may be of independent
interest.


title: The OLAC Metadata Set and Controlled Vocabularies

abstract:
  As language data and associated technologies proliferate and as the language
resources community rapidly expands, it has become difficult to locate and
reuse existing resources. Are there any lexical resources for such-and-such a
language? What tool can work with transcripts in this particular format? What
is a good format to use for linguistic data of this type? Questions like these
dominate many mailing lists, since web search engines are an unreliable way to
find language resources. This paper describes a new digital infrastructure for
language resource discovery, based on the Open Archives Initiative, and called
OLAC -- the Open Language Archives Community. The OLAC Metadata Set and the
associated controlled vocabularies facilitate consistent description and
focussed searching. We report progress on the metadata set and controlled
vocabularies, describing current issues and soliciting input from the language
resources community.


title: State Analysis and Aggregation Study for Multicast-based Micro Mobility

abstract:
  IP mobility addresses the problem of changing the network point-of-attachment
transparently during movement. Mobile IP is the proposed standard by IETF.
Several studies, however, have shown that Mobile IP has several drawbacks, such
as triangle routing and poor handoff performance. Multicast-based mobility has
been proposed as a promising solution to the above problems, incurring less
end-to-end delays and fast smooth handoff. Nonetheless, such architecture
suffers from multicast state scalability problems with the growth in number of
mobile nodes. This architecture also requires ubiquitous multicast deployment
and more complex security measures. To alleviate these problems, we propose an
intra-domain multicast-based mobility solution. A mobility proxy allocates a
multicast address for each mobile that moves to its domain. The mobile uses
this multicast address within a domain for micro mobility. Also, aggregation is
considered to reduce the multicast state. We conduct multicast state analysis
to study the efficiency of several aggregation techniques. We use extensive
simulation to evaluate our protocol's performance over a variety of real and
generated topologies. We take aggregation gain as metric for our evaluation.
  Our simulation results show that in general leaky aggregation obtains better
gains than perfect aggregation. Also, we notice that aggregation gain increases
with the increase in number of visiting mobile nodes and with the decrease in
number of mobility proxies within a domain.


title: Learning to Cooperate via Policy Search

abstract:
  Cooperative games are those in which both agents share the same payoff
structure. Value-based reinforcement-learning algorithms, such as variants of
Q-learning, have been applied to learning cooperative games, but they only
apply when the game state is completely observable to both agents. Policy
search methods are a reasonable alternative to value-based methods for
partially observable environments. In this paper, we provide a gradient-based
distributed policy-search method for cooperative games and compare the notion
of local optimum to that of Nash equilibrium. We demonstrate the effectiveness
of this method experimentally in a small, partially observable simulated soccer
domain.


title: Lectures on Reduce and Maple at UAM I - Mexico

abstract:
  These lectures give a brief introduction to the Computer Algebra systems
Reduce and Maple. The aim is to provide a systematic survey of most important
commands and concepts. In particular, this includes a discussion of
simplification schemes and the handling of simplification and substitution
rules (e.g., a Lie Algebra is implemented in Reduce by means of simplification
rules).
  Another emphasis is on the different implementations of tensor calculi and
the exterior calculus by Reduce and Maple and their application in Gravitation
theory and Differential Geometry.
  I held the lectures at the Universidad Autonoma Metropolitana-Iztapalapa,
Departamento de Fisica, Mexico, in November 1999.


title: On the Area of Hypercube Layouts

abstract:
  This paper precisely analyzes the wire density and required area in standard
layout styles for the hypercube. The most natural, regular layout of a
hypercube of N^2 nodes in the plane, in a N x N grid arrangement, uses
floor(2N/3)+1 horizontal wiring tracks for each row of nodes. (The number of
tracks per row can be reduced by 1 with a less regular design.) This paper also
gives a simple formula for the wire density at any cut position and a full
characterization of all places where the wire density is maximized (which does
not occur at the bisection).


title: Historical Dynamics of Lexical System as Random Walk Process

abstract:
  It is offered to consider word meanings changes in diachrony as
semicontinuous random walk with reflecting and swallowing screens. The basic
characteristics of word life cycle are defined. Verification of the model has
been realized on the data of Russian words distribution on various age periods.


title: Disjunctive Logic Programs with Inheritance

abstract:
  The paper proposes a new knowledge representation language, called DLP<,
which extends disjunctive logic programming (with strong negation) by
inheritance. The addition of inheritance enhances the knowledge modeling
features of the language providing a natural representation of default
reasoning with exceptions.
  A declarative model-theoretic semantics of DLP< is provided, which is shown
to generalize the Answer Set Semantics of disjunctive logic programs.
  The knowledge modeling features of the language are illustrated by encoding
classical nonmonotonic problems in DLP<.
  The complexity of DLP< is analyzed, proving that inheritance does not cause
any computational overhead, as reasoning in DLP< has exactly the same
complexity as reasoning in disjunctive logic programming. This is confirmed by
the existence of an efficient translation from DLP< to plain disjunctive logic
programming. Using this translation, an advanced KR system supporting the DLP<
language has been implemented on top of the DLV system and has subsequently
been integrated into DLV.


title: Integrating Prosodic and Lexical Cues for Automatic Topic Segmentation

abstract:
  We present a probabilistic model that uses both prosodic and lexical cues for
the automatic segmentation of speech into topically coherent units. We propose
two methods for combining lexical and prosodic information using hidden Markov
models and decision trees. Lexical information is obtained from a speech
recognizer, and prosodic features are extracted automatically from speech
waveforms. We evaluate our approach on the Broadcast News corpus, using the
DARPA-TDT evaluation metrics. Results show that the prosodic model alone is
competitive with word-based segmentation methods. Furthermore, we achieve a
significant reduction in error by combining the prosodic and word-based
knowledge sources.


title: Approximating the satisfiability threshold for random k-XOR-formulas

abstract:
  In this paper we study random linear systems with $k$ variables per equation
over the finite field GF(2), or equivalently $k$-XOR-CNF formulas. In a
previous paper Creignou and Daud\'e proved that the phase transition for the
consistency (satisfiability) of such systems (formulas) exhibits a sharp
threshold. Here we prove that the phase transition occurs as the number of
equations (clauses) is proportional to the number of variables. For any $k\ge
3$ we establish first estimates for the critical ratio. For $k=3$ we get 0.93
as an upper bound, 0.89 as a lower bound, whereas experiments suggest that the
critical ratio is approximately 0.92.


title: Solving Assembly Line Balancing Problems by Combining IP and CP

abstract:
  Assembly line balancing problems consist in partitioning the work necessary
to assemble a number of products among different stations of an assembly line.
We present a hybrid approach for solving such problems, which combines
constraint programming and integer programming.


title: A note on radial basis function computing

abstract:
  This note carries three purposes involving our latest advances on the radial
basis function (RBF) approach. First, we will introduce a new scheme employing
the boundary knot method (BKM) to nonlinear convection-diffusion problem. It is
stressed that the new scheme directly results in a linear BKM formulation of
nonlinear problems by using response point-dependent RBFs, which can be solved
by any linear solver. Then we only need to solve a single nonlinear algebraic
equation for desirable unknown at some inner node of interest. The numerical
results demonstrate high accuracy and efficiency of this nonlinear BKM
strategy. Second, we extend the concepts of distance function, which include
time-space and variable transformation distance functions. Finally, we
demonstrate that if the nodes are symmetrically placed, the RBF coefficient
matrices have either centrosymmetric or skew centrosymmetric structures. The
factorization features of such matrices lead to a considerable reduction in the
RBF computing effort. A simple approach is also presented to reduce the
ill-conditioning of RBF interpolation matrices in general cases.


title: Soft Scheduling

abstract:
  Classical notions of disjunctive and cumulative scheduling are studied from
the point of view of soft constraint satisfaction. Soft disjunctive scheduling
is introduced as an instance of soft CSP and preferences included in this
problem are applied to generate a lower bound based on existing discrete
capacity resource. Timetabling problems at Purdue University and Faculty of
Informatics at Masaryk University considering individual course requirements of
students demonstrate practical problems which are solved via proposed methods.
Implementation of general preference constraint solver is discussed and first
computational results for timetabling problem are presented.


title: The Representation of Legal Contracts

abstract:
  The paper outlines ongoing research on logic-based tools for the analysis and
representation of legal contracts of the kind frequently encountered in
large-scale engineering projects and complex, long-term trading agreements. We
consider both contract formation and contract performance, in each case
identifying the representational issues and the prospects for providing
automated support tools.


title: A Constraint-Driven System for Contract Assembly

abstract:
  We present an approach for modelling the structure and coarse content of
legal documents with a view to providing automated support for the drafting of
contracts and contract database retrieval. The approach is designed to be
applicable where contract drafting is based on model-form contracts or on
existing examples of a similar type. The main features of the approach are: (1)
the representation addresses the structure and the interrelationships between
the constituent parts of contracts, but not the text of the document itself;
(2) the representation of documents is separated from the mechanisms that
manipulate it; and (3) the drafting process is subject to a collection of
explicitly stated constraints that govern the structure of the documents. We
describe the representation of document instances and of 'generic documents',
which are data structures used to drive the creation of new document instances,
and we show extracts from a sample session to illustrate the features of a
prototype system implemented in MacProlog.


title: Modelling Contractual Arguments

abstract:
  One influential approach to assessing the "goodness" of arguments is offered
by the Pragma-Dialectical school (p-d) (Eemeren & Grootendorst 1992). This can
be compared with Rhetorical Structure Theory (RST) (Mann & Thompson 1988), an
approach that originates in discourse analysis. In p-d terms an argument is
good if it avoids committing a fallacy, whereas in RST terms an argument is
good if it is coherent. RST has been criticised (Snoeck Henkemans 1997) for
providing only a partially functional account of argument, and similar
criticisms have been raised in the Natural Language Generation (NLG)
community-particularly by Moore & Pollack (1992)- with regards to its account
of intentionality in text in general. Mann and Thompson themselves note that
although RST can be successfully applied to a wide range of texts from diverse
domains, it fails to characterise some types of text, most notably legal
contracts. There is ongoing research in the Artificial Intelligence and Law
community exploring the potential for providing electronic support to contract
negotiators, focusing on long-term, complex engineering agreements (see for
example Daskalopulu & Sergot 1997). This paper provides a brief introduction to
RST and illustrates its shortcomings with respect to contractual text. An
alternative approach for modelling argument structure is presented which not
only caters for contractual text, but also overcomes the aforementioned
limitations of RST.


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

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


title: Model Checking Contractual Protocols

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


title: Modelling Legal Contracts as Processes

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


title: Computational properties of environment-based disambiguation

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


title: Computational Properties of Metaquerying Problems

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


title: The Set of Equations to Evaluate Objects

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


title: L.T.Kuzin: Research Program

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


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

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


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

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


title: An object evaluator to generate flexible applications

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


title: Building the access pointers to a computation environment

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


title: Playing Games with Algorithms: Algorithmic Combinatorial Game Theory

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


title: Economic Models for Management of Resources in Grid Computing

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


title: Object-oriented solutions

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


title: One More Revolution to Make: Free Scientific Publishing

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


title: Object-oriented tools for advanced applications

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


title: Objects and their computational framework

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


title: Information Integration and Computational Logic

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


title: Event Driven Computations for Relational Query Language

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


title: Event Driven Objects

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


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

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


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

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


title: Logic, Individuals and Concepts

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


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

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


title: Hinged Kite Mirror Dissection

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


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

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


title: Solving equations in the relational algebra

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


title: Polymorphic type inference for the relational algebra

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


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

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


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

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


title: Simple and Effective Distributed Computing with a Scheduling Service

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


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

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


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

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


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

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


title: MACE 2.0 Reference Manual and Guide

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


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

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


title: A Sequential Model for Multi-Class Classification

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


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

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


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

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


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

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


title: On some optimization problems for star-free graphs

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


title: Recursively Undecidable Properties of NP

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


title: Classes of Terminating Logic Programs

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


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

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


title: Acceptability with general orderings

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


title: Inference of termination conditions for numerical loops

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


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

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


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

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


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

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


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

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


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

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


title: CHR as grammar formalism. A first report

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


title: Analysis of Network Traffic in Switched Ethernet Systems

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


title: Enhancing Constraint Propagation with Composition Operators

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


title: Lower Bounds for Zero-knowledge on the Internet

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


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

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


title: The Role of Conceptual Relations in Word Sense Disambiguation

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


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

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


title: The Risk Profile Problem for Stock Portfolio Optimization

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


title: Complex Tilings

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


title: A Blueprint for Building Serverless Applications on the Net

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


title: Algorithms for Boolean Function Query Properties

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


title: Distributed Broadcast in Wireless Networks with Unknown Topology

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


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

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


title: The Logic Programming Paradigm and Prolog

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


title: Transformations of CCP programs

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


title: From Neel to NPC: Colouring Small Worlds

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


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

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


title: Learning Computational Grammars

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


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

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


title: Applying Natural Language Generation to Indicative Summarization

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


title: Transformation-Based Learning in the Fast Lane

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


title: Multidimensional Transformation-Based Learning

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


title: An interactive semantics of logic programming

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


title: Vertex-Unfoldings of Simplicial Polyhedra

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


title: Enumerating Foldings and Unfoldings between Polygons and Polytopes

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


title: Computer validated proofs of a toolset for adaptable arithmetic

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


title: Annotated revision programs

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


title: Fixed-parameter complexity of semantics for logic programs

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