title:
Reliable and Efficient Inference of Bayesian Networks from Sparse Data
  by Statistical Learning Theory

abstract:
  To learn (statistical) dependencies among random variables requires
exponentially large sample size in the number of observed random variables if
any arbitrary joint probability distribution can occur.
  We consider the case that sparse data strongly suggest that the probabilities
can be described by a simple Bayesian network, i.e., by a graph with small
in-degree \Delta. Then this simple law will also explain further data with high
confidence. This is shown by calculating bounds on the VC dimension of the set
of those probability measures that correspond to simple graphs. This allows to
select networks by structural risk minimization and gives reliability bounds on
the error of the estimated joint measure without (in contrast to a previous
paper) any prior assumptions on the set of possible joint measures.
  The complexity for searching the optimal Bayesian networks of in-degree
\Delta increases only polynomially in the number of random varibales for
constant \Delta and the optimal joint measure associated with a given graph can
be found by convex optimization.


title:
Using Simulated Annealing to Calculate the Trembles of Trembling Hand
  Perfection

abstract:
  Within the literature on non-cooperative game theory, there have been a
number of attempts to propose logorithms which will compute Nash equilibria.
Rather than derive a new algorithm, this paper shows that the family of
algorithms known as Markov chain Monte Carlo (MCMC) can be used to calculate
Nash equilibria. MCMC is a type of Monte Carlo simulation that relies on Markov
chains to ensure its regularity conditions. MCMC has been widely used
throughout the statistics and optimization literature, where variants of this
algorithm are known as simulated annealing. This paper shows that there is
interesting connection between the trembles that underlie the functioning of
this algorithm and the type of Nash refinement known as trembling hand
perfection.


title: Enumerating planar locally finite Cayley graphs

abstract:
  We characterize the set of planar locally finite Cayley graphs, and give a
finite representation of these graphs by a special kind of finite state
automata called labeling schemes. As a result, we are able to enumerate and
describe all planar locally finite Cayley graphs of a given degree. This
analysis allows us to solve the problem of decision of the locally finite
planarity for a word-problem-decidable presentation.
  Keywords: vertex-transitive, Cayley graph, planar graph, tiling, labeling
scheme


title: Using Propagation for Solving Complex Arithmetic Constraints

abstract:
  Solving a system of nonlinear inequalities is an important problem for which
conventional numerical analysis has no satisfactory method. With a
box-consistency algorithm one can compute a cover for the solution set to
arbitrarily close approximation. Because of difficulties in the use of
propagation for complex arithmetic expressions, box consistency is computed
with interval arithmetic. In this paper we present theorems that support a
simple modification of propagation that allows complex arithmetic expressions
to be handled efficiently. The version of box consistency that is obtained in
this way is stronger than when interval arithmetic is used.


title: Building a Test Collection for Speech-Driven Web Retrieval

abstract:
  This paper describes a test collection (benchmark data) for retrieval systems
driven by spoken queries. This collection was produced in the subtask of the
NTCIR-3 Web retrieval task, which was performed in a TREC-style evaluation
workshop. The search topics and document collection for the Web retrieval task
were used to produce spoken queries and language models for speech recognition,
respectively. We used this collection to evaluate the performance of our
retrieval system. Experimental results showed that (a) the use of target
documents for language modeling and (b) enhancement of the vocabulary size in
speech recognition were effective in improving the system performance.


title: Threshold values of Random K-SAT from the cavity method

abstract:
  Using the cavity equations of
\cite{mezard:parisi:zecchina:02,mezard:zecchina:02}, we derive the various
threshold values for the number of clauses per variable of the random
$K$-satisfiability problem, generalizing the previous results to $K \ge 4$. We
also give an analytic solution of the equations, and some closed expressions
for these thresholds, in an expansion around large $K$. The stability of the
solution is also computed. For any $K$, the satisfiability threshold is found
to be in the stable region of the solution, which adds further credit to the
conjecture that this computation gives the exact satisfiability threshold.


title: A Cross-media Retrieval System for Lecture Videos

abstract:
  We propose a cross-media lecture-on-demand system, in which users can
selectively view specific segments of lecture videos by submitting text
queries. Users can easily formulate queries by using the textbook associated
with a target lecture, even if they cannot come up with effective keywords. Our
system extracts the audio track from a target lecture video, generates a
transcription by large vocabulary continuous speech recognition, and produces a
text index. Experimental results showed that by adapting speech recognition to
the topic of the lecture, the recognition accuracy increased and the retrieval
accuracy was comparable with that obtained by human transcription.


title: Proposed Specification of a Distributed XML-Query Network

abstract:
  W3C's XML-Query language offers a powerful instrument for information
retrieval on XML repositories. This article describes an implementation of this
retrieval in a real world's scenario. Distributed XML-Query processing reduces
load on every single attending node to an acceptable level. The network allows
every participant to control their computing load themselves. Furthermore
XML-repositories may stay at the rights holder, so every Data-Provider can
decide, whether to process critical queries or not. If Data-Providers keep
redundant information, this distributed network improves reliability of
information with duplicates removed.


title: Efficient Algorithms for Citation Network Analysis

abstract:
  In the paper very efficient, linear in number of arcs, algorithms for
determining Hummon and Doreian's arc weights SPLC and SPNP in citation network
are proposed, and some theoretical properties of these weights are presented.
The nonacyclicity problem in citation networks is discussed. An approach to
identify on the basis of arc weights an important small subnetwork is proposed
and illustrated on the citation networks of SOM (self organizing maps)
literature and US patents.


title: Results on the quantitative mu-calculus qMu

abstract:
  The mu-calculus is a powerful tool for specifying and verifying transition
systems, including those with both demonic and angelic choice; its quantitative
generalisation qMu extends that to probabilistic choice.
  We show that for a finite-state system the logical interpretation of qMu, via
fixed-points in a domain of real-valued functions into [0,1], is equivalent to
an operational interpretation given as a turn-based gambling game between two
players.
  The logical interpretation provides direct access to axioms, laws and
meta-theorems. The operational, game- based interpretation aids the intuition
and continues in the more general context to provide a surprisingly practical
specification tool.
  A corollary of our proofs is an extension of Everett's singly-nested games
result in the finite turn-based case: we prove well-definedness of the minimax
value, and existence of fixed memoriless strategies, for all qMu
games/formulae, of arbitrary (including alternating) nesting structure.


title: Evidential Force Aggregation

abstract:
  In this paper we develop an evidential force aggregation method intended for
classification of evidential intelligence into recognized force structures. We
assume that the intelligence has already been partitioned into clusters and use
the classification method individually in each cluster. The classification is
based on a measure of fitness between template and fused intelligence that
makes it possible to handle intelligence reports with multiple nonspecific and
uncertain propositions. With this measure we can aggregate on a level-by-level
basis, starting from general intelligence to achieve a complete force structure
with recognized units on all hierarchical levels.


title:
A thought experiment on Quantum Mechanics and Distributed Failure
  Detection

abstract:
  One of the biggest problems in current distributed systems is that presented
by one machine attempting to determine the liveness of another in a timely
manner. Unfortunately, the symptoms exhibited by a failed machine can also be
the result of other causes, e.g., an overloaded machine or network which drops
messages, making it impossible to detect a machine failure with cetainty until
that machine recovers. This is a well understood problem and one which has led
to a large body of research into failure suspectors: since it is not possible
to detect a failure, the best one can do is suspect a failure and program
accordingly. However, one machine's suspicions may not be the same as
another's; therefore, these algorithms spend a considerable effort in ensuring
a consistent view among all available machines of who is suspects of being
failed. This paper describes a thought experiment on how quantum mechanics may
be used to provide a failure detector that is guaranteed to give both accurate
and instantaneous information about the liveness of machines, no matter the
distances involved.


title:
Proceedings of the Fifth International Workshop on Automated Debugging
  (AADEBUG 2003)

abstract:
  Over the past decades automated debugging has seen major achievements.
