title:
Minimizing Cache Misses in Scientific Computing Using Isoperimetric
  Bodies

abstract:
  A number of known techniques for improving cache performance in scientific
computations involve the reordering of the iteration space. Some of these
reorderings can be considered coverings of the iteration space with sets having
small surface-to-volume ratios. Use of such sets may reduce the number of cache
misses in computations of local operators having the iteration space as their
domain. First, we derive lower bounds on cache misses that any algorithm must
suffer while computing a local operator on a grid. Then, we explore coverings
of iteration spaces of structured and unstructured discretization grid
operators which allow us to approach these lower bounds. For structured grids
we introduce a covering by successive minima tiles based on the interference
lattice of the grid. We show that the covering has a small surface-to-volume
ratio and present a computer experiment showing actual reduction of the cache
misses achieved by using these tiles. For planar unstructured grids we show
existence of a covering which reduces the number of cache misses to the level
of that of structured grids. Next, we introduce a class of multidimensional
grids, called starry grids in this paper. These grids represent an abstraction
of unstructured grids used in, for example, molecular simulations and the
solution of partial differential equations. We show that starry grids can be
covered by sets having a low surface-to-volume ratio and, hence have the same
cache efficiency as structured grids. Finally, we present a triangulation of a
three-dimensional cube that has the property that any local operator on the
corresponding grid must incur a significantly larger number of cache misses
than a similar operator on a structured grid of the same size.


title: Distance function wavelets - Part II: Extended results and conjectures

abstract:
  Report II is concerned with the extended results of distance function
wavelets (DFW). The fractional DFW transforms are first addressed relating to
the fractal geometry and fractional derivative, and then, the discrete
Helmholtz-Fourier transform is briefly presented. The Green second identity may
be an alternative devise in developing the theoretical framework of the DFW
transform and series. The kernel solutions of the Winkler plate equation and
the Burger's equation are used to create the DFW transforms and series. Most
interestingly, it is found that the translation invariant monomial solutions of
the high-order Laplace equations can be used to make very simple harmonic
polynomial DFW series. In most cases of this study, solid mathematical analysis
is missing and results are obtained intuitively in the conjecture status.


title: Three complete deterministic polynomial algorithms for 3SAT

abstract:
  Three algorithms are presented that determine the existence of satisfying
assignments for 3SAT Boolean satisfiability expressions. One algorithm is
presented for determining an instance of a satisfying assignment, where such
exists. The algorithms are each deterministic and of polynomial complexity. The
algorithms determining existence are complete as each produces a certificate of
non-satisfiability, for instances where no satisfying assignment exists, and of
satisfiability for such assignment does exist.


title: Bootstrapping Lexical Choice via Multiple-Sequence Alignment

abstract:
  An important component of any generation system is the mapping dictionary, a
lexicon of elementary semantic expressions and corresponding natural language
realizations. Typically, labor-intensive knowledge-based methods are used to
construct the dictionary. We instead propose to acquire it automatically via a
novel multiple-pass algorithm employing multiple-sequence alignment, a
technique commonly used in bioinformatics. Crucially, our method leverages
latent information contained in multi-parallel corpora -- datasets that supply
several verbalizations of the corresponding semantics rather than just one.
  We used our techniques to generate natural language versions of
computer-generated mathematical proofs, with good results on both a
per-component and overall-output basis. For example, in evaluations involving a
dozen human judges, our system produced output whose readability and
faithfulness to the semantic input rivaled that of a traditional generation
system.


title: Effectiveness of Preference Elicitation in Combinatorial Auctions

abstract:
  Combinatorial auctions where agents can bid on bundles of items are desirable
because they allow the agents to express complementarity and substitutability
between the items. However, expressing one's preferences can require bidding on
all bundles. Selective incremental preference elicitation by the auctioneer was
recently proposed to address this problem (Conen & Sandholm 2001), but the idea
was not evaluated. In this paper we show, experimentally and theoretically,
that automated elicitation provides a drastic benefit. In all of the
elicitation schemes under study, as the number of items for sale increases, the
amount of information elicited is a vanishing fraction of the information
collected in traditional ``direct revelation mechanisms'' where bidders reveal
all their valuation information. Most of the elicitation schemes also maintain
the benefit as the number of agents increases. We develop more effective
elicitation policies for existing query types. We also present a new query type
that takes the incremental nature of elicitation to a new level by allowing
agents to give approximate answers that are refined only on an as-needed basis.
In the process, we present methods for evaluating different types of
elicitation policies.


title:
Evaluating the Effectiveness of Ensembles of Decision Trees in
  Disambiguating Senseval Lexical Samples

abstract:
  This paper presents an evaluation of an ensemble--based system that
participated in the English and Spanish lexical sample tasks of Senseval-2. The
system combines decision trees of unigrams, bigrams, and co--occurrences into a
single classifier. The analysis is extended to include the Senseval-1 data.


title:
Assessing System Agreement and Instance Difficulty in the Lexical Sample
  Tasks of Senseval-2

abstract:
  This paper presents a comparative evaluation among the systems that
participated in the Spanish and English lexical sample tasks of Senseval-2. The
focus is on pairwise comparisons among systems to assess the degree to which
they agree, and on measuring the difficulty of the test instances included in
these tasks.


title:
Machine Learning with Lexical Features: The Duluth Approach to
  Senseval-2

abstract:
  This paper describes the sixteen Duluth entries in the Senseval-2 comparative
exercise among word sense disambiguation systems. There were eight pairs of
Duluth systems entered in the Spanish and English lexical sample tasks. These
are all based on standard machine learning algorithms that induce classifiers
from sense-tagged training text where the context in which ambiguous words
occur are represented by simple lexical features. These are highly portable,
robust methods that can serve as a foundation for more tailored approaches.


title: Thumbs up? Sentiment Classification using Machine Learning Techniques

abstract:
  We consider the problem of classifying documents not by topic, but by overall
sentiment, e.g., determining whether a review is positive or negative. Using
movie reviews as data, we find that standard machine learning techniques
definitively outperform human-produced baselines. However, the three machine
learning methods we employed (Naive Bayes, maximum entropy classification, and
support vector machines) do not perform as well on sentiment classification as
on traditional topic-based categorization. We conclude by examining factors
that make the sentiment classification problem more challenging.


title:
A Scalable Architecture for Harvest-Based Digital Libraries - The
  ODU/Southampton Experiments

abstract:
  This paper discusses the requirements of current and emerging applications
based on the Open Archives Initiative (OAI) and emphasizes the need for a
common infrastructure to support them. Inspired by HTTP proxy, cache, gateway
and web service concepts, a design for a scalable and reliable infrastructure
that aims at satisfying these requirements is presented. Moreover it is shown
how various applications can exploit the services included in the proposed
infrastructure. The paper concludes by discussing the current status of several
prototype implementations.


title: Unsupervised Learning of Morphology without Morphemes

abstract:
  The first morphological learner based upon the theory of Whole Word
Morphology Ford et al. (1997) is outlined, and preliminary evaluation results
are presented. The program, Whole Word Morphologizer, takes a POS-tagged
lexicon as input, induces morphological relationships without attempting to
discover or identify morphemes, and is then able to generate new words beyond
the learning sample. The accuracy (precision) of the generated new words is as
high as 80% using the pure Whole Word theory, and 92% after a post-hoc
adjustment is added to the routine.


title: Vote Elicitation: Complexity and Strategy-Proofness

abstract:
  Preference elicitation is a central problem in AI, and has received
significant attention in single-agent settings. It is also a key problem in
multiagent systems, but has received little attention here so far. In this
setting, the agents may have different preferences that often must be
aggregated using voting. This leads to interesting issues because what, if any,
information should be elicited from an agent depends on what other agents have
revealed about their preferences so far.
  In this paper we study effective elicitation, and its impediments, for the
most common voting protocols. It turns out that in the Single Transferable Vote
protocol, even knowing when to terminate elicitation is mathcal NP-complete,
while this is easy for all the other protocols under study. Even for these
protocols, determining how to elicit effectively is NP-complete, even with
perfect suspicions about how the agents will vote. The exception is the
Plurality protocol where such effective elicitation is easy.
  We also show that elicitation introduces additional opportunities for
strategic manipulation by the voters. We demonstrate how to curtail the space
of elicitation schemes so that no such additional strategic issues arise.


title: Complexity Results about Nash Equilibria

abstract:
  Noncooperative game theory provides a normative framework for analyzing
strategic interactions. However, for the toolbox to be operational, the
solutions it defines will have to be computed. In this paper, we provide a
single reduction that 1) demonstrates NP-hardness of determining whether Nash
equilibria with certain natural properties exist, and 2) demonstrates the
#P-hardness of counting Nash equilibria (or connected sets of Nash equilibria).
We also show that 3) determining whether a pure-strategy Bayes-Nash equilibrium
exists is NP-hard, and that 4) determining whether a pure-strategy Nash
equilibrium exists in a stochastic (Markov) game is PSPACE-hard even if the
game is invisible (this remains NP-hard if the game is finite). All of our
hardness results hold even if there are only two players and the game is
symmetric.
  Keywords: Nash equilibrium; game theory; computational complexity;
noncooperative game theory; normal form game; stochastic game; Markov game;
Bayes-Nash equilibrium; multiagent systems.


title: Complexity of Mechanism Design

abstract:
  The aggregation of conflicting preferences is a central problem in multiagent
