ABSTRACT. During the past decade reversible programming languages have been formalized using various established semantics frameworks. Common to these semantics is that they are weak at specifying the distinct properties of reversible languages at the metalevel, even including the central question whether the defined language is reversible. In this paper, we build upon a metalanguage foundation for reversible languages based on the category of sets and partial injective functions. We exemplify our approach by a step-by-step development of the full semantics of an r-Turing complete reversible while-language with recursive procedures. This leads to a formalization of the semantics in which the reversibility of the language and its inverse semantics are immediate, as well as the inversion of programs written in the language. We discuss further applications and directions for reversible semantics.

ABSTRACT. We consider several reversible finite automaton models which have been introduced over decades, and study some properties of their languages. In particular, we look at the question whether the quotients and atoms of a specific class of reversible languages also belong to that class or not. We consider bideterministic automata, reversible deterministic finite automata (REV-DFAs), reversible multiple-entry DFAs (REV-MeDFAs), and several variants of reversible nondeterministic finite automata (NFAs). It is known that the class of REV-DFA languages is strictly included in the class of REV-MeDFA languages. We show that the classes of complete REV-DFA languages and complete REV-MeDFA languages are the same. We also show that differently from the general case of a REV-DFA language, the minimal DFA of a complete REV-DFA language is a complete REV-DFA. We also show that atoms of any regular language are accepted by reversible NFAs with a single initial and a single final state.

ABSTRACT. The features of determinism and reversibility in P Systems yield different results depending on the derivation mode. For P systems with cooperative rules working in the sequential derivation mode, determinism and reversibility do not allow to obtain universality; syntactic criteria are established for deciding both strong determinism and strong reversibility. In the parallel case, strong determinism and strong reversibility have very restricted computational power.

Deterministic P systems with cooperative rules working in the sequential derivation mode are not universal, whereas P systems working in a maximally parallel derivation mode are universal. When allowing inhibitors or priorities on rules as control mechanisms, the deterministic and reversible P systems become universal with the sequential and maximally parallel derivation modes, whereas only with priorities universality is also known for the strong variants.

ABSTRACT. We consider online algorithms. Typically the model is investigated with respect to competitive ratio. In this paper, we explore two-way automata as a model for online algorithms. We focus on quantum and classical online algorithms. We show that there are problems that can be solved more efficiently by two-way automata with quantum and classical states than classical two-way automata in the case of sublogarithmic memory (sublinear size) even if classical automata get advice bits.

ABSTRACT. We study reversible deterministic finite automata (REV-DFAs), that are partial deterministic finite automata whose transition function induces an injective mapping on the state set for every letter of the input alphabet. We give a structural characterization of regular languages that can be accepted by REV-DFAs. This characterization is based on the absence of a forbidden pattern in the (minimal) deterministic state graph. Again with a forbidden pattern approach, we also show that the minimality of REV-DFAs among all equivalent REV-DFAs can be decided. Both forbidden pattern characterizations give rise to NL-complete decision algorithms. In fact, our techniques allow us to construct the minimal REV-DFA for a given minimal DFA. These considerations lead to asymptotic upper and lower bounds on the conversion from DFAs to REV-DFAs. The presented results were obtained with the co-authors Holger Bock Axelsen, Sebastian Jakobi, and Martin Kutrib.