Detecting the relevant attributes of an unknown target concept is an important and well studied problem in algorithmic learning. Simple greedy strategies have been proposed that seem to perform reasonably well in practice if a sufficiently large random subset of examples of the target concept is provided. Introducing a new ... more >>>

Binary search trees are one of the most fundamental data structures. While the height of such a tree may be linear in the worst case, the average height with respect to the uniform distribution is only logarithmic. The exact value is one of the best studied problems in average case ... more >>>

Presented is an algorithm (for learning a subclass of erasing regular pattern languages) which can be made to run with arbitrarily high probability of success on extended regular languages generated by patterns $\pi$ of the form $x_0 \alpha_1 x_1 ... \alpha_m x_m$ for unknown $m$ but known $c$, from number ... more >>>

The subclass of directed series-parallel graphs plays an important role in computer science. Whether a given graph is series-parallel is a well studied problem in algorithmic graph theory, for which fast sequential and parallel algorithms have been developed in a sequence of papers. Also methods are known to solve the ... more >>>

In parallel and distributed computing scheduling low level tasks on the available hardware is a fundamental problem. Traditionally, one has assumed that the set of tasks to be executed is known beforehand. Then the scheduling constraints are given by a precedence graph. Nodes represent the elementary tasks and edges the ... more >>>

A model for parallel and distributed programs, the dynamic process graph (DPG), is investigated under graph-theoretic and complexity aspects. Such graphs embed constructors for parallel programs, synchronization mechanisms as well as conditional branches. They are capable of representing all possible executions of a parallel or distributed program in a very ... more >>>

For ordinary circuits with a fixed upper bound on the maximal fanin of gates it has been shown that logarithmic redundancy is necessary and sufficient to overcome random hardware faults. Here, we consider the same question for unbounded fanin circuits that in the noiseless case can compute Boolean functions in ... more >>>

A new algorithm for learning one-variable pattern languages from positive data is proposed and analyzed with respect to its average-case behavior. We consider the total learning time that takes into account all operations till convergence to a correct hypothesis is achieved. For almost all meaningful distributions defining how the pattern ... more >>>

This paper tries to fully characterize the properties and relationships of space classes defined by Turing machines that use less than logarithmic space - may they be deterministic, nondeterministic or alternating (DTM, NTM or ATM). We provide several examples of specific languages and show that such machines are unable to ... more >>>

It was shown some years ago that the computation time for many important Boolean functions of n arguments on concurrent-read exclusive-write parallel random-access machines (CREW PRAMs) of unlimited size is at least f(n) = 0.72 log n. On the other hand, it is known that every Boolean function of n ... more >>>