However, as debugging is by necessity attached to particular programming
paradigms, the results are scattered. To alleviate this problem, the Automated
and Algorithmic Debugging workshop (AADEBUG for short) was organised in 1993 in
Link"oping (Sweden). As this workshop proved to be successful, subsequent
workshops have been organised in 1995 (Saint-Malo, France), 1997 (again in
Link"oping, Sweden) and 2000 (Munich, Germany). In 2003, the workshop is
organised in Ghent, Belgium, the proceedings of which you are reading right
now.


title: cTI: A constraint-based termination inference tool for ISO-Prolog

abstract:
  We present cTI, the first system for universal left-termination inference of
logic programs. Termination inference generalizes termination analysis and
checking. Traditionally, a termination analyzer tries to prove that a given
class of queries terminates. This class must be provided to the system, for
instance by means of user annotations. Moreover, the analysis must be redone
every time the class of queries of interest is updated. Termination inference,
in contrast, requires neither user annotations nor recomputation. In this
approach, terminating classes for all predicates are inferred at once. We
describe the architecture of cTI and report an extensive experimental
evaluation of the system covering many classical examples from the logic
programming termination literature and several Prolog programs of respectable
size and complexity.


title: Instrumenting self-modifying code

abstract:
  Adding small code snippets at key points to existing code fragments is called
instrumentation. It is an established technique to debug certain otherwise hard
to solve faults, such as memory management issues and data races. Dynamic
instrumentation can already be used to analyse code which is loaded or even
generated at run time.With the advent of environments such as the Java Virtual
Machine with optimizing Just-In-Time compilers, a new obstacle arises:
self-modifying code. In order to instrument this kind of code correctly, one
must be able to detect modifications and adapt the instrumentation code
accordingly, preferably without incurring a high penalty speedwise. In this
paper we propose an innovative technique that uses the hardware page protection
mechanism of modern processors to detect such modifications. We also show how
an instrumentor can adapt the instrumented version depending on the kind of
modificiations as well as an experimental evaluation of said techniques.


title: Model-Based Debugging using Multiple Abstract Models

abstract:
  This paper introduces an automatic debugging framework that relies on
model-based reasoning techniques to locate faults in programs. In particular,
model-based diagnosis, together with an abstract interpretation based conflict
detection mechanism is used to derive diagnoses, which correspond to possible
faults in programs. Design information and partial specifications are applied
to guide a model revision process, which allows for automatic detection and
correction of structural faults.


title: Timestamp Based Execution Control for C and Java Programs

abstract:
  Many programmers have had to deal with an overwritten variable resulting for
example from an aliasing problem. The culprit is obviously the last
write-access to that memory location before the manifestation of the bug. The
usual technique for removing such bugs starts with the debugger by (1) finding
the last write and (2) moving the control point of execution back to that time
by re-executing the program from the beginning. We wish to automate this. Step
(2) is easy if we can somehow mark the last write found in step (1) and control
the execution-point to move it back to this time.
  In this paper we propose a new concept, position, that is, a point in the
program execution trace, as needed for step (2) above. The position enables
debuggers to automate the control of program execution to support common
debugging activities. We have implemented position in C by modifying GCC and in
Java with a bytecode transformer. Measurements show that position can be
provided with an acceptable amount of overhead.


title: Towards declarative diagnosis of constraint programs over finite domains

abstract:
  The paper proposes a theoretical approach of the debugging of constraint
programs based on a notion of explanation tree. The proposed approach is an
attempt to adapt algorithmic debugging to constraint programming. In this
theoretical framework for domain reduction, explanations are proof trees
explaining value removals. These proof trees are defined by inductive
definitions which express the removals of values as consequences of other value
removals. Explanations may be considered as the essence of constraint
programming. They are a declarative view of the computation trace. The
diagnosis consists in locating an error in an explanation rooted by a symptom.


title: Lower bounds for predecessor searching in the cell probe model

abstract:
  We consider a fundamental problem in data structures, static predecessor
searching: Given a subset S of size n from the universe [m], store S so that
queries of the form "What is the predecessor of x in S?" can be answered
efficiently. We study this problem in the cell probe model introduced by Yao.
Recently, Beame and Fich obtained optimal bounds on the number of probes needed
by any deterministic query scheme if the associated storage scheme uses only
n^{O(1)} cells of word size (\log m)^{O(1)} bits. We give a new lower bound
proof for this problem that matches the bounds of Beame and Fich. Our lower
bound proof has the following advantages: it works for randomised query schemes
too, while Beame and Fich's proof works for deterministic query schemes only.
It also extends to `quantum address-only' query schemes that we define in this
paper, and is simpler than Beame and Fich's proof. We prove our lower bound
using the round elimination approach of Miltersen, Nisan, Safra and Wigderson.
Using tools from information theory, we prove a strong round elimination lemma
for communication complexity that enables us to obtain a tight lower bound for
the predecessor problem. Our strong round elimination lemma also extends to
quantum communication complexity. We also use our round elimination lemma to
obtain a rounds versus communication tradeoff for the `greater-than' problem,
improving on the tradeoff in Miltersen et al. We believe that our round
elimination lemma is of independent interest and should have other
applications.


title:
Measuring Praise and Criticism: Inference of Semantic Orientation from
  Association

abstract:
  The evaluative character of a word is called its semantic orientation.
Positive semantic orientation indicates praise (e.g., "honest", "intrepid") and
negative semantic orientation indicates criticism (e.g., "disturbing",
"superfluous"). Semantic orientation varies in both direction (positive or
negative) and degree (mild to strong). An automated system for measuring
semantic orientation would have application in text classification, text
filtering, tracking opinions in online discussions, analysis of survey
responses, and automated chat systems (chatbots). This paper introduces a
method for inferring the semantic orientation of a word from its statistical
association with a set of positive and negative paradigm words. Two instances
of this approach are evaluated, based on two different statistical measures of
word association: pointwise mutual information (PMI) and latent semantic
analysis (LSA). The method is experimentally tested with 3,596 words (including
adjectives, adverbs, nouns, and verbs) that have been manually labeled positive
(1,614 words) and negative (1,982 words). The method attains an accuracy of
82.8% on the full test set, but the accuracy rises above 95% when the algorithm
is allowed to abstain from classifying mild words.


title:
Combining Independent Modules to Solve Multiple-choice Synonym and
  Analogy Problems

abstract:
  Existing statistical approaches to natural language problems are very coarse
approximations to the true complexity of language processing. As such, no
single technique will be best for all problem instances. Many researchers are
examining ensemble methods that combine the output of successful, separately
developed modules to create more accurate solutions. This paper examines three
merging rules for combining probability distributions: the well known mixture
rule, the logarithmic rule, and a novel product rule. These rules were applied
with state-of-the-art results to two problems commonly used to assess human
mastery of lexical semantics -- synonym questions and analogy questions. All
three merging rules result in ensembles that are more accurate than any of
their component modules. The differences among the three rules are not
statistically significant, but it is suggestive that the popular mixture rule
is not the best rule for either of the two problems.


title:
A Neural Network Assembly Memory Model Based on an Optimal Binary Signal
  Detection Theory

abstract:
  A ternary/binary data coding algorithm and conditions under which Hopfield
networks implement optimal convolutional or Hamming decoding algorithms has
been described. Using the coding/decoding approach (an optimal Binary Signal
Detection Theory, BSDT) introduced a Neural Network Assembly Memory Model
(NNAMM) is built. The model provides optimal (the best) basic memory
performance and demands the use of a new memory unit architecture with
two-layer Hopfield network, N-channel time gate, auxiliary reference memory,
and two nested feedback loops. NNAMM explicitly describes the dependence on
time of a memory trace retrieval, gives a possibility of metamemory simulation,
generalized knowledge representation, and distinct description of conscious and
unconscious mental processes. A model of smallest inseparable part or an "atom"
of consciousness is also defined. The NNAMM's neurobiological backgrounds and
its applications to solving some interdisciplinary problems are shortly
discussed. BSDT could implement the "best neural code" used in nervous tissues
of animals and humans.


title: Postmortem Object Type Identification

abstract:
  This paper presents a novel technique for the automatic type identification
of arbitrary memory objects from a memory dump. Our motivating application is
debugging memory corruption problems in optimized, production systems -- a
problem domain largely unserved by extant methodologies. We describe our
algorithm as applicable to any typed language, and we discuss it with respect
to the formidable obstacles posed by C. We describe the heuristics that we have
developed to overcome these difficulties and achieve effective type
identification on C-based systems. We further describe the implementation of
our heuristics on one C-based system -- the Solaris operating system kernel --
and describe the extensions that we have added to the Solaris postmortem
debugger to allow for postmortem type identification. We show that our
implementation yields a sufficiently high rate of type identification to be
useful for debugging memory corruption problems. Finally, we discuss some of
the novel automated debugging mechanisms that can be layered upon postmortem
type identification.


title: A novel evolutionary formulation of the maximum independent set problem

abstract:
  We introduce a novel evolutionary formulation of the problem of finding a
maximum independent set of a graph. The new formulation is based on the
relationship that exists between a graph's independence number and its acyclic
orientations. It views such orientations as individuals and evolves them with
the aid of evolutionary operators that are very heavily based on the structure
of the graph and its acyclic orientations. The resulting heuristic has been
tested on some of the Second DIMACS Implementation Challenge benchmark graphs,
and has been found to be competitive when compared to several of the other
heuristics that have also been tested on those graphs.


title: Two novel evolutionary formulations of the graph coloring problem

abstract:
  We introduce two novel evolutionary formulations of the problem of coloring
the nodes of a graph. The first formulation is based on the relationship that
exists between a graph's chromatic number and its acyclic orientations. It
views such orientations as individuals and evolves them with the aid of
evolutionary operators that are very heavily based on the structure of the
graph and its acyclic orientations. The second formulation, unlike the first
one, does not tackle one graph at a time, but rather aims at evolving a
`program' to color all graphs belonging to a class whose members all have the
same number of nodes and other common attributes. The heuristics that result
from these formulations have been tested on some of the Second DIMACS
Implementation Challenge benchmark graphs, and have been found to be
competitive when compared to the several other heuristics that have also been
tested on those graphs.


title: A distributed algorithm to find k-dominating sets

abstract:
  We consider a connected undirected graph $G(n,m)$ with $n$ nodes and $m$
edges. A $k$-dominating set $D$ in $G$ is a set of nodes having the property
that every node in $G$ is at most $k$ edges away from at least one node in $D$.
Finding a $k$-dominating set of minimum size is NP-hard. We give a new
synchronous distributed algorithm to find a $k$-dominating set in $G$ of size
no greater than $\lfloor n/(k+1)\rfloor$. Our algorithm requires $O(k\log^*n)$
time and $O(m\log k+n\log k\log^*n)$ messages to run. It has the same time
complexity as the best currently known algorithm, but improves on that
algorithm's message complexity and is, in addition, conceptually simpler.


title: Fast Verification of Convexity of Piecewise-linear Surfaces

abstract:
  We show that a realization of a closed connected PL-manifold of dimension n-1
in n-dimensional Euclidean space (n>2) is the boundary of a convex polyhedron
(finite or infinite) if and only if the interior of each (n-3)-face has a
point, which has a neighborhood lying on the boundary of an n-dimensional
convex body. No initial assumptions about the topology or orientability of the
input surface are made. The theorem is derived from a refinement and
generalization of Van Heijenoort's theorem on locally convex manifolds to
spherical spaces. Our convexity criterion for PL-manifolds implies an easy
polynomial-time algorithm for checking convexity of a given PL-surface in
n-dimensional Euclidean or spherical space, n>2. The algorithm is worst case
optimal with respect to both the number of operations and the algebraic degree.
The algorithm works under significantly weaker assumptions and is easier to
implement than convexity verification algorithms suggested by Mehlhorn et al
(1996-1999), and Devillers et al.(1998). A paradigm of approximate convexity is
suggested and a simplified algorithm of smaller degree and complexity is
suggested for approximate floating point convexity verification.


title: On reducing the complexity of matrix clocks

abstract:
  Matrix clocks are a generalization of the notion of vector clocks that allows
the local representation of causal precedence to reach into an asynchronous
distributed computation's past with depth $x$, where $x\ge 1$ is an integer.
Maintaining matrix clocks correctly in a system of $n$ nodes requires that
everymessage be accompanied by $O(n^x)$ numbers, which reflects an exponential
dependency of the complexity of matrix clocks upon the desired depth $x$. We
introduce a novel type of matrix clock, one that requires only $nx$ numbers to
be attached to each message while maintaining what for many applications may be
the most significant portion of the information that the original matrix clock
carries. In order to illustrate the new clock's applicability, we demonstrate
its use in the monitoring of certain resource-sharing computations.


title: Finding approximate palindromes in strings

abstract:
  We introduce a novel definition of approximate palindromes in strings, and
provide an algorithm to find all maximal approximate palindromes in a string
with up to $k$ errors. Our definition is based on the usual edit operations of
approximate pattern matching, and the algorithm we give, for a string of size
$n$ on a fixed alphabet, runs in $O(k^2 n)$ time. We also discuss two
implementation-related improvements to the algorithm, and demonstrate their
efficacy in practice by means of both experiments and an average-case analysis.


title: The combinatorics of resource sharing

abstract:
  We discuss general models of resource-sharing computations, with emphasis on
the combinatorial structures and concepts that underlie the various deadlock
models that have been proposed, the design of algorithms and deadlock-handling
policies, and concurrency issues. These structures are mostly graph-theoretic
in nature, or partially ordered sets for the establishment of priorities among
processes and acquisition orders on resources. We also discuss graph-coloring
concepts as they relate to resource sharing.


title:
A uniform approach to constraint-solving for lists, multisets, compact
  lists, and sets

abstract:
  Lists, multisets, and sets are well-known data structures whose usefulness is
widely recognized in various areas of Computer Science. These data structures
have been analyzed from an axiomatic point of view with a parametric approach
in (*) where the relevant unification algorithms have been developed. In this
paper we extend these results considering more general constraints including
not only equality but also membership constraints as well as their negative
counterparts.
  (*) A. Dovier, A. Policriti, and G. Rossi. A uniform axiomatic view of lists,
multisets, and sets, and the relevant unification algorithms. Fundamenta
Informaticae, 36(2/3):201--234, 1998.


title:
The Liar and Related Paradoxes: Fuzzy Truth Value Assignment for
  Collections of Self-Referential Sentences

abstract:
  We study self-referential sentences of the type related to the Liar paradox.
In particular, we consider the problem of assigning consistent fuzzy truth
values to collections of self-referential sentences. We show that the problem
can be reduced to the solution of a system of nonlinear equations. Furthermore,
we prove that, under mild conditions, such a system always has a solution (i.e.
a consistent truth value assignment) and that, for a particular implementation
of logical ``and'', ``or'' and ``negation'', the ``mid-point'' solution is
always consistent. Next we turn to computational issues and present several
truth-value assignment algorithms; we argue that these algorithms can be
understood as generalized sequential reasoning. In an Appendix we present a
large number of examples of self-referential collections (including the Liar
and the Strengthened Liar), we formulate the corresponding truth value
equations and solve them analytically and/ or numerically.


title: Causes and Effects in Computer Programs

abstract:
  Debugging is commonly understood as finding and fixing the cause of a
problem. But what does ``cause'' mean? How can we find causes? How can we prove
that a cause is a cause--or even ``the'' cause? This paper defines common terms
in debugging, highlights the principal techniques, their capabilities and
limitations.


title:
Goedel Machines: Self-Referential Universal Problem Solvers Making
  Provably Optimal Self-Improvements

abstract:
  We present the first class of mathematically rigorous, general, fully
self-referential, self-improving, optimally efficient problem solvers. Inspired
by Kurt Goedel's celebrated self-referential formulas (1931), such a problem
solver rewrites any part of its own code as soon as it has found a proof that
the rewrite is useful, where the problem-dependent utility function and the
hardware and the entire initial code are described by axioms encoded in an
initial proof searcher which is also part of the initial code. The searcher
systematically and efficiently tests computable proof techniques (programs
whose outputs are proofs) until it finds a provably useful, computable
self-rewrite. We show that such a self-rewrite is globally optimal - no local
maxima! - since the code first had to prove that it is not useful to continue
the proof search for alternative self-rewrites. Unlike previous
non-self-referential methods based on hardwired proof searchers, ours not only
boasts an optimal order of complexity but can optimally reduce any slowdowns
hidden by the O()-notation, provided the utility of such speed-ups is provable
at all.


title: Control and Debugging of Distributed Programs Using Fiddle

abstract:
  The main goal of Fiddle, a distributed debugging engine, is to provide a
flexible platform for developing debugging tools. Fiddle provides a layered set
of interfaces with a minimal set of debugging functionalities, for the
inspection and control of distributed and multi-threaded applications.
  This paper illustrates how Fiddle is used to support integrated testing and
debugging. The approach described is based on a tool, called Deipa, that
interprets sequences of commands read from an input file, generated by an
independent testing tool. Deipa acts as a Fiddle client, in order to enforce
specific execution paths in a distributed PVM program. Other Fiddle clients may
be used along with Deipa for the fine debugging at process level. Fiddle and
Deipa functionalities and architectures are described, and a working example
shows a step-by-step application of these tools.


title:
Computing Igusa's Local Zeta Functions of Univariate Polynomials, and
  Linear Feedback Shift Registers

abstract:
  We give a polynomial time algorithm for computing the Igusa local zeta
function $Z(s,f)$ attached to a polynomial $f(x)\in \QTR{Bbb}{Z}[x]$, in one
variable, with splitting field $\QTR{Bbb}{Q}$, and a prime number $p$. We also
propose a new class of Linear Feedback Shift Registers based on the computation
of Igusa's local zeta function.


title: New Lattice Based Cryptographic Constructions

abstract:
  We introduce the use of Fourier analysis on lattices as an integral part of a
lattice based construction. The tools we develop provide an elegant description
of certain Gaussian distributions around lattice points. Our results include
two cryptographic constructions which are based on the worst-case hardness of
the unique shortest vector problem. The main result is a new public key
cryptosystem whose security guarantee is considerably stronger than previous
results ($O(n^{1.5})$ instead of $O(n^7)$). This provides the first alternative
to Ajtai and Dwork's original 1996 cryptosystem. Our second result is a family
of collision resistant hash functions which, apart from improving the security
in terms of the unique shortest vector problem, is also the first example of an
analysis which is not based on Ajtai's iterative step. Surprisingly, both
results are derived from one theorem which presents two indistinguishable
distributions on the segment $[0,1)$. It seems that this theorem can have
further applications and as an example we mention how it can be used to solve
an open problem related to quantum computation.


title: Minimal DFAs for Testing Divisibility

abstract:
  We present and prove a theorem answering the question "how many states does a
minimal deterministic finite automaton (DFA) that recognizes the set of base-b
numbers divisible by k have?"


title: A Hierarchical Situation Calculus

abstract:
  A situation calculus is presented that provides a solution to the frame
problem for hierarchical situations, that is, situations that have a modular
structure in which parts of the situation behave in a relatively independent
manner. This situation calculus is given in a relational, functional, and modal
logic form. Each form permits both a single level hierarchy or a multiple level
hierarchy, giving six versions of the formalism in all, and a number of
sub-versions of these. For multiple level hierarchies, it is possible to give
equations between parts of the situation to impose additional structure on the
problem. This approach is compared to others in the literature.


title:
Active Internet Traffic Filtering: Real-time Response to Denial of
  Service Attacks

abstract:
  Denial of Service (DoS) attacks are one of the most challenging threats to
Internet security. An attacker typically compromises a large number of
vulnerable hosts and uses them to flood the victim's site with malicious
traffic, clogging its tail circuit and interfering with normal traffic. At
present, the network operator of a site under attack has no other resolution
but to respond manually by inserting filters in the appropriate edge routers to
drop attack traffic. However, as DoS attacks become increasingly sophisticated,
manual filter propagation becomes unacceptably slow or even infeasible.
  In this paper, we present Active Internet Traffic Filtering, a new automatic
filter propagation protocol. We argue that this system provides a guaranteed,
significant level of protection against DoS attacks in exchange for a
reasonable, bounded amount of router resources. We also argue that the proposed
system cannot be abused by a malicious node to interfere with normal Internet
operation. Finally, we argue that it retains its efficiency in the face of
continued Internet growth.


title: A mathematical framework for automated bug localization

abstract:
  In this paper, we propose a mathematical framework for automated bug
localization. This framework can be briefly summarized as follows. A program
execution can be represented as a rooted acyclic directed graph. We define an
execution snapshot by a cut-set on the graph. A program state can be regarded
as a conjunction of labels on edges in a cut-set. Then we argue that a
debugging task is a pruning process of the execution graph by using cut-sets. A
pruning algorithm, i.e., a debugging task, is also presented.


title: A Performance Analysis Tool for Nokia Mobile Phone Software

abstract:
  Performance problems are often observed in embedded software systems. The
reasons for poor performance are frequently not obvious. Bottlenecks can occur
in any of the software components along the execution path. Therefore it is
important to instrument and monitor the different components contributing to
the runtime behavior of an embedded software system. Performance analysis tools
can help locate performance bottlenecks in embedded software systems by
monitoring the software's execution and producing easily understandable
performance data. We maintain and further develop a tool for analyzing the
performance of Nokia mobile phone software. The user can select among four
performance analysis reports to be generated: average processor load, processor
utilization, task execution time statistics, and task execution timeline. Each
of these reports provides important information about where execution time is
being spent. The demo will show how the tool helps to identify performance
bottlenecks in Nokia mobile phone software and better understand areas of poor
performance.


title: The Graphics Card as a Streaming Computer

abstract:
  Massive data sets have radically changed our understanding of how to design
efficient algorithms; the streaming paradigm, whether it in terms of number of
passes of an external memory algorithm, or the single pass and limited memory
of a stream algorithm, appears to be the dominant method for coping with large
data.
  A very different kind of massive computation has had the same effect at the
level of the CPU. The most prominent example is that of the computations
performed by a graphics card. The operations themselves are very simple, and
require very little memory, but require the ability to perform many
computations extremely fast and in parallel to whatever degree possible. What
has resulted is a stream processor that is highly optimized for stream
computations. An intriguing side effect of this is the growing use of a
graphics card as a general purpose stream processing engine. In an
ever-increasing array of applications, researchers are discovering that
performing a computation on a graphics card is far faster than performing it on
a CPU, and so are using a GPU as a stream co-processor.


title:
The Wake Up and Report Problem is Time-Equivalent to the Firing Squad
  Synchronization Problem

abstract:
  We consider several problems relating to strongly-connected directed networks
of identical finite-state processors that work synchronously in discrete time
steps. The conceptually simplest of these is the Wake Up and Report Problem;
this is the problem of having a unique "root" processor send a signal to all
other processors in the network and then enter a special "done" state only when
all other processors have received the signal. The most difficult of the
problems we consider is the classic Firing Squad Synchronization Problem; this
is the much-studied problem of achieving macro-synchronization in a network
given micro-synchronization. We show via a complex algorithmic application of
the "snake" data structure first introduced in Even, Litman, and Winkler [ELW],
that these two problems are asymptotically time-equivalent up to a constant
factor. This result leads immediately to the inclusion of several other related
problems into this new asymptotic time-class.


title: Determination of the Topology of a Directed Network

abstract:
  We consider strongly-connected directed networks of identical synchronous,
finite-state processors with in- and out-degree uniformly bounded by a network
constant. Via a straightforward extension of Ostrovsky and Wilkerson's
Backwards Communication Algorithm in [OW], we exhibit a protocol which solves
the Global Topology Determination Problem, the problem of having the root
processor map the global topology of a network of unknown size and topology,
with running time O(ND) where N represents the number of processors and D
represents the diameter of the network. A simple counting argument suffices to
show that the Global Topology Determination Problem has time-complexity Omega(N
logN) which makes the protocol presented asymptotically time-optimal for many
large networks.


title: Using Artificial Intelligence for Model Selection

abstract:
  We apply the optimization algorithm Adaptive Simulated Annealing (ASA) to the
problem of analyzing data on a large population and selecting the best model to
predict that an individual with various traits will have a particular disease.
We compare ASA with traditional forward and backward regression on computer
simulated data. We find that the traditional methods of modeling are better for
smaller data sets whereas a numerically stable ASA seems to perform better on
larger and more complicated data sets.


title: The Lowell Database Research Self Assessment

abstract:
  A group of senior database researchers gathers every few years to assess the
state of database research and to point out problem areas that deserve
additional focus. This report summarizes the discussion and conclusions of the
sixth ad-hoc meeting held May 4-6, 2003 in Lowell, Mass. It observes that
information management continues to be a critical component of most complex
software systems. It recommends that database researchers increase focus on:
integration of text, data, code, and streams; fusion of information from
heterogeneous data sources; reasoning about uncertain data; unsupervised data
mining for interesting correlations; information privacy; and self-adaptation
and repair.


title: Event-based Program Analysis with DeWiz

abstract:
  Due to the increased complexity of parallel and distributed programs,
debugging of them is considered to be the most difficult and time consuming
part of the software lifecycle. Tool support is hence a crucial necessity to
hide complexity from the user. However, most existing tools seem inadequate as
soon as the program under consideration exploits more than a few processors
over a long execution time. This problem is addressed by the novel debugging
tool DeWiz (Debugging Wizard), whose focus lies on scalability. DeWiz has a
modular, scalable architecture, and uses the event graph model as a
representation of the investigated program. DeWiz provides a set of modules,
which can be combined to generate, analyze, and visualize event graph data.
Within this processing pipeline the toolset tries to extract useful
information, which is presented to the user at an arbitrary level of
abstraction. Additionally, DeWiz is a framework, which can be used to easily
implement arbitrary user-defined modules.


title: Poster on MPI application in Computational Fluid Dynamics

abstract:
  Poster-presentation of the paper "Message Passing Fluids: molecules as
processes in parallel computational fluids" held at "EURO PVMMPI 2003"
Congress; the paper is on the proceedings "Recent Advances in Parallel Virtual
Machine and Message Passing Interface", 10th European PVM/MPI User's Group
Meeting, LNCS 2840, Springer-Verlag, Dongarra-Laforenza-Orlando editors, pp.
550-554.


title:
On Interference of Signals and Generalization in Feedforward Neural
  Networks

abstract:
  This paper studies how the generalization ability of neurons can be affected
by mutual processing of different signals. This study is done on the basis of a
feedforward artificial neural network. The mutual processing of signals can
possibly be a good model of patterns in a set generalized by a neural network
and in effect may improve generalization. In this paper it is discussed that
the interference may also cause a highly random generalization. Adaptive
activation functions are discussed as a way of reducing that type of
generalization. A test of a feedforward neural network is performed that shows
the discussed random generalization.


title: Transient Diversity in Multi-Agent Systems

abstract:
  Diversity is an important aspect of highly efficient multi-agent teams. We
introduce the main factors that drive a multi-agent system in either direction
along the diversity scale. A metric for diversity is described, and we
speculate on the concept of transient diversity. Finally, an experiment on
social entropy using a RoboCup simulated soccer team is presented.


title:
Re-Finding Found Things: An Exploratory Study of How Users Re-Find
  Information

abstract:
  The problem of how people find information is studied extensively; however,
the problem of how people organize, re-use, and re-find information that they
have found is not as well understood. Recently, several projects have conducted
in-situ studies to explore how people re-find and re-use information. Here, we
present results and observations from a controlled, laboratory study of
refinding information found on the web.
  Our study was conducted as a collaborative exercise with pairs of
participants. One participant acted as a retriever, helping the other
participant re-find information by telephone. This design allowed us to gain
insight into the strategies that users employed to re-find information, and
into how domain artifacts and contextual information were used to aid the
re-finding process. We also introduced the ability for users to add their own
explicitly artifacts in the form of making annotations on the web pages they
viewed.
  We observe that re-finding often occurs as a two stage, iterative process in
which users first attempt to locate an information source (search), and once
found, begin a process to find the specific information being sought (browse).
Our findings are consistent with research on waypoints; orienteering approaches
to re-finding; and navigation of electronic spaces. Furthermore, we observed
that annotations were utilized extensively, indicating that explicitly added
context by the user can play an important role in re-finding.


title: A Formal Comparison of Visual Web Wrapper Generators

abstract:
  We study the core fragment of the Elog wrapping language used in the Lixto
system (a visual wrapper generator) and formally compare Elog to other wrapping
languages proposed in the literature.


title:
WebTeach in practice: the entrance test to the Engineering faculty in
  Florence

abstract:
  We present the WebTeach project, formed by a web interface to database for
test management, a wiki site for the diffusion of teaching material and student
forums, and a suite for the generation of multiple-choice mathematical quiz
with automatic elaboration of forms. This system has been massively tested for
the entrance test to the Engineering Faculty of the University of Florence,
Italy


title: Effective XML Representation for Spoken Language in Organisations

abstract:
  Spoken Language can be used to provide insights into organisational
processes, unfortunately transcription and coding stages are very time
consuming and expensive. The concept of partial transcription and coding is
proposed in which spoken language is indexed prior to any subsequent
processing. The functional linguistic theory of texture is used to describe the
effects of partial transcription on observational records. The standard used to
encode transcript context and metadata is called CHAT, but a previous XML
schema developed to implement it contains design assumptions that make it
difficult to support partial transcription for example. This paper describes a
more effective XML schema that overcomes many of these problems and is intended
for use in applications that support the rapid development of spoken language
deliverables.


title:
Debugging Tool for Localizing Faulty Processes in Message Passing
  Programs

abstract:
  In message passing programs, once a process terminates with an unexpected
error, the terminated process can propagate the error to the rest of processes
through communication dependencies, resulting in a program failure. Therefore,
to locate faults, developers must identify the group of processes involved in
the original error and faulty processes that activate faults. This paper
presents a novel debugging tool, named MPI-PreDebugger (MPI-PD), for localizing
faulty processes in message passing programs. MPI-PD automatically
distinguishes the original and the propagated errors by checking communication
errors during program execution. If MPI-PD observes any communication errors,
it backtraces communication dependencies and points out potential faulty
processes in a timeline view. We also introduce three case studies, in which
MPI-PD has been shown to play the key role in their debugging. From these
studies, we believe that MPI-PD helps developers to locate faults and allows
them to concentrate in correcting their programs.


title: Debugging Backwards in Time

abstract:
  By recording every state change in the run of a program, it is possible to
present the programmer every bit of information that might be desired.
Essentially, it becomes possible to debug the program by going ``backwards in
time,'' vastly simplifying the process of debugging. An implementation of this
idea, the ``Omniscient Debugger,'' is used to demonstrate its viability and has
been used successfully on a number of large programs. Integration with an event
analysis engine for searching and control is presented. Several small-scale
user studies provide encouraging results. Finally performance issues and
implementation are discussed along with possible optimizations.
  This paper makes three contributions of interest: the concept and technique
of ``going backwards in time,'' the GUI which presents a global view of the
program state and has a formal notion of ``navigation through time,'' and the
integration with an event analyzer.


title: Circle and sphere blending with conformal geometric algebra

abstract:
  Blending schemes based on circles provide smooth `fair' interpolations
between series of points. Here we demonstrate a simple, robust set of
algorithms for performing circle blends for a range of cases. An arbitrary
level of G-continuity can be achieved by simple alterations to the underlying
parameterisation. Our method exploits the computational framework provided by
conformal geometric algebra. This employs a five-dimensional representation of
points in space, in contrast to the four-dimensional representation typically
used in projective geometry. The advantage of the conformal scheme is that
straight lines and circles are treated in a single, unified framework. As a
further illustration of the power of the conformal framework, the basic idea is
extended to the case of sphere blending to interpolate over a surface.


title:
The Study of the Application of a Keywords-based Chatbot System on the
  Teaching of Foreign Languages

abstract:
  This paper reports the findings of a study conducted on the application of an
on-line human-computer dialog system with natural language (chatbot) on the
teaching of foreign languages. A keywords-based human-computer dialog system
makes it possible that the user could chat with the computer using a natural
language, i.e. in English or in German to some extent. So an experiment has
been made using this system online to work as a chat partner with the users
learning the foreign languages. Dialogs between the users and the chatbot are
collected. Findings indicate that the dialogs between the human and the
computer are mostly very short because the user finds the responses from the
computer are mostly repeated and irrelevant with the topics and context and the
program does not understand the language at all. With analysis of the keywords
or pattern-matching mechanism used in this chatbot it can be concluded that
this kind of system can not work as a teaching assistant program in foreign
language learning.


title:
A hierarchical Algorithm to Solve the Shortest Path Problem in Valued
  Graphs

abstract:
  This paper details a new algorithm to solve the shortest path problem in
valued graphs. Its complexity is $O(D \log v)$ where $D$ is the graph diameter
and $v$ its number of vertices. This complexity has to be compared to the one
of the Dijkstra's algorithm, which is $O(e\log v)$ where $e$ is the number of
edges of the graph. This new algorithm lies on a hierarchical representation of
the graph, using radix trees. The performances of this algorithm show a major
improvement over the ones of the algorithms known up to now.


title: Pure Prolog Execution in 21 Rules

abstract:
  A simple mathematical definition of the 4-port model for pure Prolog is
given. The model combines the intuition of ports with a compact representation
of execution state. Forward and backward derivation steps are possible. The
model satisfies a modularity claim, making it suitable for formal reasoning.


title:
Fuzzy Relational Modeling of Cost and Affordability for Advanced
  Technology Manufacturing Environment

abstract:
  Relational representation of knowledge makes it possible to perform all the
computations and decision making in a uniform relational way by means of
special relational compositions called triangle and square products. In this
paper some applications in manufacturing related to cost analysis are
described. Testing fuzzy relational structures for various relational
properties allows us to discover dependencies, hierarchies, similarities, and
equivalences of the attributes characterizing technological processes and
manufactured artifacts in their relationship to costs and performance.
  A brief overview of mathematical aspects of BK-relational products is given
in Appendix 1 together with further references in the literature.


title:
Smoothed Analysis of the Condition Numbers and Growth Factors of
  Matrices

abstract:
  Let $\orig{A}$ be any matrix and let $A$ be a slight random perturbation of
$\orig{A}$. We prove that it is unlikely that $A$ has large condition number.
Using this result, we prove it is unlikely that $A$ has large growth factor
under Gaussian elimination without pivoting. By combining these results, we
bound the smoothed precision needed by Gaussian elimination without pivoting.
Our results improve the average-case analysis of Gaussian elimination without
pivoting performed by Yeung and Chan (SIAM J. Matrix Anal. Appl., 1997).


title: Application of Kullback-Leibler Metric to Speech Recognition

abstract:
  Article discusses the application of Kullback-Leibler divergence to the
recognition of speech signals and suggests three algorithms implementing this
divergence criterion: correlation algorithm, spectral algorithm and filter
algorithm. Discussion covers an approach to the problem of speech variability
and is illustrated with the results of experimental modeling of speech signals.
The article gives a number of recommendations on the choice of appropriate
model parameters and provides a comparison to some other methods of speech
recognition.


title:
Availability Guarantee for Deterministic Replay Starting Points in
  Real-Time Systems

abstract:
  Cyclic debugging requires repeatable executions. As non-deterministic or
real-time systems typically do not have the potential to provide this, special
methods are required. One such method is replay, a process that requires
monitoring of a running system and logging of the data produced by that
monitoring. We shall discuss the process of preparing the replay, a part of the
process that has not been very well described before.


title:
A Monitoring Language for Run Time and Post-Mortem Behavior Analysis and
  Visualization

abstract:
  UFO is a new implementation of FORMAN, a declarative monitoring language, in
which rules are compiled into execution monitors that run on a virtual machine
supported by the Alamo monitor architecture.


title: Generalized Systematic Debugging for Attribute Grammars

abstract:
  Attribute grammars (AGs) are known to be a useful formalism for semantic
analysis and translation. However, debugging AGs is complex owing to inherent
difficulties of AGs, such as recursive grammar structure and attribute
dependency. In this paper, a new systematic method of debugging AGs is
proposed. Our approach is, in principle, based on previously proposed
algorithmic debugging of AGs, but is more general. This easily enables
integration of various query-based systematic debugging methods, including the
slice-based method. The proposed method has been implemented in Aki, a debugger
for AG description. We evaluated our new approach experimentally using Aki,
which demonstrates the usability of our debugging method.


title: On the continuous Fermat-Weber problem

abstract:
  We give the first exact algorithmic study of facility location problems that
deal with finding a median for a continuum of demand points. In particular, we
consider versions of the ``continuous k-median (Fermat-Weber) problem'' where
the goal is to select one or more center points that minimize the average
distance to a set of points in a demand region. In such problems, the average
is computed as an integral over the relevant region, versus the usual discrete
sum of distances. The resulting facility location problems are inherently
geometric, requiring analysis techniques of computational geometry. We provide
polynomial-time algorithms for various versions of the L1 1-median
(Fermat-Weber) problem. We also consider the multiple-center version of the L1
k-median problem, which we prove is NP-hard for large k.


title: Providing Diversity in K-Nearest Neighbor Query Results

abstract:
  Given a point query Q in multi-dimensional space, K-Nearest Neighbor (KNN)
queries return the K closest answers according to given distance metric in the
database with respect to Q. In this scenario, it is possible that a majority of
the answers may be very similar to some other, especially when the data has
clusters. For a variety of applications, such homogeneous result sets may not
add value to the user. In this paper, we consider the problem of providing
diversity in the results of KNN queries, that is, to produce the closest result
set such that each answer is sufficiently different from the rest. We first
propose a user-tunable definition of diversity, and then present an algorithm,
called MOTLEY, for producing a diverse result set as per this definition.
Through a detailed experimental evaluation on real and synthetic data, we show
that MOTLEY can produce diverse result sets by reading only a small fraction of
the tuples in the database. Further, it imposes no additional overhead on the
evaluation of traditional KNN queries, thereby providing a seamless interface
between diversity and distance.


title: Optimizing Noncontiguous Accesses in MPI-IO

abstract:
  The I/O access patterns of many parallel applications consist of accesses to
a large number of small, noncontiguous pieces of data. If an application's I/O
needs are met by making many small, distinct I/O requests, however, the I/O
performance degrades drastically. To avoid this problem, MPI-IO allows users to
access noncontiguous data with a single I/O function call, unlike in Unix I/O.
In this paper, we explain how critical this feature of MPI-IO is for high
performance and how it enables implementations to perform optimizations. We
first provide a classification of the different ways of expressing an
application's I/O needs in MPI-IO--we classify them into four levels, called
level~0 through level~3. We demonstrate that, for applications with
noncontiguous access patterns, the I/O performance improves dramatically if
users write their applications to make level-3 requests (noncontiguous,
collective) rather than level-0 requests (Unix style). We then describe how our
MPI-IO implementation, ROMIO, delivers high performance for noncontiguous
requests. We explain in detail the two key optimizations ROMIO performs: data
sieving for noncontiguous requests from one process and collective I/O for
noncontiguous requests from multiple processes. We describe how we have
implemented these optimizations portably on multiple machines and file systems,
controlled their memory requirements, and also achieved high performance. We
demonstrate the performance and portability with performance results for three
applications--an astrophysics-application template (DIST3D), the NAS BTIO
benchmark, and an unstructured code (UNSTRUC)--on five different parallel
machines: HP Exemplar, IBM SP, Intel Paragon, NEC SX-4, and SGI Origin2000.


title: A Particular Bug Trap: Execution Replay Using Virtual Machines

abstract:
  Execution-replay (ER) is well known in the literature but has been restricted
to special system architectures for many years. Improved hardware resources and
the maturity of virtual machine technology promise to make ER useful for a
broader range of development projects.
  This paper describes an approach to create a practical, generic ER
infrastructure for desktop PC systems using virtual machine technology. In the
created VM environment arbitrary application programs will run and be replayed
unmodified, neither instrumentation nor recompilation are required.


title: A weak definition of Delaunay triangulation

abstract:
  We show that the traditional criterion for a simplex to belong to the
Delaunay triangulation of a point set is equivalent to a criterion which is a
priori weaker. The argument is quite general; as well as the classical
Euclidean case, it applies to hyperbolic and hemispherical geometries and to
Edelsbrunner's weighted Delaunay triangulation. In spherical geometry, we
establish a similar theorem under a genericity condition. The weak definition
finds natural application in the problem of approximating a point-cloud data
set with a simplical complex.


title:
A combinatorial characterization of higher-dimensional orthogonal
  packing

abstract:
  Higher-dimensional orthogonal packing problems have a wide range of practical
applications, including packing, cutting, and scheduling. Previous efforts for
exact algorithms have been unable to avoid structural problems that appear for
instances in two- or higher-dimensional space. We present a new approach for
modeling packings, using a graph-theoretical characterization of feasible
packings. Our characterization allows it to deal with classes of packings that
share a certain combinatorial structure, instead of having to consider one
packing at a time. In addition, we can make use of elegant algorithmic
properties of certain classes of graphs. This allows our characterization to be
the basis for a successful branch-and-bound framework.
  This is the first in a series of papers describing new approaches to
higher-dimensional packing.


title: A Hash of Hash Functions

abstract:
  In this paper, we present a general review of hash functions in a
cryptographic sense. We give special emphasis on some particular topics such as
cipher block chaining message authentication code (CBC MAC) and its variants.
This paper also broadens the information given in some well known surveys, by
including more details on block-cipher based hash functions and security of
different hash schemes.


title: Minimizing the stabbing number of matchings, trees, and triangulations

abstract:
  The (axis-parallel) stabbing number of a given set of line segments is the
maximum number of segments that can be intersected by any one (axis-parallel)
line. This paper deals with finding perfect matchings, spanning trees, or
triangulations of minimum stabbing number for a given set of points. The
complexity of these problems has been a long-standing open question; in fact,
it is one of the original 30 outstanding open problems in computational
geometry on the list by Demaine, Mitchell, and O'Rourke. The answer we provide
is negative for a number of minimum stabbing problems by showing them NP-hard
by means of a general proof technique. It implies non-trivial lower bounds on
the approximability. On the positive side we propose a cut-based integer
programming formulation for minimizing the stabbing number of matchings and
spanning trees. We obtain lower bounds (in polynomial time) from the
corresponding linear programming relaxations, and show that an optimal
fractional solution always contains an edge of at least constant weight. This
result constitutes a crucial step towards a constant-factor approximation via
an iterated rounding scheme. In computational experiments we demonstrate that
our approach allows for actually solving problems with up to several hundred
points optimally or near-optimally.


title: Supporting Exploratory Queries in Database Centric Web Applications

abstract:
  Users of database-centric Web applications, especially in the e-commerce
domain, often resort to exploratory ``trial-and-error'' queries since the
underlying data space is huge and unfamiliar, and there are several
alternatives for search attributes in this space. For example, scouting for
cheap airfares typically involves posing multiple queries, varying flight
times, dates, and airport locations. Exploratory queries are problematic from
the perspective of both the user and the server. For the database server, it
results in a drastic reduction in effective throughput since much of the
processing is duplicated in each successive query. For the client, it results
in a marked increase in response times, especially when accessing the service
through wireless channels.
  In this paper, we investigate the design of automated techniques to minimize
the need for repetitive exploratory queries. Specifically, we present SAUNA, a
server-side query relaxation algorithm that, given the user's initial range
query and a desired cardinality for the answer set, produces a relaxed query
that is expected to contain the required number of answers. The algorithm
incorporates a range-query-specific distance metric that is weighted to produce
relaxed queries of a desired shape (e.g. aspect ratio preserving), and utilizes
multi-dimensional histograms for query size estimation. A detailed performance
evaluation of SAUNA over a variety of multi-dimensional data sets indicates
that its relaxed queries can significantly reduce the costs associated with
exploratory query processing.


title:
Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time $O
  (m^{1.31})$

abstract:
  We present a linear-system solver that, given an $n$-by-$n$ symmetric
positive semi-definite, diagonally dominant matrix $A$ with $m$ non-zero
entries and an $n$-vector $\bb $, produces a vector $\xxt$ within relative
distance $\epsilon$ of the solution to $A \xx = \bb$ in time $O (m^{1.31} \log
(n \kappa_{f} (A)/\epsilon)^{O (1)})$, where $\kappa_{f} (A)$ is the log of the
ratio of the largest to smallest non-zero eigenvalue of $A$. In particular,
$\log (\kappa_{f} (A)) = O (b \log n)$, where $b$ is the logarithm of the ratio
of the largest to smallest non-zero entry of $A$. If the graph of $A$ has genus
$m^{2\theta}$ or does not have a $K_{m^{\theta}} $ minor, then the exponent of
$m$ can be improved to the minimum of $1 + 5 \theta $ and $(9/8) (1+\theta)$.
The key contribution of our work is an extension of Vaidya's techniques for
constructing and analyzing combinatorial preconditioners.


title: Maximum dispersion and geometric maximum weight cliques

abstract:
  We consider a facility location problem, where the objective is to
``disperse'' a number of facilities, i.e., select a given number k of locations
from a discrete set of n candidates, such that the average distance between
selected locations is maximized. In particular, we present algorithmic results
for the case where vertices are represented by points in d-dimensional space,
and edge weights correspond to rectilinear distances. Problems of this type
have been considered before, with the best result being an approximation
algorithm with performance ratio 2. For the case where k is fixed, we establish
a linear-time algorithm that finds an optimal solution. For the case where k is
part of the input, we present a polynomial-time approximation scheme.


title: On Addressing Efficiency Concerns in Privacy Preserving Data Mining

abstract:
  Data mining services require accurate input data for their results to be
meaningful, but privacy concerns may influence users to provide spurious
information. To encourage users to provide correct inputs, we recently proposed
a data distortion scheme for association rule mining that simultaneously
provides both privacy to the user and accuracy in the mining results. However,
mining the distorted database can be orders of magnitude more time-consuming as
compared to mining the original database. In this paper, we address this issue
and demonstrate that by (a) generalizing the distortion process to perform
symbol-specific distortion, (b) appropriately choosing the distortion
parameters, and (c) applying a variety of optimizations in the reconstruction
process, runtime efficiencies that are well within an order of magnitude of
undistorted mining can be achieved.


title: A Game Theoretic Framework for Incentives in P2P Systems

abstract:
  Peer-To-Peer (P2P) networks are self-organizing, distributed systems, with no
centralized authority or infrastructure. Because of the voluntary
participation, the availability of resources in a P2P system can be highly
variable and unpredictable. In this paper, we use ideas from Game Theory to
study the interaction of strategic and rational peers, and propose a
differential service-based incentive scheme to improve the system's
performance.


title: Automated Fault Localization Using Potential Invariants

abstract:
  We present a general method for fault localization based on abstracting over
program traces, and a tool that implements the method using Ernst's notion of
potential invariants. Our experiments so far have been unsatisfactory,
suggesting that further research is needed before invariants can be used to
locate faults.


title: A Dynamic Programming Algorithm for the Segmentation of Greek Texts

abstract:
  In this paper we introduce a dynamic programming algorithm to perform linear
text segmentation by global minimization of a segmentation cost function which
consists of: (a) within-segment word similarity and (b) prior information about
segment length. The evaluation of the segmentation accuracy of the algorithm on
a text collection consisting of Greek texts showed that the algorithm achieves
high segmentation accuracy and appears to be very innovating and promissing.


title:
Rigorous design of tracers: an experiment for constraint logic
  programming

abstract:
  In order to design and implement tracers, one must decide what exactly to
trace and how to produce this trace. On the one hand, trace designs are too
often guided by implementation concerns and are not as useful as they should
be. On the other hand, an interesting trace which cannot be produced
efficiently, is not very useful either. In this article we propose a
methodology which helps to efficiently produce accurate traces. Firstly, design
a formal specification of the trace model. Secondly, derive a prototype tracer
from this specification. Thirdly, analyze the produced traces. Fourthly,
implement an efficient tracer. Lastly, compare the traces of the two tracers.
At each step, problems can be found. In that case one has to iterate the
process. We have successfully applied the proposed methodology to the design
and implementation of a real tracer for constraint logic programming which is
able to efficiently generate information required to build interesting
graphical views of executions.


title:
Value-at-Risk and Expected Shortfall for Quadratic portfolio of
  securities with mixture of elliptic Distributed Risk Factors

abstract:
  Generally, in the financial literature, the notion of quadratic VaR is
implicitly confused with the Delta-Gamma VaR, because more authors dealt with
portfolios that contains derivatives instruments.
  In this paper, we postpone to estimate the Value-at-Risk of a quadratic
portfolio of securities (i.e equities) without the Delta and Gamma greeks, when
the joint log-returns changes with multivariate elliptic distribution. We have
reduced the estimation of the quadratic VaR of such portfolio to a resolution
of one dimensional integral equation. To illustrate our method, we give special
attention to the mixture of normal and mixture of t-student distribution. For
given VaR, when joint Risk Factors changes with elliptic distribution, we show
how to estimate an Expected Shortfall .


title: The Algebra of Utility Inference

abstract:
  Richard Cox [1] set the axiomatic foundations of probable inference and the
algebra of propositions. He showed that consistency within these axioms
requires certain rules for updating belief. In this paper we use the analogy
between probability and utility introduced in [2] to propose an axiomatic
foundation for utility inference and the algebra of preferences. We show that
consistency within these axioms requires certain rules for updating preference.
We discuss a class of utility functions that stems from the axioms of utility
inference and show that this class is the basic building block for any general
multiattribute utility function. We use this class of utility functions
together with the algebra of preferences to construct utility functions
represented by logical operations on the attributes.


title: An information theory for preferences

abstract:
  Recent literature in the last Maximum Entropy workshop introduced an analogy
between cumulative probability distributions and normalized utility functions.
Based on this analogy, a utility density function can de defined as the
derivative of a normalized utility function. A utility density function is
non-negative and integrates to unity. These two properties form the basis of a
correspondence between utility and probability. A natural application of this
analogy is a maximum entropy principle to assign maximum entropy utility
values. Maximum entropy utility interprets many of the common utility functions
based on the preference information needed for their assignment, and helps
assign utility values based on partial preference information. This paper
reviews maximum entropy utility and introduces further results that stem from
the duality between probability and utility.


title: Theory of One Tape Linear Time Turing Machines

abstract:
  A theory of one-tape (one-head) linear-time Turing machines is essentially
different from its polynomial-time counterpart since these machines are closely
related to finite state automata. This paper discusses structural-complexity
issues of one-tape Turing machines of various types (deterministic,
nondeterministic, reversible, alternating, probabilistic, counting, and quantum
Turing machines) that halt in linear time, where the running time of a machine
is defined as the length of any longest computation path. We explore structural
properties of one-tape linear-time Turing machines and clarify how the
machines' resources affect their computational patterns and power.


title:
Abductive Logic Programs with Penalization: Semantics, Complexity and
  Implementation

abstract:
  Abduction, first proposed in the setting of classical logics, has been
studied with growing interest in the logic programming area during the last
years.
  In this paper we study abduction with penalization in the logic programming
framework. This form of abductive reasoning, which has not been previously
analyzed in logic programming, turns out to represent several relevant
problems, including optimization problems, very naturally. We define a formal
model for abduction with penalization over logic programs, which extends the
abductive framework proposed by Kakas and Mancarella. We address knowledge
representation issues, encoding a number of problems in our abductive
framework. In particular, we consider some relevant problems, taken from
different domains, ranging from optimization theory to diagnosis and planning;
their encodings turn out to be simple and elegant in our formalism. We
thoroughly analyze the computational complexity of the main problems arising in
the context of abduction with penalization from logic programs. Finally, we
implement a system supporting the proposed abductive framework on top of the
DLV engine. To this end, we design a translation from abduction problems with
penalties into logic programs with weak constraints. We prove that this
approach is sound and complete.


title:
Managing Evolving Business Workflows through the Capture of Descriptive
  Information

abstract:
  Business systems these days need to be agile to address the needs of a
changing world. In particular the discipline of Enterprise Application
Integration requires business process management to be highly reconfigurable
with the ability to support dynamic workflows, inter-application integration
and process reconfiguration. Basing EAI systems on model-resident or on a
so-called description-driven approach enables aspects of flexibility,
distribution, system evolution and integration to be addressed in a
domain-independent manner. Such a system called CRISTAL is described in this
paper with particular emphasis on its application to EAI problem domains. A
practical example of the CRISTAL technology in the domain of manufacturing
systems, called Agilium, is described to demonstrate the principles of
model-driven system evolution and integration. The approach is compared to
other model-driven development approaches such as the Model-Driven Architecture
of the OMG and so-called Adaptive Object Models.


title: An O(m) Algorithm for Cores Decomposition of Networks

abstract:
  The structure of large networks can be revealed by partitioning them to
smaller parts, which are easier to handle. One of such decompositions is based
on $k$--cores, proposed in 1983 by Seidman. In the paper an efficient, $O(m)$,
$m$ is the number of lines, algorithm for determining the cores decomposition
of a given network is presented.


title: Feedforward Neural Networks with Diffused Nonlinear Weight Functions

abstract:
  In this paper, feedforward neural networks are presented that have nonlinear
weight functions based on look--up tables, that are specially smoothed in a
regularization called the diffusion. The idea of such a type of networks is
based on the hypothesis that the greater number of adaptive parameters per a
weight function might reduce the total number of the weight functions needed to
solve a given problem. Then, if the computational complexity of a propagation
through a single such a weight function would be kept low, then the introduced
neural networks might possibly be relatively fast.
  A number of tests is performed, showing that the presented neural networks
may indeed perform better in some cases than the classic neural networks and a
number of other learning machines.


title:
Nearly-Linear Time Algorithms for Graph Partitioning, Graph
  Sparsification, and Solving Linear Systems

abstract:
  This paper has been divided into three papers. arXiv:0809.3232,
arXiv:0808.4134, arXiv:cs/0607105


title: On secret sharing for graphs

abstract:
  In the paper we discuss how to share the secrets, that are graphs. So, far
secret sharing schemes were designed to work with numbers. As the first step,
we propose conditions for "graph to number" conversion methods. Hence, the
existing schemes can be used, without weakening their properties. Next, we show
how graph properties can be used to extend capabilities of secret sharing
schemes. This leads to proposal of using such properties for number based
secret sharing.


title:
Secret Sharing for n-Colorable Graphs with Application to Public Key
  Cryptography

abstract:
  At the beginning some results from the field of graph theory are presented.
Next we show how to share a secret that is proper n-coloring of the graph, with
the known structure. The graph is described and converted to the form, where
colors assigned to vertices form the number with entries from Zn. A secret
sharing scheme (SSS) for the graph coloring is proposed. The proposed method is
applied to the public-key cryptosystem called "Polly Cracker". In this case the
graph structure is a public key, while proper 3-colouring of the graph is a
private key. We show how to share the private key. Sharing particular
n-coloring (color-to-vertex assignment) for the known-structure graph is
presented next.


title: Kleene algebra with domain

abstract:
  We propose Kleene algebra with domain (KAD), an extension of Kleene algebra
with two equational axioms for a domain and a codomain operation, respectively.
KAD considerably augments the expressiveness of Kleene algebra, in particular
for the specification and analysis of state transition systems. We develop the
basic calculus, discuss some related theories and present the most important
models of KAD. We demonstrate applicability by two examples: First, an
algebraic reconstruction of Noethericity and well-foundedness; second, an
algebraic reconstruction of propositional Hoare logic.


title: Mace4 Reference Manual and Guide

abstract:
  Mace4 is a program that searches for finite models of first-order formulas.
For a given domain size, all instances of the formulas over the domain are
constructed. The result is a set of ground clauses with equality. Then, a
decision procedure based on ground equational rewriting is applied. If
satisfiability is detected, one or more models are printed. Mace4 is a useful
complement to first-order theorem provers, with the prover searching for proofs
and Mace4 looking for countermodels, and it is useful for work on finite
algebras. Mace4 performs better on equational problems than did our previous
model-searching program Mace2.


title: OTTER 3.3 Reference Manual

abstract:
  OTTER is a resolution-style theorem-proving program for first-order logic
with equality. OTTER includes the inference rules binary resolution,
hyperresolution, UR-resolution, and binary paramodulation. Some of its other
abilities and features are conversion from first-order formulas to clauses,
forward and back subsumption, factoring, weighting, answer literals, term
ordering, forward and back demodulation, evaluable functions and predicates,
Knuth-Bendix completion, and the hints strategy. OTTER is coded in ANSI C, is
free, and is portable to many different kinds of computer.


title: An Introduction to Using Software Tools for Automatic Differentiation

abstract:
  We give a gentle introduction to using various software tools for automatic
differentiation (AD). Ready-to-use examples are discussed, and links to further
information are presented. Our target audience includes all those who are
looking for a straightforward way to get started using the available AD
technology. The document is dynamic in the sense that its content will be
updated as the AD software evolves.


title:
Application Architecture for Spoken Language Resources in Organisational
  Settings

abstract:
  Special technologies need to be used to take advantage of, and overcome, the
challenges associated with acquiring, transforming, storing, processing, and
distributing spoken language resources in organisations. This paper introduces
an application architecture consisting of tools and supporting utilities for
indexing and transcription, and describes how these tools, together with
downstream processing and distribution systems, can be integrated into a
workflow. Two sample applications for this architecture are outlined- the
analysis of decision-making processes in organisations and the deployment of
systems development methods by designers in the field.


title: Design and Implementation of MPICH2 over InfiniBand with RDMA Support

abstract:
  For several years, MPI has been the de facto standard for writing parallel
applications. One of the most popular MPI implementations is MPICH. Its
successor, MPICH2, features a completely new design that provides more
performance and flexibility. To ensure portability, it has a hierarchical
structure based on which porting can be done at different levels. In this
paper, we present our experiences designing and implementing MPICH2 over
InfiniBand. Because of its high performance and open standard, InfiniBand is
gaining popularity in the area of high-performance computing. Our study focuses
on optimizing the performance of MPI-1 functions in MPICH2. One of our
objectives is to exploit Remote Direct Memory Access (RDMA) in Infiniband to
achieve high performance. We have based our design on the RDMA Channel
interface provided by MPICH2, which encapsulates architecture-dependent
communication functionalities into a very small set of functions. Starting with
a basic design, we apply different optimizations and also propose a
zero-copy-based design. We characterize the impact of our optimizations and
designs using microbenchmarks. We have also performed an application-level
evaluation using the NAS Parallel Benchmarks. Our optimized MPICH2
implementation achieves 7.6 $\mu$s latency and 857 MB/s bandwidth, which are
close to the raw performance of the underlying InfiniBand layer. Our study
shows that the RDMA Channel interface in MPICH2 provides a simple, yet
powerful, abstraction that enables implementations with high performance by
exploiting RDMA operations in InfiniBand. To the best of our knowledge, this is
the first high-performance design and implementation of MPICH2 on InfiniBand
using RDMA support.


title: Puzzle: Zermelo-Fraenkel set theory is inconsistent

abstract:
  In this note, we present a puzzle. We prove that Zermelo-Fraenkel set theory
is inconsistent by proving, using Zermelo-Fraenkel set theory, the false
statement that any algorithm that determines whether any $n \times n$ matrix
over $\mathbb F_2$, the finite field of order 2, is nonsingular must run in
exponential time in the worst-case scenario. The object of the puzzle is to
find the error in the proof.


title:
Local-search techniques for propositional logic extended with
  cardinality constraints

abstract:
  We study local-search satisfiability solvers for propositional logic extended
with cardinality atoms, that is, expressions that provide explicit ways to
model constraints on cardinalities of sets. Adding cardinality atoms to the
language of propositional logic facilitates modeling search problems and often
results in concise encodings. We propose two ``native'' local-search solvers
for theories in the extended language. We also describe techniques to reduce
the problem to standard propositional satisfiability and allow us to use
off-the-shelf SAT solvers. We study these methods experimentally. Our general
finding is that native solvers designed specifically for the extended language
perform better than indirect methods relying on SAT solvers.


title: WSAT(cc) - a fast local-search ASP solver

abstract:
  We describe WSAT(cc), a local-search solver for computing models of theories
in the language of propositional logic extended by cardinality atoms. WSAT(cc)
is a processing back-end for the logic PS+, a recently proposed formalism for
answer-set programming.


title: Logic programs with monotone cardinality atoms

abstract:
  We investigate mca-programs, that is, logic programs with clauses built of
monotone cardinality atoms of the form kX, where k is a non-negative integer
and X is a finite set of propositional atoms. We develop a theory of
mca-programs. We demonstrate that the operational concept of the one-step
provability operator generalizes to mca-programs, but the generalization
involves nondeterminism. Our main results show that the formalism of
mca-programs is a common generalization of (1) normal logic programming with
its semantics of models, supported models and stable models, (2) logic
programming with cardinality atoms and with the semantics of stable models, as
defined by Niemela, Simons and Soininen, and (3) of disjunctive logic
programming with the possible-model semantics of Sakama and Inoue.


title: Satisfiability and computing van der Waerden numbers

abstract:
  In this paper we bring together the areas of combinatorics and propositional
satisfiability. Many combinatorial theorems establish, often constructively,
the existence of positive integer functions, without actually providing their
closed algebraic form or tight lower and upper bounds. The area of Ramsey
theory is especially rich in such results. Using the problem of computing van
der Waerden numbers as an example, we show that these problems can be
represented by parameterized propositional theories in such a way that
decisions concerning their satisfiability determine the numbers (function) in
question. We show that by using general-purpose complete and local-search
techniques for testing propositional satisfiability, this approach becomes
effective -- competitive with specialized approaches. By following it, we were
able to obtain several new results pertaining to the problem of computing van
der Waerden numbers. We also note that due to their properties, especially
their structural simplicity and computational hardness, propositional theories
that arise in this research can be of use in development, testing and
benchmarking of SAT solvers.


title: Maintaining Information in Fully-Dynamic Trees with Top Trees

abstract:
  We introduce top trees as a design of a new simpler interface for data
structures maintaining information in a fully-dynamic forest. We demonstrate
how easy and versatile they are to use on a host of different applications. For
example, we show how to maintain the diameter, center, and median of each tree
in the forest. The forest can be updated by insertion and deletion of edges and
by changes to vertex and edge weights. Each update is supported in O(log n)
time, where n is the size of the tree(s) involved in the update. Also, we show
how to support nearest common ancestor queries and level ancestor queries with
respect to arbitrary roots in O(log n) time. Finally, with marked and unmarked
vertices, we show how to compute distances to a nearest marked vertex. The
later has applications to approximate nearest marked vertex in general graphs,
and thereby to static optimization problems over shortest path metrics.
  Technically speaking, top trees are easily implemented either with
Frederickson's topology trees [Ambivalent Data Structures for Dynamic
2-Edge-Connectivity and k Smallest Spanning Trees, SIAM J. Comput. 26 (2) pp.
484-538, 1997] or with Sleator and Tarjan's dynamic trees [A Data Structure for
Dynamic Trees. J. Comput. Syst. Sc. 26 (3) pp. 362-391, 1983]. However, we
claim that the interface is simpler for many applications, and indeed our new
bounds are quadratic improvements over previous bounds where they exist.


