The category of Pawlak machines
The chromatic sum of a graph: history and recent developments.
The Chu construction: history of an idea.
The closure under division and a characterization of the recognizable -subsets
The code problem for directed figures
We consider directed figures defined as labelled polyominoes with designated start and end points, with two types of catenation operations. We are especially interested in codicity verification for sets of figures, and we show that depending on the catenation type the question whether a given set of directed figures is a code is decidable or not. In the former case we give a constructive proof which leads to a straightforward algorithm.
The code problem for directed figures
We consider directed figures defined as labelled polyominoes with designated start and end points, with two types of catenation operations. We are especially interested in codicity verification for sets of figures, and we show that depending on the catenation type the question whether a given set of directed figures is a code is decidable or not. In the former case we give a constructive proof which leads to a straightforward algorithm.
The communication hierarchy of time and space bounded parallel machines
We describe the communicating alternating machines and their simulation. We show that, in the case of communicating alternating machines which are bounded, simultaneously, by polynomial time and logarithmic space, the use of three communication levels instead of two does not increase computational power of communicating alternating machines. This resolves an open problem [2] concerning the exact position of machines with three communication levels in the hierarchy.
The Communication Hierarchy of Time and Space Bounded Parallel Machines
We describe the communicating alternating machines and their simulation. We show that, in the case of communicating alternating machines which are bounded, simultaneously, by polynomial time and logarithmic space, the use of three communication levels instead of two does not increase computational power of communicating alternating machines. This resolves an open problem [2] concerning the exact position of machines with three communication levels in the hierarchy.
The completely distributive lattice of machine invariant sets of infinite words
We investigate the lattice of machine invariant classes. This is an infinite completely distributive lattice but it is not a Boolean lattice. The length and width of it is c. We show the subword complexity and the growth function create machine invariant classes.
The Complexity and Construction of Many Faces in Arrangements of Lines and of Segments.
The complexity of classification problems
The complexity of constructing gerechte designs.
The Complexity of Cutting Complexes.
The complexity of lexicographic sorting and searching
An asymptotically optimal sorting algorithm that uses component comparisons to lexicographically sort the set of -tuples is presented. This sorting algorithm builds the static data structure - the so called optimal lexicographic search tree - in which it is possible to perform member searching for an unknown -tuple in at most comparisons. The number of comparisons...
The Complexity of Many Cells in Arrangements of Planes and Related Problems.
The complexity of retina operators.
The complexity of short schedules for uet bipartite graphs
The complexity of short schedules for uet bipartite graphs
We show that the problem of deciding if there is a schedule of length three for the multiprocessor scheduling problem on identical machines and unit execution time tasks in -complete even for bipartite graphs, i.e. for precedence graphs of depth one. This complexity result extends a classical result of Lenstra and Rinnoy Kan [5].
The complexity of systolic dissemination of information in interconnection networks
The complexity of the travelling repairman problem