Acta Informatica

Various methods, such as address-calculation sorts, distribution counting sorts, radix sorts, and bucket sorts, use the values of the numbers being sorted to increase efficiency but do so at the expense of requiring additional storage space. In this paper, a specific implementation of bucket sort is presented whose primary advantanges are that (i) linear average-time performance is achieved with an additional amount of storage equal to any fraction of the number of elements being sorted and (ii) no linked-list data structures are used (all sorting is done with arrays). Analytical and empirical results show the trade-off between the additional storage space used and the improved computational efficiency obtained. Computer simulations show that for lists containing 1,000 to 30,000 uniformly distributed positive integers, the sort developed here is faster than both Quicksort and a standard implementation of bucket sort. Furthermore, the running time increases with size at a slower rate.

The set of all primitive words Q over an alphabet X was first defined and studied by Shyr and Thierrin (Proceedings of the 1977 Inter. FCT-Conference, Poznan, Poland, Lecture Notes in Computer Science 56. pp. 171–176 (1977)). It showed that for the case |X| ≥ 2, the set along with $${Q^{(i)} = \{f^i\,|\,f \in Q\}, i\geq 2}$$ are all disjunctive. Since then these disjunctive sets are often be quoted. Following Shyr and Thierrin showed that the half sets $${Q_{ev} = \{f \in Q\,|\,|f| = {\rm even}\}}$$ and Q od = Q \ Q ev of Q are disjunctive, Chien proved that each of the set $${Q_{p,r}= \{u\in Q\,|\,|u|\equiv r\,(mod\,p) \},\,0\leq r < p}$$ is disjunctive, where p is a prime number. In this paper, we generalize this property to that all the languages $${Q_{n,r}= \{u\in Q\,|\,|u|\equiv r\,(mod\,n) \},\, 0\leq r < n}$$ are disjunctive languages, where n is any positive integer. We proved that for any n ≥ 1, k ≥ 2, (Q n,0) k are all regular languages. Some algebraic properties related to the family of languages {Q n,r | n ≥ 2, 0 ≤ r < n } are investigated.

This paper presents a method for obtaining the optimum checkpoint interval of a transaction processing computer system subject to time dependent failures. The system uses checkpointing to create a valid system state, and roll-back in order to recover from failures. Maximizing system availability we derive the optimum checkpoint interval as a function of the load of the system and of the time dependent failure rate. The results are illustrated numerically for the Weibull failure rate.

Sei G eine kontextsensitive Grammatik. Gc∫ bezeichne den kontextfreien Kern von G. In dieser Arbeit wird die Zeitkomplexität des folgenden Problems untersucht. Das Normalisierungsproblem Sei τ ein Ableitungsbaum bezüglich Gc∫; ist τ auch ein Ableitungsbaum bezüglich G? Es wird gezeigt, daß im allgemeinen das Normalisierungs-problem NP-vollständig ist. Andererseits gibt es zu jeder kontextsensitiven Sprache L eine kontextsensitive Grammatik G, für welche das Normalisierungsproblem in Polynomzeit lösbar ist.

We present space-efficient-O(log2 n)-deterministic algorithms for some graph theoretical problems such as planarity testing, producing a plane embedding, finding minimum cost spanning trees, obtaining the connected, biconnected and triconnected components of a graph. Previous planarity algorithms used Ω(n) space. Several algorithms are based on a space-efficient matrix inversion method. The same bounds hold for uniform circuit depth.