title:
CLPGUI: a generic graphical user interface for constraint logic
  programming over finite domains

abstract:
  CLPGUI is a graphical user interface for visualizing and interacting with
constraint logic programs over finite domains. In CLPGUI, the user can control
the execution of a CLP program through several views of constraints, of finite
domain variables and of the search tree. CLPGUI is intended to be used both for
teaching purposes, and for debugging and improving complex programs of
realworld scale. It is based on a client-server architecture for connecting the
CLP process to a Java-based GUI process. Communication by message passing
provides an open architecture which facilitates the reuse of graphical
components and the porting to different constraint programming systems.
Arbitrary constraints and goals can be posted incrementally from the GUI. We
propose several dynamic 2D and 3D visualizations of the search tree and of the
evolution of finite domain variables. We argue that the 3D representation of
search trees proposed in this paper provides the most appropriate visualization
of large search trees. We describe the current implementation of the
annotations and of the interactive execution model in GNU-Prolog, and report
some evaluation results.


title: More Precise Yet Efficient Type Inference for Logic Programs

abstract:
  Type analyses of logic programs which aim at inferring the types of the
program being analyzed are presented in a unified abstract interpretation-based
framework. This covers most classical abstract interpretation-based type
analyzers for logic programs, built on either top-down or bottom-up
interpretation of the program. In this setting, we discuss the widening
operator, arguably a crucial one. We present a new widening which is more
precise than those previously proposed. Practical results with our analysis
domain are also presented, showing that it also allows for efficient analysis.


title:
Value withdrawal explanations: a theoretical tool for programming
  environments

abstract:
  Constraint logic programming combines declarativity and efficiency thanks to
constraint solvers implemented for specific domains. Value withdrawal
explanations have been efficiently used in several constraints programming
environments but there does not exist any formalization of them. This paper is
an attempt to fill this lack. Furthermore, we hope that this theoretical tool
could help to validate some programming environments. A value withdrawal
explanation is a tree describing the withdrawal of a value during a domain
reduction by local consistency notions and labeling. Domain reduction is
formalized by a search tree using two kinds of operators: operators for local
consistency notions and operators for labeling. These operators are defined by
sets of rules. Proof trees are built with respect to these rules. For each
removed value, there exists such a proof tree which is the withdrawal
explanation of this value.


title: Exporting Prolog source code

abstract:
  In this paper we present a simple source code configuration tool. ExLibris
operates on libraries and can be used to extract from local libraries all code
relevant to a particular project. Our approach is not designed to address
problems arising in code production lines, but rather, to support the needs of
individual or small teams of researchers who wish to communicate their Prolog
programs. In the process, we also wish to accommodate and encourage the writing
of reusable code. Moreover, we support and propose ways of dealing with issues
arising in the development of code that can be run on a variety of like-minded
Prolog systems. With consideration to these aims we have made the following
decisions: (i) support file-based source development, (ii) require minimal
program transformation, (iii) target simplicity of usage, and (iv) introduce
minimum number of new primitives.


title:
Proceedings of the 12th International Workshop on Logic Programming
  Environments

abstract:
  The twelfth Workshop on Logic Programming Environments, WLPE 2002, is one in
a series of international workshops held in the topic area. The workshops
facilitate the exchange ideas and results among researchers and system
developers on all aspects of environments for logic programming. Relevant
topics for these workshops include user interfaces, human engineering,
execution visualization, development tools, providing for new paradigms, and
interfacing to language system tools and external systems. This twelfth
workshop held in Copenhaguen. It follows the successful eleventh Workshop on
Logic Programming Environments held in Cyprus in December, 2001.
  WLPE 2002 features ten presentations. The presentations involve, in some way,
constraint logic programming, object-oriented programming and abstract
interpretation. Topics areas addressed include tools for software development,
execution visualization, software maintenance, instructional aids.
  This workshop was a post-conference workshop at ICLP 2002.
  Alexandre Tessier, Program Chair, WLPE 2002, June 2002.


title: An Architecture for Making Object-Oriented Systems Available from Prolog

abstract:
  It is next to impossible to develop real-life applications in just pure
Prolog. With XPCE we realised a mechanism for integrating Prolog with an
external object-oriented system that turns this OO system into a natural
extension to Prolog. We describe the design and how it can be applied to other
external OO systems.


title:
Enhancing Usefulness of Declarative Programming Frameworks through
  Complete Integration

abstract:
  The Gisela framework for declarative programming was developed with the
specific aim of providing a tool that would be useful for knowledge
representation and reasoning within real-world applications. To achieve this, a
complete integration into an object-oriented application development
environment was used. The framework and methodology developed provide two
alternative application programming interfaces (APIs): Programming using
objects or programming using a traditional equational declarative style. In
addition to providing complete integration, Gisela also allows extensions and
modifications due to the general computation model and well-defined APIs. We
give a brief overview of the declarative model underlying Gisela and we present
the methodology proposed for building applications together with some real
examples.


title: The Rise and Fall of the Church-Turing Thesis

abstract:
  The essay consists of three parts. In the first part, it is explained how
theory of algorithms and computations evaluates the contemporary situation with
computers and global networks. In the second part, it is demonstrated what new
perspectives this theory opens through its new direction that is called theory
of super-recursive algorithms. These algorithms have much higher computing
power than conventional algorithmic schemes. In the third part, we explicate
how realization of what this theory suggests might influence life of people in
future. It is demonstrated that now the theory is far ahead computing practice
and practice has to catch up with the theory. We conclude with a comparison of
different approaches to the development of information technology.


title: Modeling Complex Domains of Actions and Change

abstract:
  This paper studies the problem of modeling complex domains of actions and
change within high-level action description languages. We investigate two main
issues of concern: (a) can we represent complex domains that capture together
different problems such as ramifications, non-determinism and concurrency of
actions, at a high-level, close to the given natural ontology of the problem
domain and (b) what features of such a representation can affect, and how, its
computational behaviour. The paper describes the main problems faced in this
representation task and presents the results of an empirical study, carried out
through a series of controlled experiments, to analyze the computational
performance of reasoning in these representations. The experiments compare
different representations obtained, for example, by changing the basic ontology
of the domain or by varying the degree of use of indirect effect laws through
domain constraints. This study has helped to expose the main sources of
computational difficulty in the reasoning and suggest some methodological
guidelines for representing complex domains. Although our work has been carried
out within one particular high-level description language, we believe that the
results, especially those that relate to the problems of representation, are
independent of the specific modeling language.


title: Physical Traces: Quantum vs. Classical Information Processing

abstract:
  Within the Geometry of Interaction (GoI) paradigm, we present a setting that
enables qualitative differences between classical and quantum processes to be
explored. The key construction is the physical interpretation/realization of
the traced monoidal categories of finite-dimensional vector spaces with tensor
product as monoidal structure and of finite sets and relations with Cartesian
product as monoidal structure, both of them providing a so-called wave-style
GoI. The developments in this paper reveal that envisioning state update due to
quantum measurement as a process provides a powerful tool for developing
high-level approaches to quantum information processing.


title: Question Answering over Unstructured Data without Domain Restrictions

abstract:
  Information needs are naturally represented as questions. Automatic
Natural-Language Question Answering (NLQA) has only recently become a practical
task on a larger scale and without domain constraints.
  This paper gives a brief introduction to the field, its history and the
impact of systematic evaluation competitions.
  It is then demonstrated that an NLQA system for English can be built and
evaluated in a very short time using off-the-shelf parsers and thesauri. The
system is based on Robust Minimal Recursion Semantics (RMRS) and is portable
with respect to the parser used as a frontend. It applies atomic term
unification supported by question classification and WordNet lookup for
semantic similarity matching of parsed question representation and free text.


title: Value Based Argumentation Frameworks

abstract:
  This paper introduces the notion of value-based argumentation frameworks, an
extension of the standard argumentation frameworks proposed by Dung, which are
able toshow how rational decision is possible in cases where arguments derive
their force from the social values their acceptance would promote.


title:
Preferred well-founded semantics for logic programming by alternating
  fixpoints: Preliminary report

abstract:
  We analyze the problem of defining well-founded semantics for ordered logic
programs within a general framework based on alternating fixpoint theory. We
start by showing that generalizations of existing answer set approaches to
preference are too weak in the setting of well-founded semantics. We then
specify some informal yet intuitive criteria and propose a semantical framework
for preference handling that is more suitable for defining well-founded
semantics for ordered logic programs. The suitability of the new approach is
convinced by the fact that many attractive properties are satisfied by our
semantics. In particular, our semantics is still correct with respect to
various existing answer sets semantics while it successfully overcomes the
weakness of their generalization to well-founded semantics. Finally, we
indicate how an existing preferred well-founded semantics can be captured
within our semantical framework.


title:
Linear-Time Pointer-Machine Algorithms for Path-Evaluation Problems on
  Trees and Graphs

abstract:
  We present algorithms that run in linear time on pointer machines for a
collection of problems, each of which either directly or indirectly requires
the evaluation of a function defined on paths in a tree. These problems
previously had linear-time algorithms but only for random-access machines
(RAMs); the best pointer-machine algorithms were super-linear by an
inverse-Ackermann-function factor. Our algorithms are also simpler, in some
cases substantially, than the previous linear-time RAM algorithms. Our
improvements come primarily from three new ideas: a refined analysis of path
compression that gives a linear bound if the compressions favor certain nodes,
a pointer-based radix sort as a replacement for table-based methods, and a more
careful partitioning of a tree into easily managed parts. Our algorithms
compute nearest common ancestors off-line, verify and construct minimum
spanning trees, do interval analysis on a flowgraph, find the dominators of a
flowgraph, and build the component tree of a weighted tree.


