-
-
-
The paper discusses the problem of combining unreliable pieces of
evidence in a (generalized) probabilistic setting. The popular Dempster's
rule for combining evidence in DempsterShafer theory is criticized on two
accounts. Firstly, Dempster's rule is claimed to be invalid, and secondly,
the rul...
-
Tiling problems provide for a very simple and transparent mechanism for
encoding machine computations. This gives rise to rather simple master
reductions showing various versions of the tiling problem complete for
various complexity classes. We investigate the potential for using these
tiling...
-
My field is mathematical logic, with a special interest in constructivism,
and I would not dare to call myself a computer scientist. But some computer
scientists regard my work as a contribution to their field; and in this text I
shall try to explain how this is possible, by taking a look at the ...
-
The famous SierpinskiErd¨os Duality Theorem states, informally, that any
theorem about effective measure 0 and/or first category sets is also true
when all occurrences of ``effective measure 0'' are replaced by ``first
category'' and vice versa. This powerful and nice result shows that
``mea...
-
Inspection of the current literature on Design Patterns shows that the Prime
Directive for this community is Pragmatics. It hardly matters what patterns
are, or how Patterns are represented formally or syntactically. What does
matter is their role in enhancing the reuse of good solutions to re...
-
We investigate the frequency of complete sets for various complexity classes
within EXP under nonadaptive reductions in the sense of resource bounded
measure. We show that these sets are rare:
* The sets that are complete under <=^p_{n^\alpha-tt}reductions for NP, the
levels of the po...
-
Upper semilattice of binary strings with the relation
``x is simple conditional to y''
Andrei Muchnik, Andrei Romashchenko, Alexander Shen, Nikolai Vereshagin
We study the properties of the set of binary strings with the relation
``the Kolmogorov complexity of x conditional to y is small''. W...
-
We give resolution based decision procedures for the guarded fragment
of ([ANB96]), and for the loosely guarded fragment of ([vBenthem97]).
The relevance of the guarded fragments lies in the fact that many modal
logics can be translated into them. In this way the guarded fragments
act as a framew...
-
In this paper some ideas for adding structure to belief bases are
presented. Structured belief bases can be seen as graphs, where each
node is a belief and two nodes are adjacent if and only if they are
related. Some notions of relatedness are defined. We then show how
this extra structure can be...