Execution
models for a massively parallel prolog implementation. Part II
P.
Kacsuk
Abstract.
The Generalized
Dataflow Model is introduced for OR- and pipeline AND-parallel execution of
logic programs. A higher level abstraction of the dataflow model called the
Logicflow Model is applied to
implement Prolog on massively parallel distributed memory computers.
Properties of the Logicflow Model concerning the logic programming execution
scheme are proved in detail. Based on the two execution models the Distributed
DataDriven Prolog Abstract Machine (3DPAM) can be defined. It is shown how the
instructions of the 3DPAM are derived from the dataflow and logicflow nodes in
the case of alternative clauses.
bk-complete problems and greediness
R.
Szelepcsényi
Abstract.
Kintala and
Fischer [7] defined the limited nondeterminism hierarchy within NP, the so
called b
hierarchy. bk
is the class of
languages recognized by polynomial time bounded Turing machines that make at
most O(logk n) nondeterministic moves, where n is the length of the input.
It
has been conjectured that "by restricting the amount of nondeterminism in
NP-complete problems, we do not seem to obtain complete problems for bk
[4]". We demonstrate that this statement is incorrect under what seems to
us to be the natural interpretation
of the term "restricting the amount of nondeterminism". We develop the
concept of limited nondeterminism-preserving reductions, and obtain complete
problems for bk
by restricting the amount of nondeterminism in NP-complete problems. We also
discuss the connections between b
hierarchy completeness and greedy algorithms; we show that using greediness we
can define many complete problems for b.
table
rounding problem
J.
íma
Abstract.
From time to
time, people dealing with accounting are faced with the following table rounding
problem. Consider a m x n
table with numerical values (e.g., amount of money) in which the last column
contains check sums of numbers in particular rows. Similarly, the last row
consists of column check sums. A new table is to be produced in which the
original numbers, and check sums, are rounded off (e.g. to integers). However,
the classical rounding procedure (e.g., rounding fractions smaller than 0.,5
down, otherwise up) can generally violate the validity of sums. Therefore, the
possibility to round off the non-integer numbers in the table to adjacent
integers (i.e., either up or down independently on their fractions) is explored
in order to preserve the check sums. We formulate a necessary and sufficient
condition stating when rounding, which is consistent with prescribed (integer)
check sums, exists. We also prove that when rounding of check sums is not given
as a part of the input and, at the same time, the sums are allowed to be rounded
to adjacent integers such rounding always exists. Using maximum flow algorithm
the required rounding can be found in both cases in polynomial time O((m
+ n)3) (provided that
it exists). Moreover, rounding with the minimal sum of absolute round-errors is
computed within O(mn(m + n)2)
time.
Describing
candidate keys by hypergraphs
J.
Demetrovics, Vu Duc Thi
Abstract.
In the paper algorithms are given that find a minimal transversal and all
minimal transversals, respectively, of a hypergraph. Some other computational
problems related to the hypergraphs are also studied. As applications, new
characterizations of candidate keys of a relational datamodel are given, and new
algorithms that find all candidate keys of a relation and a relation scheme,
respectively, are presented.
Random
walks and Brownian notion
T.
Castell
Abstract.
Papadimitriou
proved in [7] that the random walk algorithm is a polynomial Monte-Carlo algorithm for the satisfiable instances
of 2SAT. We present a convergence criterion that generalizes it. We used it to
demonstrate that the random walk algorithm is also a polynomial Monte-Carlo
algorithm for the satisfiable Horn-renamable instances of SAT without unitary
clauses.