title: Some addenda on distance function wavelets

abstract:
  This report will add some supplements to the recently finished report series
on the distance function wavelets (DFW). First, we define the general distance
in terms of the Riesz potential, and then, the distance function Abel wavelets
are derived via the fractional integral and Laplacian. Second, the DFW Weyl
transform is found to be a shifted Laplace potential DFW. The DFW Radon
transform is also presented. Third, we present a conjecture on truncation error
formula of the multiple reciprocity Laplace DFW series and discuss its error
distributions in terms of node density distributions. Forth, we point out that
the Hermite distance function interpolation can be used to replace overlapping
in the domain decomposition in order to produce sparse matrix. Fifth, the shape
parameter is explained as a virtual extra axis contribution in terms of the
MQ-type Possion kernel. The report is concluded with some remarks on a range of
other issues.


title: Parallel Delaunay Refinement: Algorithms and Analyses

abstract:
  In this paper, we analyze the complexity of natural parallelizations of
Delaunay refinement methods for mesh generation. The parallelizations employ a
simple strategy: at each iteration, they choose a set of ``independent'' points
to insert into the domain, and then update the Delaunay triangulation. We show
that such a set of independent points can be constructed efficiently in
parallel and that the number of iterations needed is $O(\log^2(L/s))$, where
$L$ is the diameter of the domain, and $s$ is the smallest edge in the output
mesh. In addition, we show that the insertion of each independent set of points
can be realized sequentially by Ruppert's method in two dimensions and
Shewchuk's in three dimensions. Therefore, our parallel Delaunay refinement
methods provide the same element quality and mesh size guarantees as the
sequential algorithms in both two and three dimensions. For quasi-uniform
meshes, such as those produced by Chew's method, we show that the number of
iterations can be reduced to $O(\log(L/s))$. To the best of our knowledge,
these are the first provably polylog$(L/s)$ parallel time Delaunay meshing
algorithms that generate well-shaped meshes of size optimal to within a
constant.


title: Interpolation Theorems for Nonmonotonic Reasoning Systems

abstract:
  Craig's interpolation theorem (Craig 1957) is an important theorem known for
propositional logic and first-order logic. It says that if a logical formula
$\beta$ logically follows from a formula $\alpha$, then there is a formula
$\gamma$, including only symbols that appear in both $\alpha,\beta$, such that
$\beta$ logically follows from $\gamma$ and $\gamma$ logically follows from
$\alpha$. Such theorems are important and useful for understanding those logics
in which they hold as well as for speeding up reasoning with theories in those
logics. In this paper we present interpolation theorems in this spirit for
three nonmonotonic systems: circumscription, default logic and logic programs
with the stable models semantics (a.k.a. answer set semantics). These results
give us better understanding of those logics, especially in contrast to their
nonmonotonic characteristics. They suggest that some \emph{monotonicity}
principle holds despite the failure of classic monotonicity for these logics.
Also, they sometimes allow us to use methods for the decomposition of reasoning
for these systems, possibly increasing their applicability and tractability.
Finally, they allow us to build structured representations that use those
logics.


title: Embedding Default Logic in Propositional Argumentation Systems

abstract:
  In this paper we present a transformation of finite propositional default
theories into so-called propositional argumentation systems. This
transformation allows to characterize all notions of Reiter's default logic in
the framework of argumentation systems. As a consequence, computing extensions,
or determining wether a given formula belongs to one extension or all
extensions can be answered without leaving the field of classical propositional
logic. The transformation proposed is linear in the number of defaults.


title: Polynomial Time Data Reduction for Dominating Set

abstract:
  Dealing with the NP-complete Dominating Set problem on undirected graphs, we
demonstrate the power of data reduction by preprocessing from a theoretical as
well as a practical side. In particular, we prove that Dominating Set
restricted to planar graphs has a so-called problem kernel of linear size,
achieved by two simple and easy to implement reduction rules. Moreover, having
implemented our reduction rules, first experiments indicate the impressive
practical potential of these rules. Thus, this work seems to open up a new and
prospective way how to cope with one of the most important problems in graph
theory and combinatorial optimization.


title:
On the existence and multiplicity of extensions in dialectical
  argumentation

abstract:
  In the present paper, the existence and multiplicity problems of extensions
are addressed. The focus is on extension of the stable type. The main result of
the paper is an elegant characterization of the existence and multiplicity of
extensions in terms of the notion of dialectical justification, a close cousin
of the notion of admissibility. The characterization is given in the context of
the particular logic for dialectical argumentation DEFLOG. The results are of
direct relevance for several well-established models of defeasible reasoning
(like default logic, logic programming and argumentation frameworks), since
elsewhere dialectical argumentation has been shown to have close formal
connections with these models.


title: Knuth-Bendix constraint solving is NP-complete

abstract:
  We show the NP-completeness of the existential theory of term algebras with
the Knuth-Bendix order by giving a nondeterministic polynomial-time algorithm
for solving Knuth-Bendix ordering constraints.


title:
Small Large-Scale Wireless Networks: Mobility-Assisted Resource
  Discovery

abstract:
  In this study, the concept of small worlds is investigated in the context of
large-scale wireless ad hoc and sensor networks. Wireless networks are spatial
graphs that are usually much more clustered than random networks and have much
higher path length characteristics. We observe that by adding only few random
links, path length of wireless networks can be reduced drastically without
affecting clustering. What is even more interesting is that such links need not
be formed randomly but may be confined to a limited number of hops between the
connected nodes. This has an important practical implication, as now we can
introduce a distributed algorithm in large-scale wireless networks, based on
what we call contacts, to improve the performance of resource discovery in such
networks, without resorting to global flooding. We propose new contact-based
protocols for adding logical short cuts in wireless networks efficiently. The
new protocols take advantage of mobility in order to increase reachability of
the search. We study the performance of our proposed contact-based
architecture, and clarify the context in which large-scale wireless networks
can be turned into small world networks.


title:
A continuation semantics of interrogatives that accounts for Baker's
  ambiguity

abstract:
  Wh-phrases in English can appear both raised and in-situ. However, only
in-situ wh-phrases can take semantic scope beyond the immediately enclosing
clause. I present a denotational semantics of interrogatives that naturally
accounts for these two properties. It neither invokes movement or economy, nor
posits lexical ambiguity between raised and in-situ occurrences of the same
wh-phrase. My analysis is based on the concept of continuations. It uses a
novel type system for higher-order continuations to handle wide-scope
wh-phrases while remaining strictly compositional. This treatment sheds light
on the combinatorics of interrogatives as well as other kinds of so-called
A'-movement.


title:
A Polynomial Translation of Logic Programs with Nested Expressions into
  Disjunctive Logic Programs: Preliminary Report

abstract:
  Nested logic programs have recently been introduced in order to allow for
arbitrarily nested formulas in the heads and the bodies of logic program rules
under the answer sets semantics. Nested expressions can be formed using
conjunction, disjunction, as well as the negation as failure operator in an
unrestricted fashion. This provides a very flexible and compact framework for
knowledge representation and reasoning. Previous results show that nested logic
programs can be transformed into standard (unnested) disjunctive logic programs
in an elementary way, applying the negation as failure operator to body
literals only. This is of great practical relevance since it allows us to
evaluate nested logic programs by means of off-the-shelf disjunctive logic
programming systems, like DLV. However, it turns out that this straightforward
transformation results in an exponential blow-up in the worst-case, despite the
fact that complexity results indicate that there is a polynomial translation
among both formalisms. In this paper, we take up this challenge and provide a
polynomial translation of logic programs with nested expressions into
disjunctive logic programs. Moreover, we show that this translation is modular
and (strongly) faithful. We have implemented both the straightforward as well
as our advanced transformation; the resulting compiler serves as a front-end to
DLV and is publicly available on the Web.


title: Complexity of Nested Circumscription and Nested Abnormality Theories

abstract:
  The need for a circumscriptive formalism that allows for simple yet elegant
modular problem representation has led Lifschitz (AIJ, 1995) to introduce
nested abnormality theories (NATs) as a tool for modular knowledge
representation, tailored for applying circumscription to minimize exceptional
circumstances. Abstracting from this particular objective, we propose L_{CIRC},
which is an extension of generic propositional circumscription by allowing
propositional combinations and nesting of circumscriptive theories. As shown,
NATs are naturally embedded into this language, and are in fact of equal
expressive capability. We then analyze the complexity of L_{CIRC} and NATs, and
in particular the effect of nesting. The latter is found to be a source of
complexity, which climbs the Polynomial Hierarchy as the nesting depth
increases and reaches PSPACE-completeness in the general case. We also identify
meaningful syntactic fragments of NATs which have lower complexity. In
particular, we show that the generalization of Horn circumscription in the NAT
framework remains CONP-complete, and that Horn NATs without fixed letters can
be efficiently transformed into an equivalent Horn CNF, which implies
polynomial solvability of principal reasoning tasks. Finally, we also study
extensions of NATs and briefly address the complexity in the first-order case.
Our results give insight into the ``cost'' of using L_{CIRC} (resp. NATs) as a
host language for expressing other formalisms such as action theories,
narratives, or spatial theories.


title: Reinforcing Reachable Routes

abstract:
  This paper studies the evaluation of routing algorithms from the perspective
of reachability routing, where the goal is to determine all paths between a
sender and a receiver. Reachability routing is becoming relevant with the
changing dynamics of the Internet and the emergence of low-bandwidth
wireless/ad-hoc networks. We make the case for reinforcement learning as the
framework of choice to realize reachability routing, within the confines of the
current Internet infrastructure. The setting of the reinforcement learning
problem offers several advantages, including loop resolution, multi-path
forwarding capability, cost-sensitive routing, and minimizing state overhead,
while maintaining the incremental spirit of current backbone routing
algorithms. We identify research issues in reinforcement learning applied to
the reachability routing problem to achieve a fluid and robust backbone routing
framework. The paper is targeted toward practitioners seeking to implement a
reachability routing algorithm.


