Technical Reports

A List by Author: Pavel Krèál

e-mail:

xkrcal(a)fi.muni.cz

home page:

https://www.fi.muni.cz/~xkrcal

Reachability Relations and Sampled Semantics of Timed Systems

by Pavel Krèál, Radek Pelánek, A full version of the paper presented at conference FSTTCS 2005. December 2005, 31 pages.

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

Abstract:

Timed systems can be considered with two types of semantics -- dense time semantics and discrete time semantics. The most typical examples of both of them are real semantics and sampled semantics (i.e., discrete semantics with a fixed time step epsilon). In this work, we study different aspects of sampled semantics. At first, we study reachability relations between configurations of a timed automaton and provide a novel effective characterization of reachability relations. This result is used for proving our main result --- decidability of non-emptiness of a timed automaton omega-language in some sampled semantics (this problem was previously wrongly classified as undecidable). Also, we study relations between real semantics and sampled semantics with respect to different behavioral equivalences. Finaly, we study decidability of reachability problem for stopwatch automata with sampled semantics.

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.

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.