Default
Reasoning in a Terminological Logic
F.
Sebastiani, U. Straccia
Abstract.
Terminological Logics (TLs) are
knowledge representation formalisms of considerable applicative interest, as
they are specifically oriented to the vast class of application domains that are
describable by means of taxonomic organizations of complex objects. Although the
field of TLs has lately been an active area of investigation, only few
researchers have addressed the problem of extending these logics with the
ability to perform default reasoning.
Such extensions would prove of paramount applicative value, as many application
domains may be formalized by means of monotonic TLs only at the price of
oversimplification. In this paper we show how we can effectively integrate
terminological reasoning and default reasoning, yielding a terminological default logic. The kind of default reasoning we embed
in our TL is reminiscent of Reiter's Default Logic, but overcomes some of its
drawbacks by subscribing to the "implicit" handling of exceptions
typical of the Multiple Inheritance Networks with Exceptions proposed by
Touretzky and others.
Models
and Properties of Abstract Symbol Systems
D.
Jakuš
Abstract.
In this article we discuss properties of the abstract symbol system - a
computational device proposed in [3]. We define two formal models of the
abstract symbol system based on classical computational devices and study their
complexities. We prove the properties of the class PP
that is suggested to be an invariant class for our device. Our models are shown
to be superior (in terms of the computational complexity) to the devices they
originated from.
We deal with properties of complexity measures introduced for the
abstract symbol system, namely computational and descriptional complexities. We
prove the possibility of improvement in computational complexity for any
function bounding the descriptional complexity.
On
Epistasis
H.
van Hove, A. Verschoren
Abstract.
In this note, we compare two previously introduced notions
of epistasis and prove that they are essentially equivalent.
Armstrong
Relations, Functional Dependencies and Strong Dependencies
J.
Demetrovics, Vu Duc Thi
Abstract.
The main purpose of this paper is to give some results related to Armstrong
relations for functional dependency (FD) and strong dependency (SD). In this
paper, the dependency inference problem, the FD-relation implication problem and
the FD-relation equivalence problem are solved by combinatorial algorithms. We
prove that the time complexity of finding a set of antikeys for a given relation
scheme S is exponential in the number
of attributes. Keys play important roles for the logical and structural
investigation of functional dependency in the relational datamodel. We present a
computational connection between relations, relation schemes, sets of antikeys
and sets of minimal keys. Constructions of relation R,
relation scheme S, for which KR = KS,
where KR,
KS are the sets of minimal keys R,
S of the FD-relation key-implication problem and the FD-relation
key-equivalence problem are also presented. We show that the time complexity of
finding a relation R of a given
relation scheme
S such that KR = KS
is
exponential in the size of S. We give
a class of relations and relation schemes, for which the above problems are
solved in a polynomial time. For a given relation R
and a relation scheme S we
introduce the following two problems:
1.
Decide whether
each key of S is key of R.
2.
Decide whether all keys of R
are keys of S.
We
show that the first problem is solved in polynomial time, but the second problem
is co-NP-complete. In the second part of the paper the concept of strong scheme
is introduced. We prove that the membership problem for strong dependencies is
solved by an algorithm in polynomial time. We give a necessary and sufficient
condition for a relation to be Armstrong relation of a given strong scheme. We
present four important problems for logical and structural investigation of
strong dependencies: the construction of Armstrong relation of a given strong
scheme, the construction of strong scheme SDs of which hold in a given relation,
the SD-relation implication problem, the SD-relation equivalence problem.
We prove that above problems are solved by polynomial time algorithm.
Implementation
Analysis of Fast Matrix Multiplication Algorithms on Shared Memory Computers
E.
Francomano, A. Tortotici-Macaluso, M. Vajteršic
Abstract.
The paper presents analysis of matrix multiplication algorithms from the point
of view of their efficient implementation on shared memory machines. The
algorithms of Winograd and Strassen have been analyzed and implemented
considering the memory accesses, the stride and data transfer overheads. A
particular attention is paid to the parallel implementation of the modified
recurrence-free variant of the Strassen's algorithm.