Technical Reports
A list with abstracts sorted by year - 2003
Object with Roles and VREcko system
by
Lubomír Markovič,
September 2003, 17 pages.
FIMU-RS-2003-06.
Available as Postscript,
PDF.
Abstract:
A model based on objects with roles concept is presented. It provides
both theoretical and practical framework for construction of objects. In this model
the objects with roles can dynamically change the interfaces they support.
Some advantages of creating applications using this concept are discussed on an
example
of a system of virtual reality.
Process Rewrite Systems with Weak Finite-State Unit
by
Mojmír Křetínský,
Vojtěch Řehák,
Jan Strejček,
This is a full version of the paper presented at INFINITY`03. September 2003, 23 pages.
FIMU-RS-2003-05.
Available as Postscript,
PDF.
Abstract:
Various classes of infinite-state processes are often specified by rewrite
systems. We extend Mayr`s Process Rewrite Systems (PRS) by finite-state unit
whose transition function satisfies some restrictions inspired by weak
finite automata. We classify these models by their expressiveness and show
how the hierarchy of new classes (w.r.t. bisimilarity) is related to both
PRS hierarchy of Mayr and two other hierarchies of PRS extensions introduced
in [JKM02, Str02].
Parallel Algorithms for Detection of Negative Cycles
by
Luboš Brim,
Ivana Černá,
Lukáš Hejtmánek,
This is a full version of the paper presented at PARCO 2003. July 2003, 14 pages.
FIMU-RS-2003-04.
Available as Postscript,
PDF.
Abstract:
Several new parallel algorithms for the single source shortest paths
and for the negative cycle detection problems on directed graphs with
real edge weights and given by adjacency list are developed, analysed,
and experimentally compared. The algorithms are to be performed on
clusters of workstations that communicate via a message passing
mechanism.
Relating Hierarchy of Linear Temporal Properties to Model Checking
by
Ivana Černá,
Radek Pelánek,
April 2003, 18 pages.
FIMU-RS-2003-03.
Available as Postscript,
PDF.
Abstract:
The hierarchy of properties as overviewed by Manna and Pnueli relates language,
topology, omega-automata, and linear temporal logic classifications of
properties. We provide new characterisations of this hierarchy in terms of
automata with Buchi, co-Buchi, and Streett acceptance condition and in
terms of Until-Release alternation hierarchy. Afterwards, we analyse the complex
ity
of the model checking problem for particular classes of the hierarchy and
thanks to the new characterisations we identify those linear time temporal
properties for which the model checking problem can be solved more efficiently
than in the general case.
Linear Binary Space Partitions and Hierarchy of Object Classes
by
Petr Tobola,
Karel Nechvíle,
April 2003, 21 pages.
FIMU-RS-2003-02.
Available as Postscript,
PDF.
Abstract:
We consider the problem of constructing binary space partitions for the
set P of d-dimensional objects in d-dimensional space. There are
several classes of objects defined for such settings, which support design
of effective algorithms. We extend the existing the de Berg hierarchy of
classes by the definition of new classes derived
from that one and we show desirability of such an extension. Moreover
we propose a new algorithm, which works on generalized lambda-low
density scenes (defined in this paper) and provides BSP tree of linear size.
The tree can be constructed in O(n log^2 n) time and space, where n is
the number of objects. Moreover, we can trade-off between size and balance
of the BSP tree fairly simply.
Modelling Dialogue Systems by Finite Automata
by
Ivan Kopeček,
Libor Škarvada,
March 2003, 13 pages.
FIMU-RS-2003-01.
Available as Postscript,
PDF.
Abstract:
Based on finite state formalization, this paper deals with
the problem of modelling and automatic programming of dialogue systems.
The approach presented here is based on finding an operator (a construction)
that assigns a corresponding dialogue system to a dialogue corpus.
It will be shown that this construction is universal, in the sense
that each dialogue system can be obtained in this way, and some
related issues (uniqueness, algorithmization and algorithmical
complexity) will be briefly discussed. The theory is illustrated on
a simple example. Some related problems are formulated.
