SOFSEM 2001: Theory and Practice of Informatics
28th Conference on Current Trends in Theory and Practice of Informatics Piešt’any, Slovak Republic, November 24 – December 1, 2001 Proceedings
Book and Conference Proceedings
28th Conference on Current Trends in Theory and Practice of Informatics Piešt’any, Slovak Republic, November 24 – December 1, 2001 Proceedings
Chapter and Conference Paper
In this paper we present a general and still flexible modular technique for the design of efficient leader election algorithms in N-node networks. Our approach can be viewed as a generalization of the previous me...
Chapter and Conference Paper
We consider broadcasting on asynchronous anonymous totally unoriented n × m torus, where N=n·m is the number of nodes. We present a broadcasting algorithm with message complexity 1.43 N+O(n+m) and prove the lower...
Chapter and Conference Paper
We present deadlock-free packet (wormhole) routing algorithms based on multi-dimensional interval schemes for certain multiprocessor interconnection networks and give their analysis in terms of the compactness...
Chapter and Conference Paper
We give a survey of recent theoretical results for communication problems in point to point networks. This survey is based on the previous surveys in [57, 25].
Book and Conference Proceedings
22nd International Symposium, MFCS '97 Bratislava, Slovakia, August 25–29, 1997 Proceedings
Chapter and Conference Paper
The problem of many-to-one unification, i.e. a simultaneous weak unification of pattern terms against all subterms of a target term, is studied for linear terms. Two algorithms proposed in [10] generalize eith...
Chapter and Conference Paper
An algorithm to decide whether a pair of terms is semi-unifiable is presented. It is based on compact graph representation of terms and on efficient implementation of variable replacements. The time complexity...
Article
Further asymptotical improvement of original Robinson's unification idea is presented. By postponing the so-called occur-check in Corbin and Bidoit's quadratic rehabilitation of the Robinson algorithm at the e...
Chapter and Conference Paper
Chapter and Conference Paper
Further asymptotical improvement of original Robinson's unification idea is presented. By postponing the so-called occur-check in Corbin and Bidoit's quadratic rehabilitation of the Robinson algorithm at the e...
Chapter and Conference Paper
Chapter and Conference Paper
The classes of languages definable by operator-precedence grammars and by Floyd's operator-precedence algorithms are studied. Operator-precedence languages are shown to be a proper superclass of languages acce...
Chapter and Conference Paper
In this paper we discuss the strength of the adversary argument in establishing lower bounds on the complexity of certain sorting-type problems. The relationship between adversary argument and so called inform...
Chapter and Conference Paper
Chapter and Conference Paper