Object with Roles and VREcko system

by Lubomír Markovič, September 2003, 17 pages.

FIMU-RS-2003-06. Available as Postscript, PDF.


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.


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.


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.


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.


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.


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.