title: Paraconsistency of Interactive Computation

abstract:
  The goal of computational logic is to allow us to model computation as well
as to reason about it. We argue that a computational logic must be able to
model interactive computation. We show that first-order logic cannot model
interactive computation due to the incompleteness of interaction. We show that
interactive computation is necessarily paraconsistent, able to model both a
fact and its negation, due to the role of the world (environment) in
determining the course of the computation. We conclude that paraconsistency is
a necessary property for a logic that can model interactive computation.


title:
Nonmonotonic Probabilistic Logics between Model-Theoretic Probabilistic
  Logic and Probabilistic Logic under Coherence

abstract:
  Recently, it has been shown that probabilistic entailment under coherence is
weaker than model-theoretic probabilistic entailment. Moreover, probabilistic
entailment under coherence is a generalization of default entailment in System
P. In this paper, we continue this line of research by presenting probabilistic
generalizations of more sophisticated notions of classical default entailment
that lie between model-theoretic probabilistic entailment and probabilistic
entailment under coherence. That is, the new formalisms properly generalize
their counterparts in classical default reasoning, they are weaker than
model-theoretic probabilistic entailment, and they are stronger than
probabilistic entailment under coherence. The new formalisms are useful
especially for handling probabilistic inconsistencies related to conditioning
on zero events. They can also be applied for probabilistic belief revision.
More generally, in the same spirit as a similar previous paper, this paper
sheds light on exciting new formalisms for probabilistic reasoning beyond the
well-known standard ones.


title: Introducing Dynamic Behavior in Amalgamated Knowledge Bases

abstract:
  The problem of integrating knowledge from multiple and heterogeneous sources
is a fundamental issue in current information systems. In order to cope with
this problem, the concept of mediator has been introduced as a software
component providing intermediate services, linking data resources and
application programs, and making transparent the heterogeneity of the
underlying systems. In designing a mediator architecture, we believe that an
important aspect is the definition of a formal framework by which one is able
to model integration according to a declarative style. To this purpose, the use
of a logical approach seems very promising. Another important aspect is the
ability to model both static integration aspects, concerning query execution,
and dynamic ones, concerning data updates and their propagation among the
various data sources. Unfortunately, as far as we know, no formal proposals for
logically modeling mediator architectures both from a static and dynamic point
of view have already been developed. In this paper, we extend the framework for
amalgamated knowledge bases, presented by Subrahmanian, to deal with dynamic
aspects. The language we propose is based on the Active U-Datalog language, and
extends it with annotated logic and amalgamation concepts. We model the sources
of information and the mediator (also called supervisor) as Active U-Datalog
deductive databases, thus modeling queries, transactions, and active rules,
interpreted according to the PARK semantics. By using active rules, the system
can efficiently perform update propagation among different databases. The
result is a logical environment, integrating active and deductive rules, to
perform queries and update propagation in an heterogeneous mediated framework.


title: Libra: An Economy driven Job Scheduling System for Clusters

abstract:
  Clusters of computers have emerged as mainstream parallel and distributed
platforms for high-performance, high-throughput and high-availability
computing. To enable effective resource management on clusters, numerous
cluster managements systems and schedulers have been designed. However, their
focus has essentially been on maximizing CPU performance, but not on improving
the value of utility delivered to the user and quality of services. This paper
presents a new computational economy driven scheduling system called Libra,
which has been designed to support allocation of resources based on the users?
quality of service (QoS) requirements. It is intended to work as an add-on to
the existing queuing and resource management system. The first version has been
implemented as a plugin scheduler to the PBS (Portable Batch System) system.
The scheduler offers market-based economy driven service for managing batch
jobs on clusters by scheduling CPU time according to user utility as determined
by their budget and deadline rather than system performance considerations. The
Libra scheduler ensures that both these constraints are met within an O(n)
run-time. The Libra scheduler has been simulated using the GridSim toolkit to
carry out a detailed performance analysis. Results show that the deadline and
budget based proportional resource allocation strategy improves the utility of
the system and user satisfaction as compared to system-centric scheduling
strategies.


title:
Randomized Approximation Schemes for Cuts and Flows in Capacitated
  Graphs

abstract:
  We improve on random sampling techniques for approximately solving problems
that involve cuts and flows in graphs. We give a near-linear-time construction
that transforms any graph on n vertices into an O(n\log n)-edge graph on the
same vertices whose cuts have approximately the same value as the original
graph's. In this new graph, for example, we can run the O(m^{3/2})-time maximum
flow algorithm of Goldberg and Rao to find an s--t minimum cut in O(n^{3/2})
time. This corresponds to a (1+epsilon)-times minimum s--t cut in the original
graph. In a similar way, we can approximate a sparsest cut to within O(log n)
in O(n^2) time using a previous O(mn)-time algorithm. A related approach leads
to a randomized divide and conquer algorithm producing an approximately maximum
flow in O(m sqrt{n}) time.


title: On non-abelian homomorphic public-key cryptosystems

abstract:
  An important problem of modern cryptography concerns secret public-key
computations in algebraic structures. We construct homomorphic cryptosystems
being (secret) epimorphisms f:G --> H, where G, H are (publically known) groups
and H is finite. A letter of a message to be encrypted is an element h element
of H, while its encryption g element of G is such that f(g)=h. A homomorphic
cryptosystem allows one to perform computations (operating in a group G) with
encrypted information (without knowing the original message over H).
  In this paper certain homomorphic cryptosystems are constructed for the first
time for non-abelian groups H (earlier, homomorphic cryptosystems were known
only in the Abelian case). In fact, we present such a system for any solvable
(fixed) group H.


title: Public-key cryptography and invariant theory

abstract:
  Public-key cryptosystems are suggested based on invariants of groups. We give
also an overview of the known cryptosystems which involve groups.


title: Moebius-Invariant Natural Neighbor Interpolation

abstract:
  We propose an interpolation method that is invariant under Moebius
transformations; that is, interpolation followed by transformation gives the
same result as transformation followed by interpolation. The method uses
natural (Delaunay) neighbors, but weights neighbors according to angles formed
by Delaunay circles.


title: Dynamic Generators of Topologically Embedded Graphs

abstract:
  We provide a data structure for maintaining an embedding of a graph on a
surface (represented combinatorially by a permutation of edges around each
vertex) and computing generators of the fundamental group of the surface, in
amortized time O(log n + log g(log log g)^3) per update on a surface of genus
g; we can also test orientability of the surface in the same time, and maintain
the minimum and maximum spanning tree of the graph in time O(log n + log^4 g)
per update. Our data structure allows edge insertion and deletion as well as
the dual operations; these operations may implicitly change the genus of the
embedding surface. We apply similar ideas to improve the constant factor in a
separator theorem for low-genus graphs, and to find in linear time a
tree-decomposition of low-genus low-diameter graphs.


title: Evaluating Defaults

abstract:
  We seek to find normative criteria of adequacy for nonmonotonic logic similar
to the criterion of validity for deductive logic. Rather than stipulating that
the conclusion of an inference be true in all models in which the premises are
true, we require that the conclusion of a nonmonotonic inference be true in
``almost all'' models of a certain sort in which the premises are true. This
``certain sort'' specification picks out the models that are relevant to the
inference, taking into account factors such as specificity and vagueness, and
previous inferences. The frequencies characterizing the relevant models reflect
known frequencies in our actual world. The criteria of adequacy for a default
inference can be extended by thresholding to criteria of adequacy for an
extension. We show that this avoids the implausibilities that might otherwise
result from the chaining of default inferences. The model proportions, when
construed in terms of frequencies, provide a verifiable grounding of default
rules, and can become the basis for generating default rules from statistics.


title:
Paraconsistent Reasoning via Quantified Boolean Formulas,I: Axiomatising
  Signed Systems

abstract:
  Signed systems were introduced as a general, syntax-independent framework for
paraconsistent reasoning, that is, non-trivialised reasoning from inconsistent
information. In this paper, we show how the family of corresponding
paraconsistent consequence relations can be axiomatised by means of quantified
Boolean formulas. This approach has several benefits. First, it furnishes an
axiomatic specification of paraconsistent reasoning within the framework of
signed systems. Second, this axiomatisation allows us to identify upper bounds
for the complexity of the different signed consequence relations. We strengthen
these upper bounds by providing strict complexity results for the considered
reasoning tasks. Finally, we obtain an implementation of different forms of
paraconsistent reasoning by appeal to the existing system QUIP.


title:
Repairing Inconsistent Databases: A Model-Theoretic Approach and
  Abductive Reasoning

abstract:
  In this paper we consider two points of views to the problem of coherent
integration of distributed data. First we give a pure model-theoretic analysis
of the possible ways to `repair' a database. We do so by characterizing the
possibilities to `recover' consistent data from an inconsistent database in
terms of those models of the database that exhibit as minimal inconsistent
information as reasonably possible. Then we introduce an abductive application
to restore the consistency of a given database. This application is based on an
abductive solver (A-system) that implements an SLDNFA-resolution procedure, and
computes a list of data-facts that should be inserted to the database or
retracted from it in order to keep the database consistent. The two approaches
for coherent data integration are related by soundness and completeness
results.


title: A Model-Theoretic Semantics for Defeasible Logic

abstract:
  Defeasible logic is an efficient logic for defeasible reasoning. It is
defined through a proof theory and, until now, has had no model theory. In this
paper a model-theoretic semantics is given for defeasible logic. The logic is
sound and complete with respect to the semantics. We also briefly outline how
this approach extends to a wide range of defeasible logics.