title:
Modeling State in Software Debugging of VHDL-RTL Designs -- A
  Model-Based Diagnosis Approach

abstract:
  In this paper we outline an approach of applying model-based diagnosis to the
field of automatic software debugging of hardware designs. We present our
value-level model for debugging VHDL-RTL designs and show how to localize the
erroneous component responsible for an observed misbehavior. Furthermore, we
discuss an extension of our model that supports the debugging of sequential
circuits, not only at a given point in time, but also allows for considering
the temporal behavior of VHDL-RTL designs. The introduced model is capable of
handling state inherently present in every sequential circuit. The principal
applicability of the new model is outlined briefly and we use industrial-sized
real world examples from the ISCAS'85 benchmark suite to discuss the
scalability of our approach.


title: Computing Convex Hulls with a Linear Solver

abstract:
  A programming tactic involving polyhedra is reported that has been widely
applied in the polyhedral analysis of (constraint) logic programs. The method
enables the computations of convex hulls that are required for polyhedral
analysis to be coded with linear constraint solving machinery that is available
in many Prolog systems.
  To appear in Theory and Practice of Logic Programming (TPLP)


title: Enhancing a Search Algorithm to Perform Intelligent Backtracking

abstract:
  This paper illustrates how a Prolog program, using chronological backtracking
