Invited Speakers

Marián Dvorský (CEAi Slovakia)

Large Scale Sorting in Distributed Data Processing Systems

External sorting is a well-studied problem in computer science. However, its application in modern, distributed, large-scale, fault-tolerant, data processing systems, such as MapReduce, is not as widely known. In this talk I will describe the problem of large-scale sorting, its role in data processing systems, recent advances in implementation of sorting in real-world cloud systems, and open problems.

Christos Kapoutsis (Carnegie Mellon University in Qatar)

Alternation in Two-Way Finite Automata

In this talk we will overview two-way alternating finite automata (2AFAs). We will first list and reconcile the various definitions of what a 2AFA is, as they have appeared in the literature; as well as the various corresponding definitions of what it means for a 2AFA to accept its input. We will then study the computability and size complexity of 2AFAs. A large part of this latter study will involve the polynomial-size alternating hierarchy and its relation to its natural variants in terms of predicates and oracles. We will conclude with a list of open questions.

Sebastian Maneth (Universität Bremen, Germany)

Static Garbage Collection

We consider compositions of tree transducer and review a technique known as "static garbage collection". Garbage in a composition of two transducers are output symbols of the first transducer, that are deleted by the second transducer. Through iterated backward type inference, we are able to restrict the output of the first transducers to symbols that are not deleted by the last transducer. Several interesting results can be proven using the technique. For instance, if a function in the macro tree transducer composition hierarchy is of linear size increase, then it can be realized by just a single transducer. We present further applications of the technique.

Alexander Okhotin (St. Petersburg State University, Russia)

Graph-Walking Automata: From Whence They Come and Whither They Are Bound

Graph-walking automata are finite automata walking on graphs given as an input; tree-walking automata and two-way finite automata are their well-known special cases. Graph-walking automata can be regarded both as a model of navigation in an unknown environment, and as a generic computing device, with the graph representing the states of its memory. This talk presents the known results on these automata, ranging from their limitations in traversing graphs, studied already in the 1970s, to the recent work on the logical reversibility of their computations.

Helmut Seidl (Technische Universität München, Germany)

Deciding Equivalence of Tree Transducers by Means of Precise Abstract Interpretation

This presentation reviews the construction of the earliest normal form for top-down tree transducers. It will indicate how this construction allows to decide equivalence of deterministic top-down tree transducers and how it can be used to decide whether a top-down tree transducer is functional. The earliest normal form also opens up the way for decidability of equivalence for functional sequential tree-to-string transducers, as well as for macro tree transducers, at least if the nesting of their states inside parameters is restricted. Interestingly, both the construction of the earliest normal form as well as its application to equivalence for classes of macro tree transducers rely on techniques borrowed from precise abstract interpretation.