systems. The key difficulty is that the agents may report their preferences
insincerely. Mechanism design is the art of designing the rules of the game so
that the agents are motivated to report their preferences truthfully and a
(socially) desirable outcome is chosen. We propose an approach where a
mechanism is automatically created for the preference aggregation setting at
hand. This has several advantages, but the downside is that the mechanism
design optimization problem needs to be solved anew each time. Focusing on
settings where side payments are not possible, we show that the mechanism
design problem is NP-complete for deterministic mechanisms. This holds both for
dominant-strategy implementation and for Bayes-Nash implementation. We then
show that if we allow randomized mechanisms, the mechanism design problem
becomes tractable. In other words, the coordinator can tackle the computational
complexity introduced by its uncertainty about the agents' preferences by
making the agents face additional uncertainty. This comes at no loss, and in
some cases at a gain, in the (social) objective.


title: Complexity of Manipulating Elections with Few Candidates

abstract:
  In multiagent settings where the agents have different preferences,
preference aggregation is a central issue. Voting is a general method for
preference aggregation, but seminal results have shown that all general voting
protocols are manipulable. One could try to avoid manipulation by using voting
protocols where determining a beneficial manipulation is hard. Especially among
computational agents, it is reasonable to measure this hardness by
computational complexity. Some earlier work has been done in this area, but it
was assumed that the number of voters and candidates is unbounded. We derive
hardness results for practical multiagent settings where the number of
candidates is small but the number of voters can be large. We show that with
complete information about the others' votes, individual manipulation is easy,
and coalitional manipulation is easy with unweighted voters. However,
constructive coalitional manipulation with weighted voters is intractable for
all of the voting protocols under study, except for the nonrandomized Cup.
Destructive manipulation tends to be easier. Randomizing over instantiations of
the protocols (such as schedules of the Cup protocol) can be used to make
manipulation hard. Finally, we show that under weak assumptions, if weighted
coalitional manipulation with complete information about the others' votes is
hard in some voting protocol, then individual and unweighted manipulation is
hard when there is uncertainty about the others' votes.


title: Designing Multi-Commodity Flow Trees

abstract:
  The traditional multi-commodity flow problem assumes a given flow network in
which multiple commodities are to be maximally routed in response to given
demands. This paper considers the multi-commodity flow network-design problem:
given a set of multi-commodity flow demands, find a network subject to certain
constraints such that the commodities can be maximally routed.
  This paper focuses on the case when the network is required to be a tree. The
main result is an approximation algorithm for the case when the tree is
required to be of constant degree. The algorithm reduces the problem to the
minimum-weight balanced-separator problem; the performance guarantee of the
algorithm is within a factor of 4 of the performance guarantee of the
balanced-separator procedure. If Leighton and Rao's balanced-separator
procedure is used, the performance guarantee is O(log n). This improves the
O(log^2 n) approximation factor that is trivial to obtain by a direct
application of the balanced-separator method.


title: A Spectrum of Applications of Automated Reasoning

abstract:
  The likelihood of an automated reasoning program being of substantial
assistance for a wide spectrum of applications rests with the nature of the
options and parameters it offers on which to base needed strategies and
methodologies. This article focuses on such a spectrum, featuring W. McCune's
program OTTER, discussing widely varied successes in answering open questions,
and touching on some of the strategies and methodologies that played a key
role. The applications include finding a first proof, discovering single
axioms, locating improved axiom systems, and simplifying existing proofs. The
last application is directly pertinent to the recently found (by R. Thiele)
Hilbert's twenty-fourth problem--which is extremely amenable to attack with the
appropriate automated reasoning program--a problem concerned with proof
simplification. The methodologies include those for seeking shorter proofs and
for finding proofs that avoid unwanted lemmas or classes of term, a specific
option for seeking proofs with smaller equational or formula complexity, and a
different option to address the variable richness of a proof. The type of proof
one obtains with the use of OTTER is Hilbert-style axiomatic, including details
that permit one sometimes to gain new insights. We include questions still open
and challenges that merit consideration.


title: Connectives in Quantum and other Cumulative Logics

abstract:
  Cumulative logics are studied in an abstract setting, i.e., without
connectives, very much in the spirit of Makinson's early work. A powerful
representation theorem characterizes those logics by choice functions that
satisfy a weakening of Sen's property alpha, in the spirit of the author's
"Nonmonotonic Logics and Semantics" (JLC). The representation results obtained
are surprisingly smooth: in the completeness part the choice function may be
defined on any set of worlds, not only definable sets and no
definability-preservation property is required in the soundness part. For
abstract cumulative logics, proper conjunction and negation may be defined.
Contrary to the situation studied in "Nonmonotonic Logics and Semantics" no
proper disjunction seems to be definable in general. The cumulative relations
of KLM that satisfy some weakening of the consistency preservation property all
define cumulative logics with a proper negation. Quantum Logics, as defined by
Engesser and Gabbay are such cumulative logics but the negation defined by
orthogonal complement does not provide a proper negation.


title: Transforming the World Wide Web into a Complexity-Based Semantic Network

abstract:
  The aim of this paper is to introduce the idea of the Semantic Web to the
Complexity community and set a basic ground for a project resulting in creation
of Internet-based semantic network of Complexity-related information providers.
Implementation of the Semantic Web technology would be of mutual benefit to
both the participants and users and will confirm self-referencing power of the
community to apply the products of its own research to itself. We first explain
the logic of the transition and discuss important notions associated with the
Semantic Web technology. We then present a brief outline of the project
milestones.


title: Neural Net Model for Featured Word Extraction

abstract:
  Search engines perform the task of retrieving information related to the
user-supplied query words. This task has two parts; one is finding "featured
words" which describe an article best and the other is finding a match among
these words to user-defined search terms. There are two main independent
approaches to achieve this task. The first one, using the concepts of
semantics, has been implemented partially. For more details see another paper
of Marko et al., 2002. The second approach is reported in this paper. It is a
theoretical model based on using Neural Network (NN). Instead of using keywords
or reading from the first few lines from papers/articles, the present model
gives emphasis on extracting "featured words" from an article. Obviously we
propose to exclude prepositions, articles and so on, that is, English words
like "of, the, are, so, therefore, " etc. from such a list. A neural model is
taken with its nodes pre-assigned energies. Whenever a match is found with
featured words and userdefined search words, the node is fired and jumps to a
higher energy. This firing continues until the model attains a steady energy
level and total energy is now calculated. Clearly, higher match will generate
higher energy; so on the basis of total energy, a ranking is done to the
article indicating degree of relevance to the user's interest. Another
important feature of the proposed model is incorporating a semantic module to
refine the search words; like finding association among search words, etc. In
this manner, information retrieval can be improved markedly.


title: Building Space-Time Meshes over Arbitrary Spatial Domains

abstract:
  We present an algorithm to construct meshes suitable for space-time