title: Axiomatic Aspects of Default Inference

abstract:
  This paper studies axioms for nonmonotonic consequences from a
semantics-based point of view, focusing on a class of mathematical structures
for reasoning about partial information without a predefined syntax/logic. This
structure is called a default structure. We study axioms for the nonmonotonic
consequence relation derived from extensions as in Reiter's default logic,
using skeptical reasoning, but extensions are now used for the construction of
possible worlds in a default information structure.
  In previous work we showed that skeptical reasoning arising from
default-extensions obeys a well-behaved set of axioms including the axiom of
cautious cut. We show here that, remarkably, the converse is also true: any
consequence relation obeying this set of axioms can be represented as one
constructed from skeptical reasoning. We provide representation theorems to
relate axioms for nonmonotonic consequence relation and properties about
extensions, and provide one-to-one correspondence between nonmonotonic systems
which satisfies the law of cautious monotony and default structures with unique
extensions. Our results give a theoretical justification for a set of basic
rules governing the update of nonmonotonic knowledge bases, demonstrating the
derivation of them from the more concrete and primitive construction of
extensions. It is also striking to note that proofs of the representation
theorems show that only shallow extensions are necessary, in the sense that the
number of iterations needed to achieve an extension is at most three. All of
these developments are made possible by taking a more liberal view of
consistency: consistency is a user defined predicate, satisfying some basic
properties.


title: A Paraconsistent Higher Order Logic

abstract:
  Classical logic predicts that everything (thus nothing useful at all) follows
from inconsistency. A paraconsistent logic is a logic where an inconsistency
does not lead to such an explosion, and since in practice consistency is
difficult to achieve there are many potential applications of paraconsistent
logics in knowledge-based systems, logical semantics of natural language, etc.
Higher order logics have the advantages of being expressive and with several
automated theorem provers available. Also the type system can be helpful. We
present a concise description of a paraconsistent higher order logic with
countable infinite indeterminacy, where each basic formula can get its own
indeterminate truth value (or as we prefer: truth code). The meaning of the
logical operators is new and rather different from traditional many-valued
logics as well as from logics based on bilattices. The adequacy of the logic is
examined by a case study in the domain of medicine. Thus we try to build a
bridge between the HOL and MVL communities. A sequent calculus is proposed
based on recent work by Muskens.


title: Defining Rough Sets by Extended Logic Programs

abstract:
  We show how definite extended logic programs can be used for defining and
reasoning with rough sets. Moreover, a rough-set-specific query language is
presented and an answering algorithm is outlined. Thus, we not only show a
possible application of a paraconsistent logic to the field of rough sets as we
also establish a link between rough set theory and logic programming, making
possible transfer of expertise between both fields.


title: On a Partial Decision Method for Dynamic Proofs

abstract:
  This paper concerns a goal directed proof procedure for the propositional
fragment of the adaptive logic ACLuN1. At the propositional level, it forms an
algorithm for final derivability. If extended to the predicative level, it
provides a criterion for final derivability. This is essential in view of the
absence of a positive test. The procedure may be generalized to all flat
adaptive logics.


title:
An Almost Classical Logic for Logic Programming and Nonmonotonic
  Reasoning

abstract:
  The model theory of a first-order logic called N^4 is introduced. N^4 does
not eliminate double negations, as classical logic does, but instead reduces
fourfold negations. N^4 is very close to classical logic: N^4 has two truth
values; implications in N^4 are material, like in classical logic; and negation
distributes over compound formulas in N^4 as it does in classical logic.
Results suggest that the semantics of normal logic programs is conveniently
formalized in N^4: Classical logic Herbrand interpretations generalize
straightforwardly to N^4; the classical minimal Herbrand model of a positive
logic program coincides with its unique minimal N^4 Herbrand model; the stable
models of a normal logic program and its so-called complete minimal N^4
Herbrand models coincide.


title: Packet delay in models of data networks

abstract:
  We investigate individual packet delay in a model of data networks with
table-free, partial table and full table routing. We present analytical
estimation for the average packet delay in a network with small partial routing
table. Dependence of the delay on the size of the network and on the size of
the partial routing table is examined numerically. Consequences for network
scalability are discussed.


title: Preference Queries

abstract:
  The handling of user preferences is becoming an increasingly important issue
in present-day information systems. Among others, preferences are used for
information filtering and extraction to reduce the volume of data presented to
the user. They are also used to keep track of user profiles and formulate
policies to improve and automate decision making.
  We propose here a simple, logical framework for formulating preferences as
preference formulas. The framework does not impose any restrictions on the
preference relations and allows arbitrary operation and predicate signatures in
preference formulas. It also makes the composition of preference relations
straightforward. We propose a simple, natural embedding of preference formulas
into relational algebra (and SQL) through a single winnow operator
parameterized by a preference formula. The embedding makes possible the
formulation of complex preference queries, e.g., involving aggregation, by
piggybacking on existing SQL constructs. It also leads in a natural way to the
definition of further, preference-related concepts like ranking. Finally, we
present general algebraic laws governing the winnow operator and its
interaction with other relational algebra operators. The preconditions on the
applicability of the laws are captured by logical formulas. The laws provide a
formal foundation for the algebraic optimization of preference queries. We
demonstrate the usefulness of our approach through numerous examples.


title: Answer Sets for Consistent Query Answering in Inconsistent Databases

abstract:
  A relational database is inconsistent if it does not satisfy a given set of
integrity constraints. Nevertheless, it is likely that most of the data in it
is consistent with the constraints. In this paper we apply logic programming
based on answer sets to the problem of retrieving consistent information from a
possibly inconsistent database. Since consistent information persists from the
original database to every of its minimal repairs, the approach is based on a
specification of database repairs using disjunctive logic programs with
exceptions, whose answer set semantics can be represented and computed by
systems that implement stable model semantics. These programs allow us to
declare persistence by defaults and repairing changes by exceptions. We
concentrate mainly on logic programs for binary integrity constraints, among
which we find most of the integrity constraints found in practice.


title: Eternity variables to prove simulation of specifications

abstract:
  Simulations of specifications are introduced as a unification and
generalization of refinement mappings, history variables, forward simulations,
prophecy variables, and backward simulations. A specification implements
another specification if and only if there is a simulation from the first one
to the second one that satisfies a certain condition. By adding stutterings,
the formalism allows that the concrete behaviours take more (or possibly less)
steps than the abstract ones.
  Eternity variables are introduced as a more powerful alternative for prophecy
variables and backward simulations. This formalism is semantically complete:
every simulation that preserves quiescence is a composition of a forward
simulation, an extension with eternity variables, and a refinement mapping.
This result does not need finite invisible nondeterminism and machine closure
as in the Abadi-Lamport Theorem. Internal continuity is weakened to
preservation of quiescence.


title: Noncontiguous I/O through PVFS

abstract:
  With the tremendous advances in processor and memory technology, I/O has
risen to become the bottleneck in high-performance computing for many
applications. The development of parallel file systems has helped to ease the
performance gap, but I/O still remains an area needing significant performance
improvement. Research has found that noncontiguous I/O access patterns in
scientific applications combined with current file system methods to perform
these accesses lead to unacceptable performance for large data sets. To enhance
performance of noncontiguous I/O we have created list I/O, a native version of
noncontiguous I/O. We have used the Parallel Virtual File System (PVFS) to
implement our ideas. Our research and experimentation shows that list I/O
outperforms current noncontiguous I/O access methods in most I/O situations and
can substantially enhance the performance of real-world scientific
applications.


title: Optimal Ordered Problem Solver

abstract:
  We present a novel, general, optimally fast, incremental way of searching for
a universal algorithm that solves each task in a sequence of tasks. The Optimal
Ordered Problem Solver (OOPS) continually organizes and exploits previously
found solutions to earlier tasks, efficiently searching not only the space of
domain-specific algorithms, but also the space of search algorithms.
Essentially we extend the principles of optimal nonincremental universal search
to build an incremental universal learner that is able to improve itself
through experience. In illustrative experiments, our self-improver becomes the
first general system that learns to solve all n disk Towers of Hanoi tasks
(solution size 2^n-1) for n up to 30, profiting from previously solved, simpler
tasks involving samples of a simple context free language.


title: Classification of Random Boolean Networks

abstract:
  We provide the first classification of different types of Random Boolean
Networks (RBNs). We study the differences of RBNs depending on the degree of
synchronicity and determinism of their updating scheme. For doing so, we first
define three new types of RBNs. We note some similarities and differences
between different types of RBNs with the aid of a public software laboratory we
developed. Particularly, we find that the point attractors are independent of
the updating scheme, and that RBNs are more different depending on their
determinism or non-determinism rather than depending on their synchronicity or
asynchronicity. We also show a way of mapping non-synchronous deterministic
RBNs into synchronous RBNs. Our results are important for justifying the use of
specific types of RBNs for modelling natural phenomena.


title: Theoretical limit of the compression for the information

abstract:
  The pit recording of file, the coefficient of compression are introduced. The
theoretical limit of the information compression as minimal coefficient of
compression for the given length of alphabet are found.


title: MV2-algorithm's clones

abstract:
  The clones of MV2 algorithm for any radix are discussed. The three various
examples of ones are represented.


title: Detecting Race Conditions in Parallel Programs that Use Semaphores

abstract:
  We address the problem of detecting race conditions in programs that use
semaphores for synchronization. Netzer and Miller showed that it is NP-complete
to detect race conditions in programs that use many semaphores. We show in this
paper that it remains NP-complete even if only two semaphores are used in the
parallel programs.
  For the tractable case, i.e., using only one semaphore, we give two