to find a solution in some search space, can be enhanced to perform intelligent
backtracking. The enhancement crucially relies on the impurity of Prolog that
allows a program to store information when a dead end is reached. To illustrate
the technique, a simple search program is enhanced.
  To appear in Theory and Practice of Logic Programming.
  Keywords: intelligent backtracking, dependency-directed backtracking,
backjumping, conflict-directed backjumping, nogood sets, look-back.


title: Utility-Probability Duality

abstract:
  This paper presents duality between probability distributions and utility
functions.


title: On The Cost Distribution of a Memory Bound Function

abstract:
  Memory Bound Functions have been proposed for fighting spam, resisting Sybil
attacks and other purposes. A particular implementation of such functions has
been proposed in which the average effort required to generate a proof of
effort is set by parameters E and l to E * l. The distribution of effort
required to generate an individual proof about this average is fairly broad.
When particular uses of these functions are envisaged, the choice of E and l,
and the system design surrounding the generation and verification of proofs of
effort, need to take the breadth of the distribution into account.
  We show the distribution for this implementation, discuss the system design
issues in the context of two proposed applications, and suggest an improved
implementation.


title: How Push-To-Talk Makes Talk Less Pushy

abstract:
  This paper presents an exploratory study of college-age students using
two-way, push-to-talk cellular radios. We describe the observed and reported
use of cellular radio by the participants. We discuss how the half-duplex,
lightweight cellular radio communication was associated with reduced
interactional commitment, which meant the cellular radios could be used for a
wide range of conversation styles. One such style, intermittent conversation,
is characterized by response delays. Intermittent conversation is surprising in
an audio medium, since it is typically associated with textual media such as
instant messaging. We present design implications of our findings.


