Part 1.

It is an open problem, stated by A.Sch\"onhage in 1980, whether SMMs are more powerful than KUMs. It is easy to see that SMMs are not weaker than KUMs, i.e., KUMs can be real-time simulated by SMMs. The converse problem is hard and open for today. The difficulty here is that the storage graph of an SMM, being a directed graph, can have unbounded in-degree, while for KUMs having an undirected graph storage this is impossible.

I consider three computational models. Two of them are modifications of tree pointer machines (TPM), which can be viewed as special cases of KUMs. The third model is a variant of Turing machines with the tree-like storage (TTM). I prove that under some (natural) restriction, TPMs and TTMs cannot recognize in real time some language, which is real-time recognizable by SMMs under the same restriction.

I consider machines recognizing the so-called query languages composed of words of the form B$w, where B is supposed to be a code of some database, and w is a query to the database. The restriction is that a machine recognizing a word B$w switches to the read-only mode when it works on the part w of the input word.

These results were reported on the International Conference ``Mathematical Foundations of Computer Science'', Poland, 1991.

Part 2

B-trees are the standard data structure for representing dynamic dictionaries. The main disadvantage of B-trees is that their memory utilization is low, when the lengths of keys stored in a B-tree differ greatly from each other.

I consider a new type of balanced trees, called S(b)-trees, which efficiently maintain variable length keys. The difference with B-trees is that a node capacity for S(b)-trees is evaluated by the total length of keys stored in one node, rather than by their number as in B-trees. The balance condition for S(b)-trees is that any sequence consisting of b+1 neighboring nodes of the tree cannot be compressed into b well-formed nodes.

The main results are:

• S(b)-trees generalize B-trees: B-tree is a special case of S(0)-tree.
• S(b)-trees form a hierarchy by the parameter b. That is if b < b' then the class of S(b')-trees is strictly contained in the class of S(b)-trees.
• A 1 - e utilization lower bound is proved for S(b)-trees, where e is inversely proportional to b.
• Logarithmic running time algorithms of search, insertion, and deletion for the class of S(b)-trees are presented. The correctness of the algorithms is proved.