discontinuous Galerkin finite-element methods. Our method generalizes and
improves the `Tent Pitcher' algorithm of \"Ung\"or and Sheffer. Given an
arbitrary simplicially meshed domain M of any dimension and a time interval
[0,T], our algorithm builds a simplicial mesh of the space-time domain Mx[0,T],
in constant time per element. Our algorithm avoids the limitations of previous
methods by carefully adapting the durations of space-time elements to the local
quality and feature size of the underlying space mesh.


title: Handling Defeasibilities in Action Domains

abstract:
  Representing defeasibility is an important issue in common sense reasoning.
In reasoning about action and change, this issue becomes more difficult because
domain and action related defeasible information may conflict with general
inertia rules. Furthermore, different types of defeasible information may also
interfere with each other during the reasoning. In this paper, we develop a
prioritized logic programming approach to handle defeasibilities in reasoning
about action. In particular, we propose three action languages {\cal AT}^{0},
{\cal AT}^{1} and {\cal AT}^{2} which handle three types of defeasibilities in
action domains named defeasible constraints, defeasible observations and
actions with defeasible and abnormal effects respectively. Each language with a
higher superscript can be viewed as an extension of the language with a lower
superscript. These action languages inherit the simple syntax of {\cal A}
language but their semantics is developed in terms of transition systems where
transition functions are defined based on prioritized logic programs. By
illustrating various examples, we show that our approach eventually provides a
powerful mechanism to handle various defeasibilities in temporal prediction and
postdiction. We also investigate semantic properties of these three action
languages and characterize classes of action domains that present more
desirable solutions in reasoning about action within the underlying action
languages.


title: Mining All Non-Derivable Frequent Itemsets

abstract:
  Recent studies on frequent itemset mining algorithms resulted in significant
performance improvements. However, if the minimal support threshold is set too
low, or the data is highly correlated, the number of frequent itemsets itself
can be prohibitively large. To overcome this problem, recently several
proposals have been made to construct a concise representation of the frequent
itemsets, instead of mining all frequent itemsets. The main goal of this paper
is to identify redundancies in the set of all frequent itemsets and to exploit
these redundancies in order to reduce the result of a mining operation. We
present deduction rules to derive tight bounds on the support of candidate
itemsets. We show how the deduction rules allow for constructing a minimal
representation for all frequent itemsets. We also present connections between
our proposal and recent proposals for concise representations and we give the
results of experiments on real-life datasets that show the effectiveness of the
deduction rules. In fact, the experiments even show that in many cases, first
mining the concise representation, and then creating the frequent itemsets from
this representation outperforms existing frequent set mining algorithms.


title:
Characterization of Strongly Equivalent Logic Programs in Intermediate
  Logics

abstract:
  The non-classical, nonmonotonic inference relation associated with the answer
set semantics for logic programs gives rise to a relationship of 'strong
equivalence' between logical programs that can be verified in 3-valued Goedel
logic, G3, the strongest non-classical intermediate propositional logic
(Lifschitz, Pearce and Valverde, 2001). In this paper we will show that KC (the
logic obtained by adding axiom ~A v ~~A to intuitionistic logic), is the
weakest intermediate logic for which strongly equivalent logic programs, in a
language allowing negations, are logically equivalent.


title: Robust Feature Selection by Mutual Information Distributions

abstract:
  Mutual information is widely used in artificial intelligence, in a
descriptive way, to measure the stochastic dependence of discrete random
variables. In order to address questions such as the reliability of the
empirical value, one must consider sample-to-population inferential approaches.
This paper deals with the distribution of mutual information, as obtained in a
Bayesian framework by a second-order Dirichlet prior distribution. The exact
analytical expression for the mean and an analytical approximation of the
variance are reported. Asymptotic approximations of the distribution are
proposed. The results are applied to the problem of selecting features for
incremental learning and classification of the naive Bayes classifier. A fast,
newly defined method is shown to outperform the traditional approach based on
empirical mutual information on a number of real data sets. Finally, a
theoretical development is reported that allows one to efficiently extend the
above methods to incomplete samples in an easy and effective way.


title:
Using the Annotated Bibliography as a Resource for Indicative
  Summarization

abstract:
  We report on a language resource consisting of 2000 annotated bibliography
entries, which is being analyzed as part of our research on indicative document
summarization. We show how annotated bibliographies cover certain aspects of
summarization that have not been well-covered by other summary corpora, and
motivate why they constitute an important form to study for information
retrieval. We detail our methodology for collecting the corpus, and overview
our document feature markup that we introduced to facilitate summary analysis.
We present the characteristics of the corpus, methods of collection, and show
its use in finding the distribution of types of information included in
indicative summaries and their relative ordering within the summaries.


title:
Computer modeling of feelings and emotions: a quantitative neural
  network model of the feeling-of-knowing

abstract:
  The first quantitative neural network model of feelings and emotions is
proposed on the base of available data on their neuroscience and evolutionary
biology nature, and on a neural network human memory model which admits
distinct description of conscious and unconscious mental processes in a time
dependent manner. As an example, proposed model is applied to quantitative
description of the feeling of knowing.


title:
Implementation and complexity of the watershed-from-markers algorithm
  computed as a minimal cost forest

abstract:
  The watershed algorithm belongs to classical algorithms in mathematical
morphology. Lotufo et al. published a principle of the watershed computation by
means of an Image Foresting Transform (IFT), which computes a shortest path
forest from given markers. The algorithm itself was described for a 2D case
(image) without a detailed discussion of its computation and memory demands for
real datasets. As IFT cleverly solves the problem of plateaus and as it gives
precise results when thin objects have to be segmented, it is obvious to use
this algorithm for 3D datasets taking in mind the minimizing of a higher memory
consumption for the 3D case without loosing low asymptotical time complexity of
O(m+C) (and also the real computation speed). The main goal of this paper is an
implementation of the IFT algorithm with a priority queue with buckets and
careful tuning of this implementation to reach as minimal memory consumption as
possible.
  The paper presents five possible modifications and methods of implementation
of the IFT algorithm. All presented implementations keep the time complexity of
the standard priority queue with buckets but the best one minimizes the costly
memory allocation and needs only 19-45% of memory for typical 3D medical
imaging datasets. Memory saving was reached by an IFT algorithm simplification,
which stores more elements in temporary structures but these elements are
simpler and thus need less memory.
  The best presented modification allows segmentation of large 3D medical
datasets (up to 512x512x680 voxels) with 12-or 16-bits per voxel on currently
available PC based workstations.


title: Performance Comparison of Function Evaluation Methods

abstract:
  We perform a comparison of the performance and efficiency of four different
function evaluation methods: black-box functions, binary trees, $n$-ary trees
and string parsing. The test consists in evaluating 8 different functions of
two variables $x,y$ over 5000 floating point values of the pair $(x,y)$. The
outcome of the test indicates that the $n$-ary tree representation of algebraic
expressions is the fastest method, closely followed by black-box function
method, then by binary trees and lastly by string parsing.


title: A Statistical Physics Perspective on Web Growth

abstract:
  Approaches from statistical physics are applied to investigate the structure
of network models whose growth rules mimic aspects of the evolution of the
world-wide web. We first determine the degree distribution of a growing network
in which nodes are introduced one at a time and attach to an earlier node of
degree k with rate A_ksim k^gamma. Very different behaviors arise for gamma<1,
gamma=1, and gamma>1. We also analyze the degree distribution of a
heterogeneous network, the joint age-degree distribution, the correlation
between degrees of neighboring nodes, as well as global network properties. An
extension to directed networks is then presented. By tuning model parameters to
reasonable values, we obtain distinct power-law forms for the in-degree and
out-degree distributions with exponents that are in good agreement with current
data for the web. Finally, a general growth process with independent
introduction of nodes and links is investigated. This leads to independently
growing sub-networks that may coalesce with other sub-networks. General results
for both the size distribution of sub-networks and the degree distribution are
obtained.


title: Fast Deterministic Consensus in a Noisy Environment

abstract:
  It is well known that the consensus problem cannot be solved
deterministically in an asynchronous environment, but that randomized solutions
are possible. We propose a new model, called noisy scheduling, in which an
adversarial schedule is perturbed randomly, and show that in this model
randomness in the environment can substitute for randomness in the algorithm.
In particular, we show that a simplified, deterministic version of Chandra's
wait-free shared-memory consensus algorithm (PODC, 1996, pp. 166-175) solves
consensus in time at most logarithmic in the number of active processes. The
proof of termination is based on showing that a race between independent
delayed renewal processes produces a winner quickly. In addition, we show that
the protocol finishes in constant time using quantum and priority-based
scheduling on a uniprocessor, suggesting that it is robust against the choice
of model over a wide range.


title:
High-order fundamental and general solutions of convection-diffusion
  equation and their applications with boundary particle method

abstract:
  In this study, we presented the high-order fundamental solutions and general
solutions of convection-diffusion equation. To demonstrate their efficacy, we
applied the high-order general solutions to the boundary particle method (BPM)
for the solution of some inhomogeneous convection-diffusion problems, where the
BPM is a new truly boundary-only meshfree collocation method based on multiple
reciprocity principle. For the sake of completeness, the BPM is also briefly
described here.


title: A Method for Open-Vocabulary Speech-Driven Text Retrieval

abstract:
  While recent retrieval techniques do not limit the number of index terms,
out-of-vocabulary (OOV) words are crucial in speech recognition. Aiming at
retrieving information with spoken queries, we fill the gap between speech
recognition and text retrieval in terms of the vocabulary size. Given a spoken
query, we generate a transcription and detect OOV words through speech
recognition. We then correspond detected OOV words to terms indexed in a target
collection to complete the transcription, and search the collection for
documents relevant to the completed transcription. We show the effectiveness of
our method by way of experiments.


title:
Japanese/English Cross-Language Information Retrieval: Exploration of
  Query Translation and Transliteration

abstract:
  Cross-language information retrieval (CLIR), where queries and documents are
in different languages, has of late become one of the major topics within the
information retrieval community. This paper proposes a Japanese/English CLIR
system, where we combine a query translation and retrieval modules. We
currently target the retrieval of technical documents, and therefore the
performance of our system is highly dependent on the quality of the translation
of technical terms. However, the technical term translation is still
problematic in that technical terms are often compound words, and thus new
terms are progressively created by combining existing base words. In addition,
Japanese often represents loanwords based on its special phonogram.
Consequently, existing dictionaries find it difficult to achieve sufficient
coverage. To counter the first problem, we produce a Japanese/English
dictionary for base words, and translate compound words on a word-by-word
basis. We also use a probabilistic method to resolve translation ambiguity. For
the second problem, we use a transliteration method, which corresponds words
unlisted in the base word dictionary to their phonetic equivalents in the
target language. We evaluate our system using a test collection for CLIR, and
show that both the compound word translation and transliteration methods
improve the system performance.


title: Distance function wavelets - Part III: "Exotic" transforms and series

abstract:
  Part III of the reports consists of various unconventional distance function
wavelets (DFW). The dimension and the order of partial differential equation
(PDE) are first used as a substitute of the scale parameter in the DFW
transforms and series, especially with the space and time-space potential
problems. It is noted that the recursive multiple reciprocity formulation is
the DFW series. The Green second identity is used to avoid the singularity of
the zero-order fundamental solution in creating the DFW series. The fundamental
solutions of various composite PDEs are found very flexible and efficient to
handle a borad range of problems. We also discuss the underlying connections
between the crucial concepts of dimension, scale and the order of PDE through
the analysis of dissipative acoustic wave propagation. The shape parameter of
the potential problems is also employed as the "scale parameter" to create the
non-orthogonal DFW. This paper also briefly discusses and conjectures the DFW
correspondences of a variety of coordinate variable transforms and series.
Practically important, the anisotropic and inhomogeneous DFW's are developed by
using the geodesic distance variable. The DFW and the related basis functions
are also used in making the kernel distance sigmoidal functions, which are
potentially useful in the artificial neural network and machine learning. As or
even worse than the preceding two reports, this study scarifies mathematical
rigor and in turn unfetter imagination. Most results are intuitively obtained
without rigorous analysis. Follow-up research is still under way. The paper is
intended to inspire more research into this promising area.


title: The Prioritized Inductive Logic Programs

abstract:
  The limit behavior of inductive logic programs has not been explored, but
when considering incremental or online inductive learning algorithms which
usually run ongoingly, such behavior of the programs should be taken into
account. An example is given to show that some inductive learning algorithm may
not be correct in the long run if the limit behavior is not considered. An
inductive logic program is convergent if given an increasing sequence of
example sets, the program produces a corresponding sequence of the Horn logic
programs which has the set-theoretic limit, and is limit-correct if the limit
of the produced sequence of the Horn logic programs is correct with respect to
the limit of the sequence of the example sets. It is shown that the GOLEM
system is not limit-correct. Finally, a limit-correct inductive logic system,
called the prioritized GOLEM system, is proposed as a solution.


title: On Simultaneous Graph Embedding

abstract:
  We consider the problem of simultaneous embedding of planar graphs. There are
two variants of this problem, one in which the mapping between the vertices of
the two graphs is given and another where the mapping is not given. In
particular, we show that without mapping, any number of outerplanar graphs can
be embedded simultaneously on an $O(n)\times O(n)$ grid, and an outerplanar and
general planar graph can be embedded simultaneously on an $O(n^2)\times O(n^3)$
grid. If the mapping is given, we show how to embed two paths on an $n \times
n$ grid, a caterpillar and a path on an $n \times 2n$ grid, or two caterpillar
graphs on an $O(n^2)\times O(n^3)$ grid. We also show that 5 paths, or 3
caterpillars, or two general planar graphs cannot be simultaneously embedded
given the mapping.


title: Simultaneous Embedding of a Planar Graph and Its Dual on the Grid

abstract:
  Traditional representations of graphs and their duals suggest the requirement
that the dual vertices be placed inside their corresponding primal faces, and
the edges of the dual graph cross only their corresponding primal edges. We
consider the problem of simultaneously embedding a planar graph and its dual
into a small integer grid such that the edges are drawn as straight-line
segments and the only crossings are between primal-dual pairs of edges. We
provide a linear-time algorithm that simultaneously embeds a 3-connected planar
graph and its dual on a (2n-2) by (2n-2) integer grid, where n is the total
number of vertices in the graph and its dual. Furthermore our embedding
algorithm satisfies the two natural requirements mentioned above.


title: Multidimensional Network Monitoring for Intrusion Detection

abstract:
  An approach for real-time network monitoring in terms of numerical
time-dependant functions of protocol parameters is suggested. Applying complex
systems theory for information f{l}ow analysis of networks, the information
traffic is described as a trajectory in multi-dimensional parameter-time space
with about 10-12 dimensions. The network traffic description is synthesized by
applying methods of theoretical physics and complex systems theory, to provide
a robust approach for network monitoring that detects known intrusions, and
supports developing real systems for detection of unknown intrusions. The
methods of data analysis and pattern recognition presented are the basis of a
technology study for an automatic intrusion detection system that detects the
attack in the reconnaissance stage.


title: The analysis of the IFPUG method sensitivity

abstract:
  J. Albrecht`s Function Point Analysis (FPA) is a method to determine the