algorithms for detecting race conditions from the trace of executing a parallel
program on p processors, where n semaphore operations are executed. The first
algorithm determines in O(n) time whether a race condition exists between any
two given operations. The second algorithm runs in O(np log n) time and outputs
a compact representation from which one can determine in O(1) time whether a
race condition exists between any two given operations. The second algorithm is
near-optimal in that the running time is only O(log n) times the time required
simply to write down the output.


title: Probabilistic Search for Object Segmentation and Recognition

abstract:
  The problem of searching for a model-based scene interpretation is analyzed
within a probabilistic framework. Object models are formulated as generative
models for range data of the scene. A new statistical criterion, the truncated
object probability, is introduced to infer an optimal sequence of object
hypotheses to be evaluated for their match to the data. The truncated
probability is partly determined by prior knowledge of the objects and partly
learned from data. Some experiments on sequence quality and object segmentation
and recognition from stereo data are presented. The article recovers classic
concepts from object recognition (grouping, geometric hashing, alignment) from
the probabilistic perspective and adds insight into the optimal ordering of
object hypotheses for evaluation. Moreover, it introduces point-relation
densities, a key component of the truncated probability, as statistical models
of local surface shape.


title: Rectangle Size Bounds and Threshold Covers in Communication Complexity

abstract:
  We investigate the power of the most important lower bound technique in
randomized communication complexity, which is based on an evaluation of the
maximal size of approximately monochromatic rectangles, minimized over all
distributions on the inputs. While it is known that the 0-error version of this
bound is polynomially tight for deterministic communication, nothing in this
direction is known for constant error and randomized communication complexity.
We first study a one-sided version of this bound and obtain that its value lies
between the MA- and AM-complexities of the considered function. Hence the lower
bound actually works for a (communication complexity) class between MA cap
co-MA and AM cap co-AM. We also show that the MA-complexity of the disjointness
problem is Omega(sqrt(n)). Following this we consider the conjecture that the
lower bound method is polynomially tight for randomized communication
complexity. First we disprove a distributional version of this conjecture. Then
we give a combinatorial characterization of the value of the lower bound
method, in which the optimization over all distributions is absent. This
characterization is done by what we call a uniform threshold cover. We also
study relaxations of this notion, namely approximate majority covers and
majority covers, and compare these three notions in power, exhibiting
exponential separations. Each of these covers captures a lower bound method
previously used for randomized communication complexity.


title:
On the graph coloring check-digit scheme with applications to verifiable
  secret sharing

abstract:
  In the paper we apply graph vertex coloring for verification of secret
shares. We start from showing how to convert any graph into the number and vice
versa. Next, theoretical result concerning properties of n-colorable graphs is
stated and proven. From this result we derive graph coloring check-digit
scheme. Feasibility of proposed scheme increases with the size of the number,
which digits are checked and overall probability of errors. The check-digit
scheme is used to build shares verification method that does not require
cooperation of the third party. It allows implementing verification structure
different from the access structure. It does not depend on particular secret
sharing method. It can be used as long as the secret shares can be represented
by numbers or graphs.


title: Soft Concurrent Constraint Programming

abstract:
  Soft constraints extend classical constraints to represent multiple
consistency levels, and thus provide a way to express preferences, fuzziness,
and uncertainty. While there are many soft constraint solving formalisms, even
distributed ones, by now there seems to be no concurrent programming framework
where soft constraints can be handled. In this paper we show how the classical
concurrent constraint (cc) programming framework can work with soft
constraints, and we also propose an extension of cc languages which can use
soft constraints to prune and direct the search for a solution. We believe that
this new programming paradigm, called soft cc (scc), can be also very useful in
many web-related scenarios. In fact, the language level allows web agents to
express their interaction and negotiation protocols, and also to post their
requests in terms of preferences, and the underlying soft constraint solver can
find an agreement among the agents even if their requests are incompatible.


title: Offline Specialisation in Prolog Using a Hand-Written Compiler Generator

abstract:
  The so called ``cogen approach'' to program specialisation, writing a
compiler generator instead of a specialiser, has been used with considerable
success in partial evaluation of both functional and imperative languages. This
paper demonstrates that the cogen approach is also applicable to the
specialisation of logic programs (also called partial deduction) and leads to
effective specialisers. Moreover, using good binding-time annotations, the
speed-ups of the specialised programs are comparable to the speed-ups obtained
with online specialisers. The paper first develops a generic approach to
offline partial deduction and then a specific offline partial deduction method,
leading to the offline system LIX for pure logic programs. While this is a
usable specialiser by itself, it is used to develop the cogen system LOGEN.
Given a program, a specification of what inputs will be static, and an
annotation specifying which calls should be unfolded, LOGEN generates a
specialised specialiser for the program at hand. Running this specialiser with
particular values for the static inputs results in the specialised program.
While this requires two steps instead of one, the efficiency of the
specialisation process is improved in situations where the same program is
specialised multiple times. The paper also presents and evaluates an automatic
binding-time analysis that is able to derive the annotations. While the derived
annotations are still suboptimal compared to hand-crafted ones, they enable
non-expert users to use the LOGEN system in a fully automated way. Finally,
LOGEN is extended so as to directly support a large part of Prolog's
declarative and non-declarative features and so as to be able to perform so
called mixline specialisations.


title: TerraService.NET: An Introduction to Web Services

abstract:
  This article explores the design and construction of a geo-spatial Internet
web service application from the host web site perspective and from the
perspective of an application using the web service. The TerraService.NET web
service was added to the popular TerraServer database and web site with no
major structural changes to the database. The article discusses web service
design, implementation, and deployment concepts and design guidelines. Web
services enable applications that aggregate and interact with information and
resources from Internet-scale distributed servers. The article presents the
design of two USDA applications that interoperate with database and web service
resources in Fort Collins Colorado and the TerraService web service located in
Tukwila Washington.


title:
TeraScale SneakerNet: Using Inexpensive Disks for Backup, Archiving, and
  Data Exchange

abstract:
  Large datasets are most economically trnsmitted via parcel post given the
current economics of wide-area networking. This article describes how the Sloan
Digital Sky Survey ships terabyte scale datasets both within the US and to
Europe and Asia. We 3GT storage bricks (Ghz processor, GB ram, GbpsEthernet, TB
disk) for about 2k$ each. These bricks act as database servers on the LAN. They
are loaded at one site and read at the second site. The paper describes the
bricks, their economics, and some software issues that they raise.


title: Online Scientific Data Curation, Publication, and Archiving

abstract:
  Science projects are data publishers. The scale and complexity of current and
future science data changes the nature of the publication process. Publication
is becoming a major project component. At a minimum, a project must preserve
the ephemeral data it gathers. Derived data can be reconstructed from metadata,
but metadata is ephemeral. Longer term, a project should expect some archive to
preserve the data. We observe that pub-lished scientific data needs to be
available forever ? this gives rise to the data pyramid of versions and to data
inflation where the derived data volumes explode. As an example, this article
describes the Sloan Digital Sky Survey (SDSS) strategies for data publication,
data access, curation, and preservation.


title: Petabyte Scale Data Mining: Dream or Reality?

abstract:
  Science is becoming very data intensive1. Today's astronomy datasets with
tens of millions of galaxies already present substantial challenges for data
mining. In less than 10 years the catalogs are expected to grow to billions of
objects, and image archives will reach Petabytes. Imagine having a 100GB
database in 1996, when disk scanning speeds were 30MB/s, and database tools
were immature. Such a task today is trivial, almost manageable with a laptop.
We think that the issue of a PB database will be very similar in six years. In
this paper we scale our current experiments in data archiving and analysis on
the Sloan Digital Sky Survey2,3 data six years into the future. We analyze
these projections and look at the requirements of performing data mining on
such data sets. We conclude that the task scales rather well: we could do the
job today, although it would be expensive. There do not seem to be any
show-stoppers that would prevent us from storing and using a Petabyte dataset
six years from today.


title: Web Services for the Virtual Observatory

abstract:
  Web Services form a new, emerging paradigm to handle distributed access to
resources over the Internet. There are platform independent standards (SOAP,
WSDL), which make the developers? task considerably easier. This article
discusses how web services could be used in the context of the Virtual
Observatory. We envisage a multi-layer architecture, with interoperating
services. A well-designed lower layer consisting of simple, standard services
implemented by most data providers will go a long way towards establishing a
modular architecture. More complex applications can be built upon this core
layer. We present two prototype applications, the SdssCutout and the SkyQuery
as examples of this layered architecture.


title: Spatial Clustering of Galaxies in Large Datasets

abstract:
  Datasets with tens of millions of galaxies present new challenges for the
analysis of spatial clustering. We have built a framework that integrates a
database of object catalogs, tools for creating masks of bad regions, and a
fast (NlogN) correlation code. This system has enabled unprecedented efficiency
in carrying out the analysis of galaxy clustering in the SDSS catalog. A
similar approach is used to compute the three-dimensional spatial clustering of
galaxies on very large scales. We describe our strategy to estimate the effect
of photometric errors using a database. We discuss our efforts as an early
example of data-intensive science. While it would have been possible to get
these results without the framework we describe, it will be infeasible to
perform these computations on the future huge datasets without using this
framework.


title:
A note on fractional derivative modeling of broadband
  frequency-dependent absorption: Model III

abstract:
  By far, the fractional derivative model is mainly related to the modelling of
complicated solid viscoelastic material. In this study, we try to build the
fractional derivative PDE model for broadband ultrasound propagation through
human tissues.


title: Linking Makinson and Kraus-Lehmann-Magidor preferential entailments

abstract:
  About ten years ago, various notions of preferential entailment have been
