Technical Reports

A list with abstracts sorted by year - 1999

Timetabling with Annotations

by Hana Rudová, Ludìk Matyska, December 1999, 17 pages.

FIMU-RS-99-09. Available as Postscript, PDF.

Abstract:

One of the peculiarities of university timetabling problems lies in their huge complexity and the easy transition between complex constrained system to an over-constrained one. The Faculty of Informatics timetabling problem represents very complex scheduling and resource allocation problem as individual timetable for every student has to be scheduled with respect to course pre-enrollment informations. Variables` annotations were proposed to define preferences of variables in constraints and they serve as a source for computing variable ordering in optimization problems where the search space is too large to be fully traversed and explored. Annotations suggest a route through this space which leads quickly to at least sub-optimal solutions. Annotations may even help to find preferred solutions first as they instantiate preferred values in the domain of variables as soon as possible.

A Fully Abstract Semantics for a Version of Synchronous Concurrent Constraint Programming

by Jean-Marie Jacquet, Lubo¹ Brim, David Gilbert, Mojmír Køetínský, December 1999, 62 pages.

FIMU-RS-99-08. Available as Postscript, PDF.

Abstract:

Concurrent constraint programming is classically based on asynchronous communication via a shared store. In previous work, we presented a new version of the ask and tell primitives which features synchronicity, our approach being based on the idea of telling new information just in the case that a concurrently running process is asking for it. We turn in this paper to a semantic study of this new framework, called Scc.

It is first shown to be different in nature from classical concurrent constraint programming and from CCS, a classical reference in traditional concurrency theory. This suggests the interest of new semantics for Scc. To that end, an operational semantics reporting the steps of the computations is presented. A denotational semantics is then proposed. It uses monotonic sequences of labelled pairs of input-output states, possibly containing gaps, and ending - according to the logic programming tradition - with marks reporting success or failure. This denotational semantics is proved to be correct with respect to the operational semantics as well as fully abstract.

Linear BSP Tree in the Plane for Set of Segments with Low Directional Density

by Petr Tobola, Karel Nechvíle, A full version of the paper which appeared in Proceedings WSCG`99. September 1999, 20 pages.

FIMU-RS-99-07. Available as Postscript, PDF.

Abstract:

We introduce a new BSP tree construction method for set of segments in the plane. Our algorithm is able to create BSP tree of linear size in the time O(n log^3 n) for set of segments with low directional density (i.e. it holds for arbitrary segment s_i from such set, that a line created as extension of this segment doesn`t intersect too many other segments from the set in a near neighbourhood of s_i) and a directional constant delta belonging to this set.

On Birkhoff`s Aesthetic Measure of Vases

by Tomá¹ Staudek, September 1999, 8 pages.

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

Abstract:

The report discusses contribution of Birkhoff`s aesthetic measure to formal aesthetic evaluation of regular geometrical objects, namely Chinese vases. Characteristics of aesthetic measure function are considered in order to verify correctness of such application and extended Birkhoff`s aesthetic measure is then introduced.

Approximating Weak Bisimulation on Basic Process Algebra

by Jitka Støíbrná, This work has been presented at MFCS`99. September 1999, 18 pages.

FIMU-RS-99-05. Available as Postscript, PDF.

Abstract:

The maximal strong and weak bisimulations on any class of processes can be obtained as the limits of decreasing chains of binary relations, approximants. In the case of strong bisimulation and Basic Process Algebras this chain has length at most omega which enables semidecidability of strong bisimilarity. We show that it is not so for weak bisimulation where the chain can grow much longer, and discuss the implications this has for the problem of (semi)decidability of weak bisimilarity.

CED -- Program for Corpora Editing

by Marek Veber, September 1999, 9 pages.

FIMU-RS-99-04. Available as Postscript, PDF.

Abstract:

The article is concerned with editing of corpora, tagged corpora in particular. It introduces a corpus editor (program ced) and a software library for work with corpora. The following functions are described: Journaling of changes, document editing, working with a list of localities in the course of making aggregate corrections, co-operating with a corpus manager, independence of the physical corpora`s data storage.

Corpus-based Rules for Czech Verb Discontinuous Constituents

by Eva ®áèková, Karel Pala, This is an adapted version of the paper accepted for printing in the Proceedings of TSD`99. August 1999, 6 pages.

FIMU-RS-99-03. Available as Postscript, PDF.

Abstract:

In this paper we present a method for extracting general structures of the verb groups from a tagged and fully disambiguated corpus and consecutive exploitation of these structures for the building a formal grammar in the Prolog DCG fashion. Our goal is to apply them as a rules for the analysis of the Czech verb groups in the non-disambiguated grammatically tagged Czech corpus texts. The problem of the recognition of verb discontinuous constituents in Czech is also approached and obtained statistical data are presented.

Complexity Issues of the Pattern Equations in Idempotent Semigroups

by Ondøej Klíma, Jiøí Srba, August 1999, 14 pages.

FIMU-RS-99-02. Available as Postscript, PDF.

Abstract:

A pattern equation is a word equation of the form X=A where X is a sequence of variables and A is a sequence of constants. The problem whether X=A has a solution in a free idempotent semigroup (free band) is shown to be NP--complete.

On the Pattern Equations

by Ivana Èerná, Ondøej Klíma, Jiøí Srba, This is a full version of the paper accepted to SOFSEM`99. July 1999, 11 pages.

FIMU-RS-99-01. Available as Postscript, PDF.

Abstract:

Word equation in a special form X=A, where X is a sequence of variables and A is a sequence of constants, is considered. The problem whether X=A has a solution over a free monoid (PATTERN EQUATION problem) is shown to be NP--complete. It is also shown that disjunction of a special type equation systems and conjunction of the general ones can be eliminated. Finally, the case of stuttering equations where the word identity is read modulo xx=x is mentioned.