title: Parametric Connectives in Disjunctive Logic Programming

abstract:
  Disjunctive Logic Programming (\DLP) is an advanced formalism for Knowledge
Representation and Reasoning (KRR). \DLP is very expressive in a precise
mathematical sense: it allows to express every property of finite structures
that is decidable in the complexity class $\SigmaP{2}$ ($\NP^{\NP}$).
Importantly, the \DLP encodings are often simple and natural.
  In this paper, we single out some limitations of \DLP for KRR, which cannot
naturally express problems where the size of the disjunction is not known ``a
priori'' (like N-Coloring), but it is part of the input. To overcome these
limitations, we further enhance the knowledge modelling abilities of \DLP, by
extending this language by {\em Parametric Connectives (OR and AND)}. These
connectives allow us to represent compactly the disjunction/conjunction of a
set of atoms having a given property. We formally define the semantics of the
new language, named $DLP^{\bigvee,\bigwedge}$ and we show the usefulness of the
new constructs on relevant knowledge-based problems. We address implementation
issues and discuss related works.


title:
A Parameterised Hierarchy of Argumentation Semantics for Extended Logic
  Programming and its Application to the Well-founded Semantics

abstract:
  Argumentation has proved a useful tool in defining formal semantics for
assumption-based reasoning by viewing a proof as a process in which proponents
and opponents attack each others arguments by undercuts (attack to an
argument's premise) and rebuts (attack to an argument's conclusion). In this
paper, we formulate a variety of notions of attack for extended logic programs
from combinations of undercuts and rebuts and define a general hierarchy of
argumentation semantics parameterised by the notions of attack chosen by
proponent and opponent. We prove the equivalence and subset relationships
between the semantics and examine some essential properties concerning
consistency and the coherence principle, which relates default negation and
explicit negation. Most significantly, we place existing semantics put forward
in the literature in our hierarchy and identify a particular argumentation
semantics for which we prove equivalence to the paraconsistent well-founded
semantics with explicit negation, WFSX$_p$. Finally, we present a general proof
theory, based on dialogue trees, and show that it is sound and complete with
respect to the argumentation semantics.