functional size of software products. An organization called International
Function Point Users Group (IPFUG), considers the FPA as a standard in the
software functional size measurement. The Albrechts method is followed by IPFUG
method which includes some modifications in order to improve it. A limitation
of the method refers to the fact that FPA is not sensitive enough to
differentiate the functional size in small enhancements. That affects the
productivity analysis, where the software product functional size is required.
To provide more power to the functional size measurement, A. Abran, M. Maya and
H. Nguyeckim have proposed some modifications to improve it. The IPFUG v 4.1
method which includes these modifications is named IFPUG v 4.1 extended. In
this work we set the conditions to delimiting granular from non granular
functions and we calculate the static calibration and sensitivity graphs for
the measurements of a set of projects with a high percentage of granular
functions, all of then measured with the IFPUG v 4.1 method and the IFPUG v 4.1
extended. Finally, we introduce a statistic analysis in order to determine
whether significant differences exist between both methods or not.


title: The Fastest and Shortest Algorithm for All Well-Defined Problems

abstract:
  An algorithm $M$ is described that solves any well-defined problem $p$ as
quickly as the fastest algorithm computing a solution to $p$, save for a factor
of 5 and low-order additive terms. $M$ optimally distributes resources between
the execution of provably correct $p$-solving programs and an enumeration of
all proofs, including relevant proofs of program correctness and of time bounds
on program runtimes. $M$ avoids Blum's speed-up theorem by ignoring programs
without correctness proof. $M$ has broader applicability and can be faster than
Levin's universal search, the fastest method for inverting functions save for a
large multiplicative constant. An extension of Kolmogorov complexity and two
novel natural measures of function complexity are used to show that the most
efficient program computing some function $f$ is also among the shortest
programs provably computing $f$.


title: Relational Association Rules: getting WARMeR

abstract:
  In recent years, the problem of association rule mining in transactional data
has been well studied. We propose to extend the discovery of classical
association rules to the discovery of association rules of conjunctive queries
in arbitrary relational data, inspired by the WARMR algorithm, developed by
Dehaspe and Toivonen, that discovers association rules over a limited set of
conjunctive queries. Conjunctive query evaluation in relational databases is
well understood, but still poses some great challenges when approached from a
discovery viewpoint in which patterns are generated and evaluated with respect
to some well defined search space and pruning operators.


title: Sierpinski Gaskets for Logic Functions Representation

abstract:
  This paper introduces a new approach to represent logic functions in the form
of Sierpinski Gaskets. The structure of the gasket allows to manipulate with
the corresponding logic expression using recursive essence of fractals. Thus,
the Sierpinski gasket's pattern has myriad useful properties which can enhance
practical features of other graphic representations like decision diagrams. We
have covered possible applications of Sierpinski gaskets in logic design and
justified our assumptions in logic function minimization (both Boolean and
multiple-valued cases). The experimental results on benchmarks with advances in
the novel structure are considered as well.


title:
The Lattice of Fuzzy Intervals and Sufficient Conditions for its
  Distributivity

abstract:
  Given a reference lattice, we define fuzzy intervals to be the fuzzy sets
such that their p-cuts are crisp closed intervals. We show that: given a
complete reference lattice, the collection of its fuzzy intervals is a complete
lattice. Furthermore we show that: if the reference lattice is completely
distributive then the lattice of its fuzzy intervals is distributive.


title: Interleaved semantic interpretation in environment-based parsing

abstract:
  This paper extends a polynomial-time parsing algorithm that resolves
structural ambiguity in input to a speech-based user interface by calculating
and comparing the denotations of rival constituents, given some model of the
interfaced application environment (Schuler 2001). The algorithm is extended to
incorporate a full set of logical operators, including quantifiers and
conjunctions, into this calculation without increasing the complexity of the
overall algorithm beyond polynomial time, both in terms of the length of the
input and the number of entities in the environment model.


title:
Behaviour-based Knowledge Systems: An Epigenetic Path from Behaviour to
  Knowledge

abstract:
  In this paper we expose the theoretical background underlying our current
research. This consists in the development of behaviour-based knowledge
systems, for closing the gaps between behaviour-based and knowledge-based
systems, and also between the understandings of the phenomena they model. We
expose the requirements and stages for developing behaviour-based knowledge
systems and discuss their limits. We believe that these are necessary
conditions for the development of higher order cognitive capacities, in
artificial and natural cognitive systems.


title:
Knowledge management for enterprises (Wissensmanagement fuer
  Unternehmen)

abstract:
  Although knowledge is one of the most valuable resource of enterprises and an
important production and competition factor, this intellectual potential is
often used (or maintained) only inadequate by the enterprises. Therefore, in a
globalised and growing market the optimal usage of existing knowledge
represents a key factor for enterprises of the future. Here, knowledge
management systems should engage facilitating. Because geographically far
distributed establishments cause, however, a distributed system, this paper
should uncover the spectrum connected with it and present a possible basic
approach which is based on ontologies and modern, platform independent
technologies. Last but not least this attempt, as well as general questions of
the knowledge management, are discussed.


title: Computer-Generated Photorealistic Hair

abstract:
  This paper presents an efficient method for generating and rendering
photorealistic hair in two dimensional pictures. The method consists of three
major steps. Simulating an artist drawing is used to design the rough hair
shape. A convolution based filter is then used to generate photorealistic hair
patches. A refine procedure is finally used to blend the boundaries of the
patches with surrounding areas. This method can be used to create all types of
photorealistic human hair (head hair, facial hair and body hair). It is also
suitable for fur and grass generation. Applications of this method include:
hairstyle designing/editing, damaged hair image restoration, human hair
animation, virtual makeover of a human, and landscape creation.


title:
A Probabilistic Method for Analyzing Japanese Anaphora Integrating Zero
  Pronoun Detection and Resolution

abstract:
  This paper proposes a method to analyze Japanese anaphora, in which zero
pronouns (omitted obligatory cases) are used to refer to preceding entities
(antecedents). Unlike the case of general coreference resolution, zero pronouns
have to be detected prior to resolution because they are not expressed in
discourse. Our method integrates two probability parameters to perform zero
pronoun detection and resolution in a single framework. The first parameter
quantifies the degree to which a given case is a zero pronoun. The second
parameter quantifies the degree to which a given entity is the antecedent for a
detected zero pronoun. To compute these parameters efficiently, we use corpora
with/without annotations of anaphoric relations. We show the effectiveness of
our method by way of experiments.


title: A sufficient condition for global invertibility of Lipschitz mapping

abstract:
  We show that S.Vavasis' sufficient condition for global invertibility of a
polynomial mapping can be easily generalized to the case of a general Lipschitz
mapping. Keywords: Invertibility conditions, generalized Jacobian, nonsmooth
analysis.


title: A correct proof of the heuristic GCD algorithm

abstract:
  In this note, we fill a gap in the proof of the heuristic GCD in the
multivariate case made by Char, Geddes and Gonnet (JSC 1989) and give some
additionnal information on this method.


title: Algorithms for Media

abstract:
  Falmagne recently introduced the concept of a medium, a combinatorial object
encompassing hyperplane arrangements, topological orderings, acyclic
orientations, and many other familiar structures. We find efficient solutions
for several algorithmic problems on media: finding short reset sequences,
shortest paths, testing whether a medium has a closed orientation, and listing
the states of a medium given a black-box description.


title:
Applying a Hybrid Query Translation Method to Japanese/English
  Cross-Language Patent Retrieval

abstract:
  This paper applies an existing query translation method to cross-language
