Preprints of IIS SB RAS, 1997

Preprint 46
Michael V. Leonov, Alexey G. Nikitin
An efficient algorithm for a closed set of boolean operations on polygonal regions in the plane

This paper presents a simple and fast algorithm for computing union, intersection, difference and symmetrical difference of boundary represented polygonal regions in the plane. The algorithm explicitly copes with degenerate cases and vertices of high degree so that the output of the algorithm satisfies its input restrictions. An expected running time of the algorithm is O(n log*n + k + z log n), where n (respectively z) is the total number of edges (respectively contours) in polygons describing input regions and k is the number of intersections between the edges. The presented algorithm outperforms most of known algorithms for polygon set operations and is relatively easy to implement.

Preprint 43
Kasyanov V.N., Nesgovorova G.P.
Simics - the information system for supporting humanity researches in the field of the culture

A project of the information system SIMICS for humanity investigations in the field of culture is considered. This information system is aimed at processing of knowledge in the field of modern music and cinema and also in the field of informatics history so far as we regard it as an element of the culture in the modern society. We tried to reflect regional features during gaining information data for this information system. A descriptions of a themes peculiarity of information system and its structure are given. The information system SIMIKS is intented for art critics, teachers and students of a conservatoire, institutes and faculties of the culture and for everyone who is interested in the problems and hystory of the modern culture.

Preprint 41
A. V. Votintseva
Investigation of equivalence notions for event structures

R. Glabbeek and U. Goltz have introduced a number of bisimulations on event structures: interleaving, step, pomset, history preserving, and established their relationships. F. Cherief considered the variant of back-and-forth bisimulation in interleaving semantics. The notion of weak bisimulation were investigated for labelled transition systems by R. Milner. In this paper the back-and-forth variants of bisimulations in different semantics are considered for event structures, a number of bisimulations, reflecting explicitly concurrency and conflict between events in a structure, are defined. The weak variants (taking into account the invisible nature of silent move) of the mentioned bisimulations are introduced. The complete hierarchy of the all considered equivalence notions was established in the paper. For each recently introduced bisimulation we investigated the question about its preservation under the operation of action refinement. was established.

Preprint 40
I. S. Anureev
Formula rewriting systems

A new method of automatic proving is suggested. The method is based on formula rewriting systems, a generalization of term rewriting systems. The main concepts of the theory of formula rewriting systems are given. The properties of correctness and termination for such systems are considered and sufficient conditions which guarantee the fulfilment of these properties are stated.




You are reporting a typo in the following text:
Simply click the "Send typo report" button to complete the report. You can also include a comment.