-
Chapter and Conference Paper
Local disambiguating transformation
-
Chapter and Conference Paper
On the lower bound for minimum comparison selection
-
Chapter and Conference Paper
How good is the adversary lower bound ?
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
Validity test for Floyd's operator-precedence parsing algorithms
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
Time and space bounds in producing certain partial orders
-
Chapter and Conference Paper
On efficiency of interval routing algorithms
-
Chapter and Conference Paper
An almost linear robinson unification algorithm
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
An efficient decision algorithm for the uniform semi-unification problem extended abstract
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...
-
Chapter and Conference Paper
On time-space trade-offs in dynamic graph pebbling
Pebble game on dynamic graphs is studied as an abstract model for the incremental computations. We investigate how the time T and/or the space S is changing according to the number m of insert-edge/delete-edge op...
-
Chapter and Conference Paper
Efficient tree pattern unification
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
Yet Another Modular Technique for Efficient Leader Election
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
Broadcasting on Anonymous Unoriented Tori
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
Efficient deadlock-free multi-dimensional interval routing in interconnection networks
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
Efficient Communication Schemes
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].
-
Chapter and Conference Paper
Changes in Marble Quality After Sodium Sulphate Crystallization and Long-Lasting Freeze-Thaw Testing
This paper summarizes research results about the quality and durability assessment of marbles from Slovakia quarries or outcrops, as well as marbles imported to Slovakia for building purposes through standard ...