patent retrieval. In our method, multiple dictionaries are used to derive all
possible translations for an input query, and collocational statistics are used
to resolve translation ambiguity. We used Japanese/English parallel patent
abstracts to perform comparative experiments, where our method outperformed a
simple dictionary-based query translation method, and achieved 76% of
monolingual retrieval in terms of average precision.


title: PRIME: A System for Multi-lingual Patent Retrieval

abstract:
  Given the growing number of patents filed in multiple countries, users are
interested in retrieving patents across languages. We propose a multi-lingual
patent retrieval system, which translates a user query into the target
language, searches a multilingual database for patents relevant to the query,
and improves the browsing efficiency by way of machine translation and
clustering. Our system also extracts new translations from patent families
consisting of comparable patents, to enhance the translation dictionary.


title: Language Modeling for Multi-Domain Speech-Driven Text Retrieval

abstract:
  We report experimental results associated with speech-driven text retrieval,
which facilitates retrieving information in multiple domains with spoken
queries. Since users speak contents related to a target collection, we produce
language models used for speech recognition based on the target collection, so
as to improve both the recognition and retrieval accuracy. Experiments using
existing test collections combined with dictated queries showed the
effectiveness of our method.


title:
Speech-Driven Text Retrieval: Using Target IR Collections for
  Statistical Language Model Adaptation in Speech Recognition

abstract:
  Speech recognition has of late become a practical technology for real world
applications. Aiming at speech-driven text retrieval, which facilitates
retrieving information with spoken queries, we propose a method to integrate
speech recognition and retrieval methods. Since users speak contents related to
a target collection, we adapt statistical language models used for speech
recognition based on the target collection, so as to improve both the
recognition and retrieval accuracy. Experiments using existing test collections
combined with dictated queries showed the effectiveness of our method.


title:
A Multilevel Approach to Topology-Aware Collective Operations in
  Computational Grids

abstract:
  The efficient implementation of collective communiction operations has
received much attention. Initial efforts produced "optimal" trees based on
network communication models that assumed equal point-to-point latencies
between any two processes. This assumption is violated in most practical
settings, however, particularly in heterogeneous systems such as clusters of
SMPs and wide-area "computational Grids," with the result that collective
operations perform suboptimally. In response, more recent work has focused on
creating topology-aware trees for collective operations that minimize
communication across slower channels (e.g., a wide-area network). While these
efforts have significant communication benefits, they all limit their view of
the network to only two layers. We present a strategy based upon a multilayer
view of the network. By creating multilevel topology-aware trees we take
advantage of communication cost differences at every level in the network. We
used this strategy to implement topology-aware versions of several MPI
collective operations in MPICH-G2, the Globus Toolkit[tm]-enabled version of
the popular MPICH implementation of the MPI standard. Using information about
topology provided by MPICH-G2, we construct these multilevel topology-aware
trees automatically during execution. We present results demonstrating the
advantages of our multilevel approach by comparing it to the default
(topology-unaware) implementation provided by MPICH and a topology-aware
two-layer implementation.


title:
Hidden Markov model segmentation of hydrological and enviromental time
  series

abstract:
  Motivated by Hubert's segmentation procedure we discuss the application of
hidden Markov models (HMM) to the segmentation of hydrological and enviromental
time series. We use a HMM algorithm which segments time series of several
hundred terms in a few seconds and is computationally feasible for even longer
time series. The segmentation algorithm computes the Maximum Likelihood
segmentation by use of an expectation / maximization iteration. We rigorously
prove algorithm convergence and use numerical experiments, involving
temperature and river discharge time series, to show that the algorithm usually
converges to the globally optimal segmentation. The relation of the proposed
algorithm to Hubert's segmentation procedure is also discussed.

categories: cs.CE cs.NA math.NA nlin.CD physics.data-an


title: MPICH-G2: A Grid-Enabled Implementation of the Message Passing Interface

abstract:
  Application development for distributed computing "Grids" can benefit from
tools that variously hide or enable application-level management of critical
aspects of the heterogeneous environment. As part of an investigation of these
issues, we have developed MPICH-G2, a Grid-enabled implementation of the
Message Passing Interface (MPI) that allows a user to run MPI programs across
multiple computers, at the same or different sites, using the same commands
that would be used on a parallel computer. This library extends the Argonne
MPICH implementation of MPI to use services provided by the Globus Toolkit for
authentication, authorization, resource allocation, executable staging, and
I/O, as well as for process creation, monitoring, and control. Various
performance-critical operations, including startup and collective operations,
are configured to exploit network topology information. The library also
exploits MPI constructs for performance management; for example, the MPI
communicator construct is used for application-level discovery of, and
adaptation to, both network topology and network quality-of-service mechanisms.
We describe the MPICH-G2 design and implementation, present performance
results, and review application experiences, including record-setting
distributed simulations.


title: Anticipatory Guidance of Plot

abstract:
  An anticipatory system for guiding plot development in interactive narratives
is described. The executable model is a finite automaton that provides the
implemented system with a look-ahead. The identification of undesirable future
states in the model is used to guide the player, in a transparent manner. In
this way, too radical twists of the plot can be avoided. Since the player
participates in the development of the plot, such guidance can have many forms,
depending on the environment of the player, on the behavior of the other
players, and on the means of player interaction. We present a design method for
interactive narratives which produces designs suitable for the implementation
of anticipatory mechanisms. Use of the method is illustrated by application to
our interactive computer game Kaktus.


title:
National Infrastructure Contingencies: Survey of Wireless Technology
  Support

abstract:
  In modern society, the flow of information has become the lifeblood of
commerce and social interaction. This movement of data supports most aspects of
the United States economy in particular, as well as, serving as the vehicle
upon which governmental agencies react to social conditions. In addition, it is
understood that the continuance of efficient and reliable data communications
during times of national or regional disaster remains a priority in the United
States. The coordination of emergency response and area revitalization /
rehabilitation efforts between local, state, and federal emergency response is
increasingly necessary as agencies strive to work more seamlessly between the
affected organizations. Additionally, international support is often made
available to react to such adverse conditions as wildfire suppression scenarios
and therefore require the efficient management of workforce and associated
logistics support.
  It is through the examination of the issues related to un-tethered data
transmission during infrastructure contingencies that responders may best
tailor a unified approach to the rapid recovery after disasters occur.


title: Using eigenvectors of the bigram graph to infer morpheme identity

abstract:
  This paper describes the results of some experiments exploring statistical
methods to infer syntactic behavior of words and morphemes from a raw corpus in
an unsupervised fashion. It shares certain points in common with Brown et al
(1992) and work that has grown out of that: it employs statistical techniques
to analyze syntactic behavior based on what words occur adjacent to a given
word. However, we use an eigenvector decomposition of a nearest-neighbor graph
to produce a two-dimensional rendering of the words of a corpus in which words
of the same syntactic category tend to form neighborhoods. We exploit this
technique for extending the value of automatic learning of morphology. In
particular, we look at the suffixes derived from a corpus by unsupervised
learning of morphology, and we ask which of these suffixes have a consistent
syntactic function (e.g., in English, -tion is primarily a mark of nouns, but
-s marks both noun plurals and 3rd person present on verbs), and we determine
that this method works well for this task.


title:
Analysis of Titles and Readers For Title Generation Centered on the
  Readers

abstract:
  The title of a document has two roles, to give a compact summary and to lead
the reader to read the document. Conventional title generation focuses on
finding key expressions from the author's wording in the document to give a
compact summary and pays little attention to the reader's interest. To make the
title play its second role properly, it is indispensable to clarify the content
(``what to say'') and wording (``how to say'') of titles that are effective to
attract the target reader's interest. In this article, we first identify
typical content and wording of titles aimed at general readers in a comparative
study between titles of technical papers and headlines rewritten for
newspapers. Next, we describe the results of a questionnaire survey on the
effects of the content and wording of titles on the reader's interest. The
survey of general and knowledgeable readers shows both common and different
tendencies in interest.


title: Optimally cutting a surface into a disk

abstract:
  We consider the problem of cutting a set of edges on a polyhedral manifold
surface, possibly with boundary, to obtain a single topological disk,
minimizing either the total number of cut edges or their total length. We show
that this problem is NP-hard, even for manifolds without boundary and for
punctured spheres. We also describe an algorithm with running time n^{O(g+k)},
where n is the combinatorial complexity, g is the genus, and k is the number of
boundary components of the input surface. Finally, we describe a greedy
algorithm that outputs a O(log^2 g)-approximation of the minimum cut graph in
O(g^2 n log n) time.


title: Efficient Deep Processing of Japanese

abstract:
  We present a broad coverage Japanese grammar written in the HPSG formalism
with MRS semantics. The grammar is created for use in real world applications,
such that robustness and performance issues play an important role. It is
connected to a POS tagging and word segmentation tool. This grammar is being
developed in a multilingual context, requiring MRS structures that are easily
comparable across languages.


title:
Orthonormal RBF wavelet and ridgelet-like series and transforms for
  high-dimensional problems

abstract:
  This paper developed a systematic strategy establishing RBF on the wavelet
analysis, which includes continuous and discrete RBF orthonormal wavelet
transforms respectively in terms of singular fundamental solutions and
nonsingular general solutions of differential operators. In particular, the
harmonic Bessel RBF transforms were presented for high-dimensional data
processing. It was also found that the kernel functions of convection-diffusion
operator are feasible to construct some stable ridgelet-like RBF transforms. We
presented time-space RBF transforms based on non-singular solution and
fundamental solution of time-dependent differential operators. The present
methodology was further extended to analysis of some known RBFs such as the MQ,
Gaussian and pre-wavelet kernel RBFs.


title:
Evolutionary Circuit Design: Information Theory Perspective on Signal
  Propagation

abstract:
  This paper presents case-study results on the application of information
