KUTRIB , Martin

The paper investigates classes of languages of innite words with respect to the acceptance conditions of the nite automata recognizing them. Some new natural classes are compared with the Borel hierachy. In particular, it is proved that (fin, =) is as high as F R σ and G R δ. As a side eect, it is also proved that in this last case, considering...

Deterministic one-way Turing machines with sublinear space bounds are systematically studied. We distinguish among the notions of strong, weak, and restricted space bounds. The latter is motivated by the study of P automata. The space available on the work tape depends on the number of input symbols read so far, instead of the entire input. The...

Deterministic one-way Turing machines with sublinear space bounds are systematically studied. We distinguish among the notions of strong, weak, and restricted space bounds. The latter is motivated by the study of P automata. The space available on the work tape depends on the number of input symbols read so far, instead of the entire input. The...

Reversible computation allows computation to proceed not only in the standard, forward direction, but also backward, recovering past states. While reversible computation has attracted interest for its multiple applications, covering areas as different as low-power computing , simulation, robotics and debugging, such applications need to be...