title: OGSA/Globus Evaluation for Data Intensive Applications

abstract:
  We present an architecture of Globus Toolkit 3 based testbed intended for
evaluation of applicability of the Open Grid Service Architecture (OGSA) for
Data Intensive Applications.


title: Problem of Application Job Monitoring in GRID Systems

abstract:
  We present a new approach to monitoring of the execution process of an
application job in the GRID environment. The main point of the approach is use
of GRID ervices to access monitoring information with the security level
available in GRID.


title:
On an explicit finite difference method for fractional diffusion
  equations

abstract:
  A numerical method to solve the fractional diffusion equation, which could
also be easily extended to many other fractional dynamics equations, is
considered. These fractional equations have been proposed in order to describe
anomalous transport characterized by non-Markovian kinetics and the breakdown
of Fick's law. In this paper we combine the forward time centered space (FTCS)
method, well known for the numerical integration of ordinary diffusion
equations, with the Grunwald-Letnikov definition of the fractional derivative
operator to obtain an explicit fractional FTCS scheme for solving the
fractional diffusion equation. The resulting method is amenable to a stability
analysis a la von Neumann. We show that the analytical stability bounds are in
excellent agreement with numerical tests. Comparison between exact analytical
solutions and numerical predictions are made.

categories: cs.NA cond-mat.stat-mech cs.CE physics.comp-ph


title: A rigorous definition of axial lines: ridges on isovist fields

abstract:
  We suggest that 'axial lines' defined by (Hillier and Hanson, 1984) as lines
of uninterrupted movement within urban streetscapes or buildings, appear as
ridges in isovist fields (Benedikt, 1979). These are formed from the maximum
diametric lengths of the individual isovists, sometimes called viewsheds, that
make up these fields (Batty and Rana, 2004). We present an image processing
technique for the identification of lines from ridges, discuss current
strengths and weaknesses of the method, and show how it can be implemented
easily and effectively.