theoretic approach to gate-level evolutionary circuit design. We introduce
information measures to provide better estimates of synthesis criteria of
digital circuits. For example, the analysis of signal propagation during
evolving gate-level synthesis can be improved by using information theoretic
measures that will make it possible to find the most effective geometry and
therefore predict the cost of the final design solution. The problem is
considered from the information engine point of view. That is, the process of
evolutionary gate-level circuit design is presented via such measures as
entropy, logical work and information vitality. Some examples of geometry
driven synthesis are provided to prove the above idea.


title: Agent Programming with Declarative Goals

abstract:
  A long and lasting problem in agent research has been to close the gap
between agent logics and agent programming frameworks. The main reason for this
problem of establishing a link between agent logics and agent programming
frameworks is identified and explained by the fact that agent programming
frameworks have not incorporated the concept of a `declarative goal'. Instead,
such frameworks have focused mainly on plans or `goals-to-do' instead of the
end goals to be realised which are also called `goals-to-be'. In this paper, a
new programming language called GOAL is introduced which incorporates such
declarative goals. The notion of a `commitment strategy' - one of the main
theoretical insights due to agent logics, which explains the relation between
beliefs and goals - is used to construct a computational semantics for GOAL.
Finally, a proof theory for proving properties of GOAL agents is introduced.
Thus, we offer a complete theory of agent programming in the sense that our
theory provides both for a programming framework and a programming logic for
such agents. An example program is proven correct by using this programming
logic.


title:
Computing Elementary Symmetric Polynomials with a Sublinear Number of
  Multiplications

abstract:
  Elementary symmetric polynomials $S_n^k$ are used as a benchmark for the
bounded-depth arithmetic circuit model of computation. In this work we prove
that $S_n^k$ modulo composite numbers $m=p_1p_2$ can be computed with much
fewer multiplications than over any field, if the coefficients of monomials
$x_{i_1}x_{i_2}... x_{i_k}$ are allowed to be 1 either mod $p_1$ or mod $p_2$
but not necessarily both. More exactly, we prove that for any constant $k$ such
a representation of $S_n^k$ can be computed modulo $p_1p_2$ using only
$\exp(O(\sqrt{\log n}\log\log n))$ multiplications on the most restricted
depth-3 arithmetic circuits, for $\min({p_1,p_2})>k!$. Moreover, the number of
multiplications remain sublinear while $k=O(\log\log n).$ In contrast, the
well-known Graham-Pollack bound yields an $n-1$ lower bound for the number of
multiplications even for the exact computation (not the representation) of
$S_n^2$. Our results generalize for other non-prime power composite moduli as
well. The proof uses the famous BBR-polynomial of Barrington, Beigel and
Rudich.


title: Symmetric boundary knot method

abstract:
  The boundary knot method (BKM) is a recent boundary-type radial basis
function (RBF) collocation scheme for general PDEs. Like the method of
fundamental solution (MFS), the RBF is employed to approximate the
inhomogeneous terms via the dual reciprocity principle. Unlike the MFS, the
method uses a nonsingular general solution instead of a singular fundamental
solution to evaluate the homogeneous solution so as to circumvent the
controversial artificial boundary outside the physical domain. The BKM is
meshfree, superconvergent, integration free, very easy to learn and program.
The original BKM, however, loses symmetricity in the presense of mixed
boundary. In this study, by analogy with Hermite RBF interpolation, we
developed a symmetric BKM scheme. The accuracy and efficiency of the symmetric
BKM are also numerically validated in some 2D and 3D Helmholtz and diffusion
reaction problems under complicated geometries.


title: Improving Web Database Access Using Decision Diagrams

abstract:
  In some areas of management and commerce, especially in Electronic commerce
(E-commerce), that are accelerated by advances in Web technologies, it is
essential to support the decision making process using formal methods. Among
the problems of E-commerce applications: reducing the time of data access so
that huge databases can be searched quickly; decreasing the cost of database
design ... etc. We present the application of Decision Diagrams design using
Information Theory approach to improve database access speeds. We show that
such utilization provides systematic and visual ways of applying Decision
Making methods to simplify complex Web engineering problems.


title:
Synthesis of Low-Power Digital Circuits Derived from Binary Decision
  Diagrams

abstract:
  This paper introduces a novel method for synthesizing digital circuits
derived from Binary Decision Diagrams (BDDs) that can yield to reduction in
power dissipation. The power reduction is achieved by decreasing the switching
activity in a circuit while paying close attention to information measures as
an optimization criterion. We first present the technique of efficient
BDD-based computation of information measures which are used to guide the power
optimization procedures. Using this technique, we have developed an algorithm
of BDD reordering which leads to reducing the power consumption of the circuits
derived from BDDs. Results produced by the synthesis on the ISCAS benchmark
circuits are very encouraging.


title:
A Compact Graph Model of Handwritten Images: Integration into
  Authentification and Recognition

abstract:
  A novel algorithm for creating a mathematical model of curved shapes is
introduced. The core of the algorithm is based on building a graph
representation of the contoured image, which occupies less storage space than
produced by raster compression techniques. Different advanced applications of
the mathematical model are discussed: recognition of handwritten characters and
verification of handwritten text and signatures for authentification purposes.
Reducing the storage requirements due to the efficient mathematical model
results in faster retrieval and processing times. The experimental outcomes in
compression of contoured images and recognition of handwritten numerals are
given.


title: On the Information Engine of Circuit Design

abstract:
  This paper addresses a new approach to find a spectrum of information
measures for the process of digital circuit synthesis. We consider the problem
from the information engine point of view. The circuit synthesis as a whole and
different steps of the design process (an example of decision diagram is given)
are presented via such measurements as entropy, logical work and information
vitality. We also introduce new information measures to provide better
estimates of synthesis criteria. We show that the basic properties of
information engine, such as the conservation law of information flow and the
equilibrium law of information can be formulated.


title: New advances in dual reciprocity and boundary-only RBF methods

abstract:
  This paper made some significant advances in the dual reciprocity and
boundary-only RBF techniques. The proposed boundary knot method (BKM) is
different from the standard boundary element method in a number of important
aspects. Namely, it is truly meshless, exponential convergence,
integration-free (of course, no singular integration), boundary-only for
general problems, and leads to symmetric matrix under certain conditions (able
to be extended to general cases after further modified). The BKM also avoids
the artificial boundary in the method of fundamental solution. An amazing
finding is that the BKM can formulate linear modeling equations for nonlinear
partial differential systems with linear boundary conditions. This merit makes
it circumvent all perplexing issues in the iteration solution of nonlinear
equations. On the other hand, by analogy with Green's second identity, this
paper also presents a general solution RBF (GSR) methodology to construct
efficient RBFs in the dual reciprocity and domain-type RBF collocation methods.
The GSR approach first establishes an explicit relationship between the BEM and
RBF itself on the ground of the weighted residual principle. This paper also
discusses the RBF convergence and stability problems within the framework of
integral equation theory.


title:
Relationship between boundary integral equation and radial basis
  function

abstract:
  This paper aims to survey our recent work relating to the radial basis
function (RBF) from some new views of points. In the first part, we established
the RBF on numerical integration analysis based on an intrinsic relationship
between the Green's boundary integral representation and RBF. It is found that
the kernel function of integral equation is important to create efficient RBF.
The fundamental solution RBF (FS-RBF) was presented as a novel strategy
constructing operator-dependent RBF. We proposed a conjecture formula featuring
the dimension affect on error bound to show the independent-dimension merit of
the RBF techniques. We also discussed wavelet RBF, localized RBF schemes, and
the influence of node placement on the RBF solution accuracy. The
centrosymmetric matrix structure of the RBF interpolation matrix under
symmetric node placing is proved.
  The second part of this paper is concerned with the boundary knot method
(BKM), a new boundary-only, meshless, spectral convergent, integration-free RBF
collocation technique. The BKM was tested to the Helmholtz, Laplace, linear and
nonlinear convection-diffusion problems. In particular, we introduced the
response knot-dependent nonsingular general solution to calculate
varying-parameter and nonlinear steady convection-diffusion problems very
efficiently. By comparing with the multiple dual reciprocity method, we
discussed the completeness issue of the BKM.
  Finally, the nonsingular solutions for some known differential operators were
given in appendix. Also we expanded the RBF concepts by introducing time-space
RBF for transient problems.


title: New Insights in Boundary-only and Domain-type RBF Methods

abstract:
  This paper has made some significant advances in the boundary-only and
domain-type RBF techniques. The proposed boundary knot method (BKM) is
different from the standard boundary element method in a number of important
aspects. Namely, it is truly meshless, exponential convergence,
integration-free (of course, no singular integration), boundary-only for
general problems, and leads to symmetric matrix under certain conditions (able
to be extended to general cases after further modified). The BKM also avoids
the artificial boundary in the method of fundamental solution. An amazing
finding is that the BKM can formulate linear modeling equations for nonlinear
partial differential systems with linear boundary conditions. This merit makes
it circumvent all perplexing issues in the iteration solution of nonlinear
equations. On the other hand, by analogy with Green's second identity, we also
presents a general solution RBF (GSR) methodology to construct efficient RBFs
in the domain-type RBF collocation method and dual reciprocity method. The GSR
approach first establishes an explicit relationship between the BEM and RBF
itself on the ground of the potential theory. This paper also discusses some
essential issues relating to the RBF computing, which include time-space RBFs,
direct and indirect RBF schemes, finite RBF method, and the application of
multipole and wavelet to the RBF solution of the PDEs.


title: Definitions of distance function in radial basis function approach

abstract:
  Very few studies involve how to construct the efficient RBFs by means of
problem features. Recently the present author presented general solution RBF
(GS-RBF) methodology to create operator-dependent RBFs successfully [1]. On the
other hand, the normal radial basis function (RBF) is defined via Euclidean
space distance function or the geodesic distance [2]. This purpose of this note
is to redefine distance function in conjunction with problem features, which
include problem-dependent and time-space distance function.


