Technical Report MSC-2015-20

Title: Closure under reversal of languages over infinite alphabets: a case study
Authors: Liat Peterfreund
Supervisors: Michael Kaminski
PDFCurrently accessibly only within the Technion network
Abstract: There are two main computational models over infinite alphabets. The first, Finite-Memory Automata, were first introduced by Kaminski and Francez in 1994. The second, Pebble Automata, on which we will focus, were first introduced by Neven, Schwentick and Vianu in 2001. Both models accept precisely the set of regular languages when restricted to finite alphabets but are orthogonal.

In essence, Pebble Automata are finite state automata equipped with a finite number of pebbles. Each pebble can serve as the head of the automaton or point at a single position, exclusively and alternately. The pebbles are placed on the input word in the stack discipline. That is, the first pebble placed is the last to be lifted. One pebble can only point at one position and the most recently placed pebble serves as the head of the automaton. The automaton moves from one configuration to another depending on the symbol the head pebble points at and the equality tests among symbols under the other pebbles and among other pebbles' positions. As shown by Neven, Schwentick and Vianu, languages over infinite alphabets accepted by Pebble Automata possess desirable closure properties such as intersection, union, concatenation and completion. Nevertheless, Pebble Automata languages have an undesirable property for application: undecidability of its emptiness problem (in contrast to Finite Memory Automata).

The thesis deals with languages over infinite alphabets that are accepted by weak Pebble Automata (which is one of the variants of Pebble Automata). We examine similarity between these languages and regular languages by examining their closure properties. We prove that languages accepted by weak Pebble Automata are not closed under reversal. That it, there exists a language that is accepted by weak Pebble Automata, whereas its reversal is not. For the proof, we establish a kind of periodicity of an automaton's computation over a specific set of words. This periodicity is partly due to the finiteness of the automaton and partly due to the word's structure. The periodicity enables us to present a word, such that during the automaton's run on it there are two different, yet indistinguishable, configurations. Thus, we can remove a part of the input without affecting acceptance. Choosing the right language leads us to the desired result.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2015
To the main CS technical reports page

Computer science department, Technion