introduced. The main reference is a paper by Kraus, Lehmann and Magidor (KLM),
one of the main competitor being a more general version defined by Makinson
(MAK). These two versions have already been compared, but it is time to revisit
these comparisons. Here are our three main results: (1) These two notions are
equivalent, provided that we restrict our attention, as done in KLM, to the
cases where the entailment respects logical equivalence (on the left and on the
right). (2) A serious simplification of the description of the fundamental
cases in which MAK is equivalent to KLM, including a natural passage in both
ways. (3) The two previous results are given for preferential entailments more
general than considered in some of the original texts, but they apply also to
the original definitions and, for this particular case also, the models can be
simplified.


title: Does P = NP?

abstract:
  This paper considers the question of P = NP in context of the polynomial time
SAT algorithm. It posits proposition dependent on existence of conjectured
problem that even where the algorithm is shown to solve SAT in polynomial time
it remains theoretically possible for there to yet exist a
non-deterministically polynomial (NP) problem for which the algorithm does not
provide a polynomial (P) time solution. The paper leaves open as subject of
continuing research the question of existence of instance of conjectured
problem.


title: Knowledge Representation

abstract:
  This work analyses main features that should be present in knowledge
representation. It suggests a model for representation and a way to implement
this model in software. Representation takes care of both low-level sensor
information and high-level concepts.


title: Using the DIFF Command for Natural Language Processing

abstract:
  Diff is a software program that detects differences between two data sets and
is useful in natural language processing. This paper shows several examples of
the application of diff. They include the detection of differences between two
different datasets, extraction of rewriting rules, merging of two different
datasets, and the optimal matching of two different data sets. Since diff comes
with any standard UNIX system, it is readily available and very easy to use.
Our studies showed that diff is a practical tool for research into natural
language processing.


title: Implicit Simulations using Messaging Protocols

abstract:
  A novel algorithm for performing parallel, distributed computer simulations
on the Internet using IP control messages is introduced. The algorithm employs
carefully constructed ICMP packets which enable the required computations to be
completed as part of the standard IP communication protocol. After providing a
detailed description of the algorithm, experimental applications in the areas
of stochastic neural networks and deterministic cellular automata are
discussed. As an example of the algorithms potential power, a simulation of a
deterministic cellular automaton involving 10^5 Internet connected devices was
performed.


title:
Symbolic Methodology in Numeric Data Mining: Relational Techniques for
  Financial Applications

abstract:
  Currently statistical and artificial neural network methods dominate in
financial data mining. Alternative relational (symbolic) data mining methods
have shown their effectiveness in robotics, drug design and other applications.
Traditionally symbolic methods prevail in the areas with significant
non-numeric (symbolic) knowledge, such as relative location in robot
navigation. At first glance, stock market forecast looks as a pure numeric area
irrelevant to symbolic methods. One of our major goals is to show that
financial time series can benefit significantly from relational data mining
based on symbolic methods. The paper overviews relational data mining
methodology and develops this techniques for financial data mining.


title:
The STRESS Method for Boundary-point Performance Analysis of End-to-end
  Multicast Timer-Suppression Mechanisms

abstract:
  Evaluation of Internet protocols usually uses random scenarios or scenarios
based on designers' intuition. Such approach may be useful for average-case
analysis but does not cover boundary-point (worst or best-case) scenarios. To
synthesize boundary-point scenarios a more systematic approach is needed.In
this paper, we present a method for automatic synthesis of worst and best case
scenarios for protocol boundary-point evaluation.
  Our method uses a fault-oriented test generation (FOTG) algorithm for
searching the protocol and system state space to synthesize these scenarios.
The algorithm is based on a global finite state machine (FSM) model. We extend
the algorithm with timing semantics to handle end-to-end delays and address
performance criteria. We introduce the notion of a virtual LAN to represent
delays of the underlying multicast distribution tree. The algorithms used in
our method utilize implicit backward search using branch and bound techniques
and start from given target events. This aims to reduce the search complexity
drastically. As a case study, we use our method to evaluate variants of the
timer suppression mechanism, used in various multicast protocols, with respect
to two performance criteria: overhead of response messages and response time.
Simulation results for reliable multicast protocols show that our method
provides a scalable way for synthesizing worst-case scenarios automatically.
Results obtained using stress scenarios differ dramatically from those obtained
through average-case analyses. We hope for our method to serve as a model for
applying systematic scenario generation to other multicast protocols.


title:
Contact-Based Architecture for Resource Discovery (CARD) in Large Scale
  MANets

abstract:
  In this paper we propose a novel architecture, CARD, for resource discovery
in large scale Mobile Ad hoc Networks (MANets) which, may scale up to thousands
of nodes and may span wide geographical regions. Unlike previously proposed
schemes, our architecture avoids expensive mechanisms such as global flooding
as well as complex coordination between nodes to form a hierarchy. CARD is also
independent of any external source of information such as GPS. In our
architecture nodes within a limited number of hops from each node form the
neighborhood of that node. Resources within the neighborhood can be readily
accessed with the help of a proactive scheme within the neighborhood. For
accessing resources beyond the neighborhood, each node also maintains a few
distant nodes called contacts. Contacts help in creating a small world in the
network and provide an efficient way to query for resources beyond the
neighborhood. As the number of contacts of a node increases, the network view
(reachability) of the node increases. Paths to contacts are validated
periodically to adapt to mobility. We present mechanisms for contact selection
and maintenance that attempt to increase reachability while minimizing
overhead. Our simulation results show a clear trade-off between increase in
reachability on one hand, and contact selection and maintenance overhead on the
other. Our results suggest that CARD can be configured to provide a desirable
reachability distribution for different network sizes. Comparisons with other
schemes for resource discovery, such as flooding and bordercasting, show our
architecture to be much more efficient and scalable.


title:
Efficient Micro-Mobility using Intra-domain Multicast-based Mechanisms
  (M&M)

abstract:
  One of the most important metrics in the design of IP mobility protocols is
the handover performance. The current Mobile IP (MIP) standard has been shown
to exhibit poor handover performance. Most other work attempts to modify MIP to
slightly improve its efficiency, while others propose complex techniques to
replace MIP. Rather than taking these approaches, we instead propose a new
architecture for providing efficient and smooth handover, while being able to
co-exist and inter-operate with other technologies. Specifically, we propose an
intra-domain multicast-based mobility architecture, where a visiting mobile is
assigned a multicast address to use while moving within a domain. Efficient
handover is achieved using standard multicast join/prune mechanisms. Two
approaches are proposed and contrasted. The first introduces the concept
proxy-based mobility, while the other uses algorithmic mapping to obtain the
multicast address of visiting mobiles. We show that the algorithmic mapping
approach has several advantages over the proxy approach, and provide mechanisms
to support it. Network simulation (using NS-2) is used to evaluate our scheme
and compare it to other routing-based micro-mobility schemes - CIP and HAWAII.
The proactive handover results show that both M&M and CIP shows low handoff
delay and packet reordering depth as compared to HAWAII. The reason for M&M's
comparable performance with CIP is that both use bi-cast in proactive handover.
The M&M, however, handles multiple border routers in a domain, where CIP fails.
We also provide a handover algorithm leveraging the proactive path setup
capability of M&M, which is expected to outperform CIP in case of reactive
handover.


title: Mathematical basis for polySAT implication operator

abstract:
  The mathematical basis motivating the "implication operator" of the polySAT
algorithm and its function is examined. Such is not undertaken with onerous
rigor of symbolic mathematics; a more intuitive visual appeal being employed to
present some of the mathematical premises underlying function of the
implication operator.


title: A Unified Theory of Shared Memory Consistency

abstract:
  Memory consistency models have been developed to specify what values may be
returned by a read given that, in a distributed system, memory operations may
only be partially ordered. Before this work, consistency models were defined
independently. Each model followed a set of rules which was separate from the
rules of every other model. In our work we have defined a set of four
consistency properties. Any subset of the four properties yields a set of rules
which constitute a consistency model. Every consistency model previously
described in the literature can be defined based on our four properties.
Therefore, we present these properties as a unfied theory of shared memory
consistency.


title: A logical reconstruction of SPKI

abstract:
  SPKI/SDSI is a proposed public key infrastructure standard that incorporates
the SDSI public key infrastructure. SDSI's key innovation was the use of local
names. We previously introduced a Logic of Local Name Containment that has a
clear semantics and was shown to completely characterize SDSI name resolution.
Here we show how our earlier approach can be extended to deal with a number of
key features of SPKI, including revocation, expiry dates, and tuple reduction.
We show that these extensions add relatively little complexity to the logic. In
particular, we do not need a nonmonotonic logic to capture revocation. We then
use our semantics to examine SPKI's tuple reduction rules. Our analysis
highlights places where SPKI's informal description of tuple reduction is
somewhat vague, and shows that extra reduction rules are necessary in order to
capture general information about binding and authorization.


title:
Logic programming in the context of multiparadigm programming: the Oz
  experience

abstract:
  Oz is a multiparadigm language that supports logic programming as one of its
major paradigms. A multiparadigm language is designed to support different
programming paradigms (logic, functional, constraint, object-oriented,
sequential, concurrent, etc.) with equal ease. This article has two goals: to
give a tutorial of logic programming in Oz and to show how logic programming
fits naturally into the wider context of multiparadigm programming. Our
experience shows that there are two classes of problems, which we call
algorithmic and search problems, for which logic programming can help formulate
practical solutions. Algorithmic problems have known efficient algorithms.
Search problems do not have known efficient algorithms but can be solved with
search. The Oz support for logic programming targets these two problem classes
specifically, using the concepts needed for each. This is in contrast to the
Prolog approach, which targets both classes with one set of concepts, which
results in less than optimal support for each class. To explain the essential
difference between algorithmic and search programs, we define the Oz execution
model. This model subsumes both concurrent logic programming
(committed-choice-style) and search-based logic programming (Prolog-style).
Instead of Horn clause syntax, Oz has a simple, fully compositional,
higher-order syntax that accommodates the abilities of the language. We
conclude with lessons learned from this work, a brief history of Oz, and many
entry points into the Oz literature.