title: Information Measures in Detecting and Recognizing Symmetries

abstract:
  This paper presents a method to detect and recognize symmetries in Boolean
functions. The idea is to use information theoretic measures of Boolean
functions to detect sub-space of possible symmetric variables. Coupled with the
new techniques of efficient estimations of information measures on Binary
Decision Diagrams (BDDs) we obtain promised results in symmetries detection for
large-scale functions.


title:
Towards Efficient Calculation of Information Measures for Reordering of
  Binary Decision Diagrams

abstract:
  This paper introduces new technique for efficient calculation of different
Shannon information measures which operates Binary Decision Diagrams (BDDs). We
offer an algorithm of BDD reordering which demonstrates the improvement of the
obtaining outcomes over the existing reordering approaches. The technique and
the reordering algorithm have been implemented, and the results on circuits'
benchmarks are analyzed. We point out that the results are quite promising, the
algorithm is very fast, and it is easy to implement. Finally, we show that our
approach to BDD reordering can yield to reduction in the power dissipation for
the circuits derived from BDDs.


title: Abduction, ASP and Open Logic Programs

abstract:
  Open logic programs and open entailment have been recently proposed as an
abstract framework for the verification of incomplete specifications based upon
normal logic programs and the stable model semantics. There are obvious
analogies between open predicates and abducible predicates. However, despite
superficial similarities, there are features of open programs that have no
immediate counterpart in the framework of abduction and viceversa. Similarly,
open programs cannot be immediately simulated with answer set programming
(ASP). In this paper we start a thorough investigation of the relationships
between open inference, abduction and ASP. We shall prove that open programs
generalize the other two frameworks. The generalized framework suggests
interesting extensions of abduction under the generalized stable model
semantics. In some cases, we will be able to reduce open inference to abduction
and ASP, thereby estimating its computational complexity. At the same time, the
aforementioned reduction opens the way to new applications of abduction and
ASP.


title: What is a Joint Goal? Games with Beliefs and Defeasible Desires

abstract:
  In this paper we introduce a qualitative decision and game theory based on
belief (B) and desire (D) rules. We show that a group of agents acts as if it
is maximizing achieved joint goals.


title: Domain-Dependent Knowledge in Answer Set Planning

abstract:
  In this paper we consider three different kinds of domain-dependent control
knowledge (temporal, procedural and HTN-based) that are useful in planning. Our
approach is declarative and relies on the language of logic programming with
answer set semantics (AnsProlog*). AnsProlog* is designed to plan without
control knowledge. We show how temporal, procedural and HTN-based control
knowledge can be incorporated into AnsProlog* by the modular addition of a
small number of domain-dependent rules, without the need to modify the planner.
We formally prove the correctness of our planner, both in the absence and
presence of the control knowledge. Finally, we perform some initial
experimentation that demonstrates the potential reduction in planning time that
can be achieved when procedural domain knowledge is used to solve planning
problems with large plan length.


title: On Concise Encodings of Preferred Extensions

abstract:
  Much work on argument systems has focussed on preferred extensions which
define the maximal collectively defensible subsets. Identification and
enumeration of these subsets is (under the usual assumptions) computationally
demanding. We consider approaches to deciding if a subset S is a preferred
extension which query a representations encoding all such extensions, so that
the computational effort is invested once only (for the initial enumeration)
rather than for each separate query.


title:
"Minimal defence": a refinement of the preferred semantics for
  argumentation frameworks

abstract:
  Dung's abstract framework for argumentation enables a study of the
interactions between arguments based solely on an ``attack'' binary relation on
the set of arguments. Various ways to solve conflicts between contradictory
pieces of information have been proposed in the context of argumentation,
nonmonotonic reasoning or logic programming, and can be captured by appropriate
semantics within Dung's framework. A common feature of these semantics is that
one can always maximize in some sense the set of acceptable arguments. We
propose in this paper to extend Dung's framework in order to allow for the
representation of what we call ``restricted'' arguments: these arguments should
only be used if absolutely necessary, that is, in order to support other
arguments that would otherwise be defeated. We modify Dung's preferred
semantics accordingly: a set of arguments becomes acceptable only if it
contains a minimum of restricted arguments, for a maximum of unrestricted
arguments.


title:
Linear-Time Algorithms for Computing Maximum-Density Sequence Segments
  with Bioinformatics Applications

abstract:
  We study an abstract optimization problem arising from biomolecular sequence
analysis. For a sequence A of pairs (a_i,w_i) for i = 1,..,n and w_i>0, a
segment A(i,j) is a consecutive subsequence of A starting with index i and
ending with index j. The width of A(i,j) is w(i,j) = sum_{i <= k <= j} w_k, and
the density is (sum_{i<= k <= j} a_k)/ w(i,j). The maximum-density segment
problem takes A and two values L and U as input and asks for a segment of A
with the largest possible density among those of width at least L and at most
U. When U is unbounded, we provide a relatively simple, O(n)-time algorithm,
improving upon the O(n \log L)-time algorithm by Lin, Jiang and Chao. When both
L and U are specified, there are no previous nontrivial results. We solve the
problem in O(n) time if w_i=1 for all i, and more generally in
O(n+n\log(U-L+1)) time when w_i>=1 for all i.


title:
Permutation graphs, fast forward permutations, and sampling the cycle
  structure of a permutation

abstract:
  A permutation P on {1,..,N} is a_fast_forward_permutation_ if for each m the
computational complexity of evaluating P^m(x)$ is small independently of m and
x. Naor and Reingold constructed fast forward pseudorandom cycluses and
involutions. By studying the evolution of permutation graphs, we prove that the
number of queries needed to distinguish a random cyclus from a random
permutation on {1,..,N} is Theta(N) if one does not use queries of the form
P^m(x), but is only Theta(1) if one is allowed to make such queries.
  We construct fast forward permutations which are indistinguishable from
random permutations even when queries of the form P^m(x) are allowed. This is
done by introducing an efficient method to sample the cycle structure of a
random permutation, which in turn solves an open problem of Naor and Reingold.


title:
Greedy Facility Location Algorithms Analyzed using Dual Fitting with
  Factor-Revealing LP

abstract:
  In this paper, we will formalize the method of dual fitting and the idea of
factor-revealing LP. This combination is used to design and analyze two greedy
algorithms for the metric uncapacitated facility location problem. Their
approximation factors are 1.861 and 1.61, with running times of O(mlog m) and
O(n^3), respectively, where n is the total number of vertices and m is the
number of edges in the underlying complete bipartite graph between cities and
facilities. The algorithms are used to improve recent results for several
variants of the problem.


title: Two Representations for Iterative Non-prioritized Change

abstract:
  We address a general representation problem for belief change, and describe
two interrelated representations for iterative non-prioritized change: a
logical representation in terms of persistent epistemic states, and a
constructive representation in terms of flocks of bases.


title: Collective Argumentation

abstract:
  An extension of an abstract argumentation framework, called collective
argumentation, is introduced in which the attack relation is defined directly
among sets of arguments. The extension turns out to be suitable, in particular,
for representing semantics of disjunctive logic programs. Two special kinds of
collective argumentation are considered in which the opponents can share their
arguments.


title: Intuitions and the modelling of defeasible reasoning: some case studies

abstract:
  The purpose of this paper is to address some criticisms recently raised by
