^March April – 2007 ^May

An instance of the sorting buffer problem consists of a metric space and a server, equipped with a finite-capacity buffer capable of holding a limited number of requests. An additional ingredient of the input is an online sequence of requests, each of which is characterized by a destination in the given metric; whenever a request arrives, it must be stored in the sorting buffer. At any point in time, a currently pending request can be served by drawing it out of the buffer and moving the server to its corresponding destination. The objective is to serve all input requests in a way that minimizes the total distance traveled by the server.

In this paper, we focus our attention on instances of the problem in which the underlying metric is either an evenly-spaced line metric or a continuous line metric. Although such restricted settings may appear to be very simple at first glance, we demonstrate that they still capture one of the most fundamental problems in the design of storage systems, known as the disk arm scheduling problem. Our main findings can be briefly summarized as follows:

1. We present a deterministic $O(\log{n})$-competitive algorithm for n-point evenly-spaced line metrics. This result improves on a randomized $O(\log^2{n})$-competitive algorithm due to Khandekar and Pandit (STACS '06). It also refutes their conjecture, stating that a deterministic strategy is unlikely to obtain a non-trivial competitive ratio.
2. We devise a deterministic $O(\log{N}\log\log{N})$-competitive algorithm for continuous line metrics, where N denotes the length of the input sequence. In this context, we introduce a novel discretization technique, which is of independent interest, as it may be applicable in other settings as well.
3. We establish the first non-trivial lower bound for the evenly-spaced case, by proving that the competitive ratio of any deterministic algorithm is at least 2.154. This result settles, to some extent, an open question due to Khandekar and Pandit (STACS '06), who posed the task of attaining lower bounds on the achievable competitive ratio as a foundational objective for future research.

Remark: For sake of social welfare, I intend to avoid delving into technicalities at all cost. Relatively involved arguments will be "established" by employing drawings and intuition, while some inaccuracies will be introduced without any hesitation. For this reason, my talk should be accessible to just about anyone.

Joint work with Iftah Gamzu (TAU).

We propose the use of tree automata as abstractions in the verification of branching time properties, and show several benefits. In this setting, soundness and completeness are trivial. It unifies the abundance of frameworks in the literature, and clarifies the role of concepts therein in terms of the well-studied field of automata theory. Moreover, using automata as models simpli fies and generalizes results on maximal model theorems.

Given a positive integer $k$, a sequence $A=(a_n)_{n=0}^{\infty}$ over a finite alphabet set $\Omega$ is said to be $k$-automatic if the $n$th term of this sequence is generated by a finite state machine with $n$ in base-$k$ as an input. Those sequences occur in many different areas (such as number theory, combinatorics, computer graphics, ergodic theory, physics and even music). We begin with some background on the theory of automatic sequences. Then we study the subword complexity of those sequences and of some more general sequences which are defined in terms of context-free languages. In particular we consider a problem of Allouche and Shallit [1] on $k$-context-free sequences.

J.-P. Allouche and J. O. Shallit, Automatic Sequences. Theory, Applications, Generalizations. Cambridge University Press, Cambridge, 2003.