title:
A direct time-domain FEM modeling of broadband frequency-dependent
  absorption with the presence of matrix fractional power: Model I

abstract:
  The frequency-dependent attenuation of broadband acoustics is often
confronted in many different areas. However, the related time domain simulation
is rarely found in literature due to enormous technical difficulty. The
currently popular relaxation models with the presence of convolution operation
require some material parameters which are not readily available. In this
study, three reports are contributed to address broadband ultrasound
frequency-dependent absorptions using the readily available empirical
parameters. This report is the first in series concerned with developing a
direct time domain FEM formulation. The next two reports are about the
frequency decomposition model and the fractional derivative model.


title: Parameterized Type Definitions in Mathematica: Methods and Advantages

abstract:
  The theme of symbolic computation in algebraic categories has become of
utmost importance in the last decade since it enables the automatic modeling of
modern algebra theories. On this theoretical background, the present paper
reveals the utility of the parameterized categorical approach by deriving a
multivariate polynomial category (over various coefficient domains), which is
used by our Mathematica implementation of Buchberger's algorithms for
determining the Groebner basis. These implementations are designed according to
domain and category parameterization principles underlining their advantages:
operation protection, inheritance, generality, easy extendibility. In
particular, such an extension of Mathematica, a widely used symbolic
computation system, with a new type system has a certain practical importance.
The approach we propose for Mathematica is inspired from D. Gruntz and M.
Monagan's work in Gauss, for Maple.


title: First-order Logic as a Constraint Programming Language

abstract:
  We provide a denotational semantics for first-order logic that captures the
two-level view of the computation process typical for constraint programming.
At one level we have the usual program execution. At the other level an
automatic maintenance of the constraint store takes place. We prove that the
resulting semantics is sound with respect to the truth definition. By
instantiating it by specific forms of constraint management policies we obtain
several sound evaluation policies of first-order formulas. This semantics can
also be used a basis for sound implementation of constraint maintenance in
presence of block declarations and conditionals.


title: Complete Axiomatizations for Reasoning About Knowledge and Time

abstract:
  Sound and complete axiomatizations are provided for a number of different
logics involving modalities for knowledge and time. These logics arise from
different choices for various parameters. All the logics considered involve the
discrete time linear temporal logic operators `next' and `until' and an
operator for the knowledge of each of a number of agents. Both the single agent
and multiple agent cases are studied: in some instances of the latter there is
also an operator for the common knowledge of the group of all agents. Four
different semantic properties of agents are considered: whether they have a
unique initial state, whether they operate synchronously, whether they have
perfect recall, and whether they learn. The property of no learning is
essentially dual to perfect recall. Not all settings of these parameters lead
to recursively axiomatizable logics, but sound and complete axiomatizations are
presented for all the ones that do.


title:
Causes and Explanations: A Structural-Model Approach. Part II:
  Explanations

abstract:
  We propose new definitions of (causal) explanation, using structural
equations to model counterfactuals. The definition is based on the notion of
actual cause, as defined and motivated in a companion paper. Essentially, an
explanation is a fact that is not known for certain but, if found to be true,
would constitute an actual cause of the fact to be explained, regardless of the
agent's initial uncertainty. We show that the definition handles well a number
of problematic examples from the literature.


title: Evaluation of Coreference Rules on Complex Narrative Texts

abstract:
  This article studies the problem of assessing relevance to each of the rules
of a reference resolution system. The reference solver described here stems
from a formal model of reference and is integrated in a reference processing
workbench. Evaluation of the reference resolution is essential, as it enables
differential evaluation of individual rules. Numerical values of these measures
are given, and discussed, for simple selection rules and other processing
rules; such measures are then studied for numerical parameters.


title: Three New Methods for Evaluating Reference Resolution

abstract:
  Reference resolution on extended texts (several thousand references) cannot
be evaluated manually. An evaluation algorithm has been proposed for the MUC
tests, using equivalence classes for the coreference relation. However, we show
here that this algorithm is too indulgent, yielding good scores even for poor
resolution strategies. We elaborate on the same formalism to propose two new
evaluation algorithms, comparing them first with the MUC algorithm and giving
then results on a variety of examples. A third algorithm using only
distributional comparison of equivalence classes is finally described; it
assesses the relative importance of the recall vs. precision errors.


title:
Cooperation between Pronoun and Reference Resolution for Unrestricted
  Texts

abstract:
  Anaphora resolution is envisaged in this paper as part of the reference
resolution process. A general open architecture is proposed, which can be
particularized and configured in order to simulate some classic anaphora
resolution methods. With the aim of improving pronoun resolution, the system
takes advantage of elementary cues about characters of the text, which are
represented through a particular data structure. In its most robust
configuration, the system uses only a general lexicon, a local morpho-syntactic
parser and a dictionary of synonyms. A short comparative corpus analysis shows
that narrative texts are the most suitable for testing such a system.


title:
Reference Resolution Beyond Coreference: a Conceptual Frame and its
  Application

abstract:
  A model for reference use in communication is proposed, from a
representationist point of view. Both the sender and the receiver of a message
handle representations of their common environment, including mental
representations of objects. Reference resolution by a computer is viewed as the
construction of object representations using referring expressions from the
discourse, whereas often only coreference links between such expressions are
looked for. Differences between these two approaches are discussed. The model
has been implemented with elementary rules, and tested on complex narrative
texts (hundreds to thousands of referring expressions). The results support the
mental representations paradigm.


title: A Virtual Library of Technical Publications

abstract:
  Through a collaborative effort, the Fermilab Information Resources Department
and Computing Division have created a "virtual library" of technical
publications that provides public access to electronic full-text documents.
This paper will discuss the vision, planning and milestones of the project, as
well as the hardware, software and interdepartmental cooperation components.


title:
Using Hierarchical Data Mining to Characterize Performance of Wireless
  System Configurations

abstract:
  This paper presents a statistical framework for assessing wireless systems
performance using hierarchical data mining techniques. We consider WCDMA
(wideband code division multiple access) systems with two-branch STTD (space
time transmit diversity) and 1/2 rate convolutional coding (forward error
correction codes). Monte Carlo simulation estimates the bit error probability
(BEP) of the system across a wide range of signal-to-noise ratios (SNRs). A
performance database of simulation runs is collected over a targeted space of
system configurations. This database is then mined to obtain regions of the
configuration space that exhibit acceptable average performance. The shape of
the mined regions illustrates the joint influence of configuration parameters
on system performance. The role of data mining in this application is to
provide explainable and statistically valid design conclusions. The research
issue is to define statistically meaningful aggregation of data in a manner
that permits efficient and effective data mining algorithms. We achieve a good
compromise between these goals and help establish the applicability of data
mining for characterizing wireless systems performance.


title: Perfectly Secure Message Transmission Revisited

abstract:
  Achieving secure communications in networks has been one of the most
important problems in information technology. Dolev, Dwork, Waarts, and Yung
have studied secure message transmission in one-way or two-way channels. They
only consider the case when all channels are two-way or all channels are
one-way. Goldreich, Goldwasser, and Linial, Franklin and Yung, Franklin and
Wright, and Wang and Desmedt have studied secure communication and secure
computation in multi-recipient (multicast) models. In a ``multicast channel''
(such as Ethernet), one processor can send the same message--simultaneously and
privately--to a fixed subset of processors. In this paper, we shall study
necessary and sufficient conditions for achieving secure communications against
active adversaries in mixed one-way and two-way channels. We also discuss
multicast channels and neighbor network channels.


title: Proving correctness of Timed Concurrent Constraint Programs

abstract:
  A temporal logic is presented for reasoning about the correctness of timed
concurrent constraint programs. The logic is based on modalities which allow
one to specify what a process produces as a reaction to what its environment
inputs. These modalities provide an assumption/commitment style of
specification which allows a sound and complete compositional axiomatization of
the reactive behavior of timed concurrent constraint programs.


title: Gales Suffice for Constructive Dimension

abstract:
  Supergales, generalizations of supermartingales, have been used by Lutz
(2002) to define the constructive dimensions of individual binary sequences.
Here it is shown that gales, the corresponding generalizations of martingales,
can be equivalently used to define constructive dimension.


title:
Gales and supergales are equivalent for defining constructive Hausdorff
  dimension

abstract:
  We show that for a wide range of probability measures, constructive gales are
interchangable with constructive supergales for defining constructive Hausdorff
dimension, thus generalizing a previous independent result of Hitchcock
(cs.CC/0208043) and partially answering an open question of Lutz
(cs.CC/0203017).


title: A Novel Statistical Diagnosis of Clinical Data

abstract:
  In this paper, we present a diagnosis method of diseases from clinical data.
The data are routine test such as urine test, hematology, chemistries etc.
Though those tests have been done for people who check in medical institutes,
how each item of the data interacts each other and which combination of them
cause a disease are neither understood nor studied well. Here we attack the
practically important problem by putting the data into mathematical setup and
applying support vector machine. Finally we present simulation results for
fatty liver, gastritis etc and discuss about their implications.


title: A Chart-Parsing Algorithm for Efficient Semantic Analysis

abstract:
  In some contexts, well-formed natural language cannot be expected as input to