John Horty in two articles against the validity of two commonly accepted
defeasible reasoning patterns, viz. reinstatement and floating conclusions. I
shall argue that Horty's counterexamples, although they significantly raise our
understanding of these reasoning patterns, do not show their invalidity. Some
of them reflect patterns which, if made explicit in the formalisation, avoid
the unwanted inference without having to give up the criticised inference
principles. Other examples seem to involve hidden assumptions about the
specific problem which, if made explicit, are nothing but extra information
that defeat the defeasible inference. These considerations will be put in a
wider perspective by reflecting on the nature of defeasible reasoning
principles as principles of justified acceptance rather than `real' logical
inference.


title: Alternative Characterizations for Strong Equivalence of Logic Programs

abstract:
  In this work we present additional results related to the property of strong
equivalence of logic programs. This property asserts that two programs share
the same set of stable models, even under the addition of new rules. As shown
in a recent work by Lifschitz, Pearce and Valverde, strong equivalence can be
simply reduced to equivalence in the logic of Here-and-There (HT). In this
paper we provide two alternatives respectively based on classical logic and
3-valued logic. The former is applicable to general rules, but not for nested
expressions, whereas the latter is applicable for nested expressions but, when
moving to an unrestricted syntax, it generally yields different results from
HT.


title:
Reducing the Computational Requirements of the Differential Quadrature
  Method

abstract:
  This paper shows that the weighting coefficient matrices of the differential
quadrature method (DQM) are centrosymmetric or skew-centrosymmetric if the grid
spacings are symmetric irrespective of whether they are equal or unequal. A new
skew centrosymmetric matrix is also discussed. The application of the
properties of centrosymmetric and skew centrosymmetric matrix can reduce the
computational effort of the DQM for calculations of the inverse, determinant,
eigenvectors and eigenvalues by 75%. This computational advantage are also
demonstrated via several numerical examples.


title: A Note on the DQ Analysis of Anisotropic Plates

abstract:
  Recently, Bert, Wang and Striz [1, 2] applied the differential quadrature
(DQ) and harmonic differential quadrature (HDQ) methods to analyze static and
dynamic behaviors of anisotropic plates. Their studies showed that the methods
were conceptually simple and computationally efficient in comparison to other
numerical techniques. Based on some recent work by the present author [3, 4],
the purpose of this note is to further simplify the formulation effort and
improve computing efficiency in applying the DQ and HDQ methods for these
cases.


title:
A Lyapunov Formulation for Efficient Solution of the Poisson and
  Convection-Diffusion Equations by the Differential Quadrature Method

abstract:
  Civan and Sliepcevich [1, 2] suggested that special matrix solver should be
developed to further reduce the computing effort in applying the differential
quadrature (DQ) method for the Poisson and convection-diffusion equations.
Therefore, the purpose of the present communication is to introduce and apply
the Lyapunov formulation which can be solved much more efficiently than the
Gaussian elimination method. Civan and Sliepcevich [2] first presented DQ
approximate formulas in polynomial form for partial derivatives in
tow-dimensional variable domain. For simplifying formulation effort, Chen et
al. [3] proposed the compact matrix form of these DQ approximate formulas. In
this study, by using these matrix approximate formulas, the DQ formulations for
the Poisson and convection-diffusion equations can be expressed as the Lyapunov
algebraic matrix equation. The formulation effort is simplified, and a simple
and explicit matrix formulation is obtained. A variety of fast algorithms in
the solution of the Lyapunov equation [4-6] can be successfully applied in the
DQ analysis of these two-dimensional problems, and, thus, the computing effort
can be greatly reduced. Finally, we also point out that the present reduction
technique can be easily extended to the three-dimensional cases.


title:
System Description for a Scalable, Fault-Tolerant, Distributed Garbage
  Collector

abstract:
  We describe an efficient and fault-tolerant algorithm for distributed cyclic
garbage collection. The algorithm imposes few requirements on the local
machines and allows for flexibility in the choice of local collector and
distributed acyclic garbage collector to use with it. We have emphasized
reducing the number and size of network messages without sacrificing the
promptness of collection throughout the algorithm. Our proposed collector is a
variant of back tracing to avoid extensive synchronization between machines. We
have added an explicit forward tracing stage to the standard back tracing stage
and designed a tuned heuristic to reduce the total amount of work done by the
collector. Of particular note is the development of fault-tolerant cooperation
between traces and a heuristic that aggressively reduces the set of suspect
objects.


title: Some logics of belief and disbelief

abstract:
  The introduction of explicit notions of rejection, or disbelief, into logics
for knowledge representation can be justified in a number of ways. Motivations
range from the need for versions of negation weaker than classical negation, to
the explicit recording of classic belief contraction operations in the area of
belief change, and the additional levels of expressivity obtained from an
extended version of belief change which includes disbelief contraction. In this
paper we present four logics of disbelief which address some or all of these
intuitions. Soundness and completeness results are supplied and the logics are
compared with respect to applicability and utility.


title:
Iterated revision and the axiom of recovery: a unified treatment via
  epistemic states

abstract:
  The axiom of recovery, while capturing a central intuition regarding belief
change, has been the source of much controversy. We argue briefly against
putative counterexamples to the axiom--while agreeing that some of their
insight deserves to be preserved--and present additional recovery-like axioms
in a framework that uses epistemic states, which encode preferences, as the
object of revisions. This provides a framework in which iterated revision
becomes possible and makes explicit the connection between iterated belief
change and the axiom of recovery. We provide a representation theorem that
connects the semantic conditions that we impose on iterated revision and the
additional syntactical properties mentioned. We also show some interesting
similarities between our framework and that of Darwiche-Pearl. In particular,
we show that the intuitions underlying the controversial (C2) postulate are
captured by the recovery axiom and our recovery-like postulates (the latter can
be seen as weakenings of (C2).


title:
Dual reciprocity BEM and dynamic programming filter for inverse
  elastodynamic problems

abstract:
  This paper presents the first coupling application of the dual reciprocity
BEM (DRBEM) and dynamic programming filter to inverse elastodynamic problem.
The DRBEM is the only BEM method, which does not require domain discretization
for general linear and nonlinear dynamic problems. Since the size of numerical
discretization system has a great effect on the computing effort of recursive
or iterative calculations of inverse analysis, the intrinsic boundary-only
merit of the DRBEM causes a considerable computational saving. On the other
hand, the strengths of the dynamic programming filter lie in its mathematical
simplicity, easy to program and great flexibility in the type, number and
locations of measurements and unknown inputs. The combination of these two
techniques is therefore very attractive for the solution of practical inverse
problems. In this study, the spatial and temporal partial derivatives of the
governing equation are respectively discretized first by the DRBEM and the
precise integration method, and then, by using dynamic programming with
regularization, dynamic load is estimated based on noisy measurements of
velocity and displacement at very few locations. Numerical experiments involved
with the periodic and Heaviside impact load are conducted to demonstrate the
applicability, efficiency and simplicity of this strategy. The affect of noise
level, regularization parameter, and measurement types on the estimation is
also investigated.


title: Well-Founded Argumentation Semantics for Extended Logic Programming

abstract:
  This paper defines an argumentation semantics for extended logic programming
and shows its equivalence to the well-founded semantics with explicit negation.
We set up a general framework in which we extensively compare this semantics to
other argumentation semantics, including those of Dung, and Prakken and Sartor.
We present a general dialectical proof theory for these argumentation
semantics.


title: RBF-based meshless boundary knot method and boundary particle method

abstract:
  This paper is concerned with the two new boundary-type radial basis function
collocation schemes, boundary knot method (BKM) and boundary particle method
(BPM). The BKM is developed based on the dual reciprocity theorem, while the
BPM employs the multiple reciprocity technique. Unlike the method of
fundamental solution, the wto methods use the nonsingular general solutions
instead of singular fundamental solution to circumvent the controversial
artificial boundary outside physical domain. Compared with the boundary element
method, both the BKM and BPM are meshfree, superconvergent, meshfree,
integration free, symmetric, and mathematically simple collocation techniques
for general PDEs. In particular, the BPM does not require any inner nodes for
inhomogeneous problems. In this study, the accuracy and efficiency of the two
methods are numerically demonstrated to some 2D, 3D Helmholtz and
convection-diffusion problems under complicated geometries.


title: Logic Programming with Ordered Disjunction

abstract:
  Logic programs with ordered disjunction (LPODs) combine ideas underlying
Qualitative Choice Logic (Brewka et al. KR 2002) and answer set programming.
Logic programming under answer set semantics is extended with a new connective
called ordered disjunction. The new connective allows us to represent
alternative, ranked options for problem solutions in the heads of rules: A
\times B intuitively means: if possible A, but if A is not possible then at
least B. The semantics of logic programs with ordered disjunction is based on a
preference relation on answer sets. LPODs are useful for applications in design
and configuration and can serve as a basis for qualitative decision making.


title: A meshless, integration-free, and boundary-only RBF technique

abstract:
  Based on the radial basis function (RBF), non-singular general solution and
dual reciprocity method (DRM), this paper presents an inherently meshless,
integration-free, boundary-only RBF collocation techniques for numerical
solution of various partial differential equation systems. The basic ideas
behind this methodology are very mathematically simple. In this study, the RBFs
are employed to approximate the inhomogeneous terms via the DRM, while
non-singular general solution leads to a boundary-only RBF formulation for
homogenous solution. The present scheme is named as the boundary knot method
(BKM) to differentiate it from the other numerical techniques. In particular,
due to the use of nonsingular general solutions rather than singular
fundamental solutions, the BKM is different from the method of fundamental
solution in that the former does no require the artificial boundary and results
in the symmetric system equations under certain conditions. The efficiency and
utility of this new technique are validated through a number of typical
numerical examples. Completeness concern of the BKM due to the only use of
non-singular part of complete fundamental solution is also discussed.


title: Declarative program development in Prolog with GUPU

abstract:
  We present GUPU, a side-effect free environment specialized for programming
courses. It seamlessly guides and supports students during all phases of
program development, covering specification, implementation, and program
debugging. GUPU features several innovations in this area. The specification
phase is supported by reference implementations augmented with diagnostic
facilities. During implementation, immediate feedback from test cases and from
visualization tools helps the programmer's program understanding. A set of
slicing techniques narrows down programming errors. The whole process is guided
by a marking system.


title: Compilation of Propositional Weighted Bases

abstract:
  In this paper, we investigate the extent to which knowledge compilation can
be used to improve inference from propositional weighted bases. We present a
general notion of compilation of a weighted base that is parametrized by any
equivalence--preserving compilation function. Both negative and positive
results are presented. On the one hand, complexity results are identified,
showing that the inference problem from a compiled weighted base is as
difficult as in the general case, when the prime implicates, Horn cover or
renamable Horn cover classes are targeted. On the other hand, we show that the
inference problem becomes tractable whenever DNNF-compilations are used and
clausal queries are considered. Moreover, we show that the set of all preferred
models of a DNNF-compilation of a weighted base can be computed in time
polynomial in the output size. Finally, we sketch how our results can be used
in model-based diagnosis in order to compute the most probable diagnoses of a
system.


title: COINS: a constraint-based interactive solving system

abstract:
  This paper describes the COINS (COnstraint-based INteractive Solving) system:
a conflict-based constraint solver. It helps understanding inconsistencies,
simulates constraint additions and/or retractions (without any propagation),
determines if a given constraint belongs to a conflict and provides diagnosis
tools (e.g. why variable v cannot take value val). COINS also uses
user-friendly representation of conflicts and explanations.


title: Tracing and Explaining Execution of CLP(FD) Programs

abstract:
  Previous work in the area of tracing CLP(FD) programs mainly focuses on
providing information about control of execution and domain modification. In
this paper, we present a trace structure that provides information about
additional important aspects. We incorporate explanations in the trace
structure, i.e. reasons for why certain solver actions occur. Furthermore, we
come up with a format for describing the execution of the filtering algorithms
of global constraints. Some new ideas about the design of the trace are also
presented. For example, we have modeled our trace as a nested block structure
in order to achieve a hierarchical view. Also, new ways about how to represent
and identify different entities such as constraints and domain variables are
presented.