Technical Reports

A list with abstracts sorted by year - 2001

How to Employ Reverse Search in Distributed Single Source Shortest Paths

by Lubo¹ Brim, Ivana Èerná, Pavel Krèál, Radek Pelánek, This is a full version of the paper presented at SOFSEM 2001. November 2001, 22 pages.

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

Abstract:

A distributed algorithm for the single-source shortest path problem for directed graphs with arbitrary edge lengths is proposed. The new algorithm is based on relaxations and uses reverse search for inspecting edges and thus avoids using any additional data structures. At the same time the algorithm uses a novel way to recognize a reachable negative-length cycle in the graph which facilitates the scalability of the algorithm.

Proceedings of the Third Learning Language in Logic Workshop

by Lubo¹ Popelínský, Miloslav Nepil, September 2001, 66 pages.

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

Abstract:

The 3rd Learning Language in Logic (LLL) workshop held in August 8-9 in Strasbourg was the follow-up of the previous LLL workshops held in 1999 in Bled, Slovenia, and in 2000 in Lisboa, Portugal. The LLL workshop took place as a joint workshop of ILP`2001 conference. The program of the workshop split into two parts. Work-in-progress papers presented in Aug 8 afternoon are contained in this report.

Control of the Hypertext System Audis Using the Dialogue

by Pavel Gaura, September 2001, 6 pages.

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

Abstract:

The brief description of the blind user oriented hypertext system AUDIS and the principals of the dialogue approach to the system control are described in the paper. The emphasis is placed on the improvements to the control of the system using the dialogues. AUDIS is developed primarily as a support that would help visually impaired students to study various materials.

A Comparison of Algorithms for Normed BPA Processes -- An Experimental Performance Evaluation

by Ale¹ Borek, September 2001, 13 pages.

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

Abstract:

Three algorithms for deciding bisimilarity of normed BPA processes (two using bisimulation base and one using tableau) are evaluated. The evaluation is based on experimental results and some weak and strong points of algorithms with regard to practical use are being shown.

Data Structures for Spatial Data Mining

by Petr Kuba, September 2001, 22 pages.

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

Abstract:

This report deals with spatial data structures for indexing and with their usability for knowledge discovery in spatial data. Huge amount of data processed in spatial data mining (or in data mining generally) requires using some indexing structures to speed up the mining process. Typical data types and operations used in geographic information systems are described in this paper. Then basic spatial data mining tasks and some spatial data mining systems are introduced. Finally, indexing spatial structures for both vector and metric spaces are described and structures used in some spatial data mining systems are presented.

Dialogue Interfaces for Library Systems

by Pavel Cenek, June 2001, 15 pages.

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

Abstract:

Basic principles and structure of a dialogue interface are introduced in the paper. Then features specific for library systems are described. Next part deals with the question how to use these features for the design of a dialogue interface for library systems. Finally some specific library systems are introduced and possibilities how to design a dialogue interface for them is discussed.

Automatic Processing of Czech Inflectional and Derivative Morphology

by Radek Sedláèek, Pavel Smr¾, This is an extended version of the paper which is going to be published in the Proceedings of the Fourth International Conference TSD 2001, LNAI 1902, Pilsen, Czech Republic, September 2001, Springer-Verlag. June 2001, 12 pages.

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

Abstract:

This paper deals with the effective implementation of the new Czech morphological analyser ajka which is based on the algorithmic description of the Czech formal morphology. First, we present two most important word-forming processes in Czech --- inflection and derivation. A brief description of the data structures used for storing morphological information as well as a discussion of the efficient storage of lexical items (stem bases of Czech words) is included too. Then, we describe the morphological analysis algorithm in details and finally, we bring some interesting features of the designed and implemented system ajka together with current statistic data.

Finding Semantically Related Words in Large Corpora

by Pavel Smr¾, Pavel Rychlý, Slightly modified version of the paper published in the Proceedings of TSD 2001, Pilsen, Czech Republic. June 2001, 9 pages.

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

Abstract:

The paper deals with the linguistic problem of fully automatic grouping of semantically related words. We discuss the measures of semantic relatedness of basic word forms and describe the treatment of collocations. Next we present the procedure of hierarchical clustering of a very large number of semantically related words and give examples of the resulting partitioning of data in the form of dendrogram. Finally we show a form of the output presentation that facilitates the inspection of the resulting word clusters.

Distributed Shortest Paths for Directed Graphs with Negative Edge Lengths

by Lubo¹ Brim, Ivana Èerná, Pavel Krèál, Radek Pelánek, This is a full version of the paper presented at FST&TCS 2001. May 2001, 19 pages.

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

Abstract:

A distributed algorithm for single source shortest path problem in an arbitrary directed graph which can contain negative length cycles is presented. The new algorithm is a label-correcting one and uses a novel way for detection of negative length cycles. It works on a network of processors with disjoint memory that communicate via message passing. Correctness of the algorithm is proved. The algorithm is work-efficient as its worst time complexity is O(n^3/p), where p is the number of processors.