information or communication systems. In these contexts, the use of
grammar-independent input (sequences of uninflected semantic units like e.g.
language-independent icons) can be an answer to the users' needs. A semantic
analysis can be performed, based on lexical semantic knowledge: it is
equivalent to a dependency analysis with no syntactic or morphological clues.
However, this requires that an intelligent system should be able to interpret
this input with reasonable accuracy and in reasonable time. Here we propose a
method allowing a purely semantic-based analysis of sequences of semantic
units. It uses an algorithm inspired by the idea of ``chart parsing'' known in
Natural Language Processing, which stores intermediate parsing results in order
to bring the calculation time down. In comparison with using declarative logic
programming - where the calculation time, left to a prolog engine, is
hyperexponential -, this method brings the calculation time down to a
polynomial time, where the order depends on the valency of the predicates.


title:
Rerendering Semantic Ontologies: Automatic Extensions to UMLS through
  Corpus Analytics

abstract:
  In this paper, we discuss the utility and deficiencies of existing ontology
resources for a number of language processing applications. We describe a
technique for increasing the semantic type coverage of a specific ontology, the
National Library of Medicine's UMLS, with the use of robust finite state
methods used in conjunction with large-scale corpus analytics of the domain
corpus. We call this technique "semantic rerendering" of the ontology. This
research has been done in the context of Medstract, a joint Brandeis-Tufts
effort aimed at developing tools for analyzing biomedical language (i.e.,
Medline), as well as creating targeted databases of bio-entities, biological
relations, and pathway data for biological researchers. Motivating the current
research is the need to have robust and reliable semantic typing of syntactic
elements in the Medline corpus, in order to improve the overall performance of
the information extraction applications mentioned above.


title:
Analysis of Non-Gaussian Nature of Network Traffic and its Implication
  on Network Performance

abstract:
  We analyzed the non-Gaussian nature of network traffic using some Internet
traffic data. We found that (1) the non-Gaussian nature degrades network
performance, (2) it is caused by `greedy flows' that exist with non-negligible
probability, and (3) a large majority of `greedy flows' are TCP flows having
relatively small hop counts, which correspond to small round-trip times. We
conclude that in a network hat has greedy flows with non-negligible
probability, a traffic controlling scheme or bandwidth design that considers
non-Gaussian nature is essential.


title: Sampling from a couple of positively correlated binomial variables

abstract:
  We know that the marginals in a multinomial distribution are binomial
variates exhibiting a negative correlation. But we can construct two linear
combinations of such marginals in such a way to obtain a positive correlation.
We discuss the restrictions that are to be imposed on the parameters of the
given marginals to accomplish such a result. Next we discuss the regression
function, showing that it is a linear function but not homoscedastic.


title: Fast optical layer mesh protection using pre-cross-connected trails

abstract:
  Conventional optical networks are based on SONET rings, but since rings are
known to use bandwidth inefficiently, there has been much research into shared
mesh protection, which promises significant bandwidth savings. Unfortunately,
most shared mesh protection schemes cannot guarantee that failed traffic will
be restored within the 50 ms timeframe that SONET standards specify. A notable
exception is the p-cycle scheme of Grover and Stamatelakis. We argue, however,
that p-cycles have certain limitations, e.g., there is no easy way to adapt
p-cycles to a path-based protection scheme, and p-cycles seem more suited to
static traffic than to dynamic traffic. In this paper we show that the key to
fast restoration times is not a ring-like topology per se, but rather the
ability to pre-cross-connect protection paths. This leads to the concept of a
pre-cross-connected trail or PXT, which is a structure that is more flexible
than rings and that adapts readily to both path-based and link-based schemes
and to both static and dynamic traffic. The PXT protection scheme achieves fast
restoration speeds, and our simulations, which have been carefully chosen using
ideas from experimental design theory, show that the bandwidth efficiency of
the PXT protection scheme is comparable to that of conventional shared mesh
protection schemes.


title: A Survey and a New Competitive Method for the Planar min-# Problem

abstract:
  We survey most of the different types of approximation algorithms which
minimize the number of output vertices. We present their main qualities and
their inherent drawbacks.


title: The partition semantics of questions, syntactically

abstract:
  Groenendijk and Stokhof (1984, 1996; Groenendijk 1999) provide a logically
attractive theory of the semantics of natural language questions, commonly
referred to as the partition theory. Two central notions in this theory are
entailment between questions and answerhood. For example, the question "Who is
going to the party?" entails the question "Is John going to the party?", and
"John is going to the party" counts as an answer to both. Groenendijk and
Stokhof define these two notions in terms of partitions of a set of possible
worlds.
  We provide a syntactic characterization of entailment between questions and
answerhood . We show that answers are, in some sense, exactly those formulas
that are built up from instances of the question. This result lets us compare
the partition theory with other approaches to interrogation -- both linguistic
analyses, such as Hamblin's and Karttunen's semantics, and computational
systems, such as Prolog. Our comparison separates a notion of answerhood into
three aspects: equivalence (when two questions or answers are interchangeable),
atomic answers (what instances of a question count as answers), and compound
answers (how answers compose).


title: Question answering: from partitions to Prolog

abstract:
  We implement Groenendijk and Stokhof's partition semantics of questions in a
simple question answering algorithm. The algorithm is sound, complete, and
based on tableau theorem proving. The algorithm relies on a syntactic
characterization of answerhood: Any answer to a question is equivalent to some
formula built up only from instances of the question. We prove this
characterization by translating the logic of interrogation to classical
predicate logic and applying Craig's interpolation theorem.


title:
Introduction to the CoNLL-2002 Shared Task: Language-Independent Named
  Entity Recognition

abstract:
  We describe the CoNLL-2002 shared task: language-independent named entity
recognition. We give background information on the data sets and the evaluation
method, present a general overview of the systems that have taken part in the
task and discuss their performance.


title: Gossip Based Ad-Hoc Routing

abstract:
  Many ad hoc routing protocols are based on some variant of flooding. Despite
various optimizations, many routing messages are propagated unnecessarily. We
propose a gossiping-based approach, where each node forwards a message with
some probability, to reduce the overhead of the routing protocols. Gossiping
exhibits bimodal behavior in sufficiently large networks: in some executions,
the gossip dies out quickly and hardly any node gets the message; in the
remaining executions, a substantial fraction of the nodes gets the message. The
fraction of executions in which most nodes get the message depends on the
gossiping probability and the topology of the network. In the networks we have
considered, using gossiping probability between 0.6 and 0.8 suffices to ensure
that almost every node gets the message in almost every execution. For large
networks, this simple gossiping protocol uses up to 35% fewer messages than
flooding, with improved performance. Gossiping can also be combined with
various optimizations of flooding to yield further benefits. Simulations show
that adding gossiping to AODV results in significant performance improvement,
even in networks as small as 150 nodes. We expect that the improvement should
be even more significant in larger networks.


title:
Analysis of a Cone-Based Distributed Topology Control Algorithm for
  Wireless Multi-hop Networks

abstract:
  The topology of a wireless multi-hop network can be controlled by varying the
transmission power at each node. In this paper, we give a detailed analysis of
a cone-based distributed topology control algorithm. This algorithm, introduced
in [16], does not assume that nodes have GPS information available; rather it
depends only on directional information. Roughly speaking, the basic idea of
the algorithm is that a node $u$ transmits with the minimum power
$p_{u,\alpha}$ required to ensure that in every cone of degree $\alpha$ around
$u$, there is some node that $u$ can reach with power $p_{u,\alpha}$. We show
that taking $\alpha = 5\pi/6$ is a necessary and sufficient condition to
guarantee that network connectivity is preserved. More precisely, if there is a
path from $s$ to $t$ when every node communicates at maximum power, then, if
$\alpha <= 5\pi/6$, there is still a path in the smallest symmetric graph
$G_\alpha$ containing all edges $(u,v)$ such that $u$ can communicate with $v$
using power $p_{u,\alpha}$. On the other hand, if $\alpha > 5\pi/6$,
connectivity is not necessarily preserved. We also propose a set of
optimizations that further reduce power consumption and prove that they retain
network connectivity. Dynamic reconfiguration in the presence of failures and
mobility is also discussed. Simulation results are presented to demonstrate the
effectiveness of the algorithm and the optimizations.


title: Minimum-Energy Mobile Wireless Networks Revisited

abstract:
  We propose a protocol that, given a communication network, computes a
subnetwork such that, for every pair $(u,v)$ of nodes connected in the original
network, there is a minimum-energy path between $u$ and $v$ in the subnetwork
(where a minimum-energy path is one that allows messages to be transmitted with
a minimum use of energy). The network computed by our protocol is in general a
subnetwork of the one computed by the protocol given in [13]. Moreover, our
protocol is computationally simpler. We demonstrate the performance
improvements obtained by using the subnetwork computed by our protocol through
simulation.


title: Randomized protocols for asynchronous consensus

abstract:
  The famous Fischer, Lynch, and Paterson impossibility proof shows that it is
impossible to solve the consensus problem in a natural model of an asynchronous
distributed system if even a single process can fail. Since its publication,
two decades of work on fault-tolerant asynchronous consensus algorithms have
evaded this impossibility result by using extended models that provide (a)
randomization, (b) additional timing assumptions, (c) failure detectors, or (d)
stronger synchronization mechanisms than are available in the basic model.
Concentrating on the first of these approaches, we illustrate the history and
structure of randomized asynchronous consensus protocols by giving detailed
descriptions of several such protocols.


title: Does NP not equal P?

abstract:
  Stephen Cook posited SAT is NP-Complete in 1971. If SAT is NP-Complete then,
as is generally accepted, any polynomial solution of it must also present a
polynomial solution of all NP decision problems. It is here argued, however,
that NP is not of necessity equivalent to P where it is shown that SAT is
contained in P. This due to a paradox, of nature addressed by both Godel and
Russell, in regards to the P-NP system in total.