Degrees of Streams

We introduce a novel approach to comparing the complexity of streams (one-sided infinite sequences or infinite words), where streams are compared on the basis of transducibility using finite state transducers (FST). For streams s,t we define s ≥ t if there exists an FST that transduces s to t; if also a back-transformation is possible, the streams are deemed equivalent. Thus, for example the well-known Thue-Morse sequence M is equivalent to the period-doubling sequence PD. This gives rise to a hierarchy of stream `degrees', somewhat analogous to the recursion-theoretic degrees of unsolvability. It is the structure and properties of this partial order of degrees that we are primarily interested in. Remarkably, in spite of its simplicity, the main idea of this approach seems to have remained unexplored.


Partial order of degrees.


In contrast to the recursion-theoretic hierarchy, which identifies all computable streams, the structure of the FST-hierarchy is fine-grained enough to distinguish computable streams by their intrinsic infinite pattern. By this we mean that a degree is invariant under the insertion or removal of finitely many elements, or a change of encoding.

The bottom degree of this hierarchy is formed by the set of ultimately periodic streams. Our main result is the existence of prime degrees, that is, degrees that have no other degree between themselves and the bottom degree. In particular, we show that the degree of the stream 1101001000100001... is prime. Apart from these initial results, many interesting properties remain unexplored.

★ Research Questions / Open Problems
  • How many prime degrees exist?
  • How do the degrees of some well-known streams compare? For example, are the Thue-Morse sequence M and the Sierpinski sequence S of the same degree?
  • In general: how to prove non-transducibility between morphic streams? This is challenging question, interesting both for combinatorics and formal language theory. Discriminating morphic words seems to require heavier machinery than arguments based on the pumping lemma.
  • Do the following structures exist in the hierarchy?

    The arrows s → t mean s > t. Using transitivity of > we leave some arrows implicit. Moreover, we assume that if s is a degree and s > t, then t is depicted as well. In particular there are no intermediate degrees between two displayed nodes connected by an arrow.

For further reading, we refer to:

Iterated Morphisms and Automatic Sequences

We investigate the computational power of periodically iterated morphisms, also known as DOP systems with periodic control, PDOL systems for short. These systems give rise to a class of one-sided infinite sequences, called PDOL words.

We construct a PDOL word with exponential subword complexity, thereby answering a question raised by Lepistö on the existence of such words. We solve another open problem concerning the decidability of the first-order theories of PDOL words; we show it is already undecidable whether a certain letter occurs in a PDOL word.


An excerpt of the PDOL word with exponential subword complexity.


★ Research Questions / Open Problems
  • Lepistö has shown in 1992 that the subword complexity of PDOL words can exceed any polynomial. He employs PDOL systems H = (w,h0,...,hn) that are locally uniform, that is, each of the morphisms h0,...,hn is uniform (all images of single letters have equal length). In contrast to the results of Lepistö, our results are crucially based on the use of PDOL systems that are not locally uniform. Thus a natural question is:

    Are there locally uniform PDOL systems generating words with exponential subword complexity?

For further reading, we refer to:

Automatic Sequences and Zip-Specifications

We consider infinite sequences of symbols, also known as streams, and the decidability question for equality of streams defined in a restricted format. (Some formats lead to undecidable equivalence problems.) This restricted format consists of prefixing a symbol at the head of a stream, of the stream function `zip', and recursion variables. Here `zip' interleaves the elements of two streams alternatingly. As a term rewriting rule, `zip' can be defined as follows:

zip(x:s,y:t) = x:y:zip(s,t)

The celebrated Thue--Morse sequence is obtained by the succinct `zip-specification'

M = 0 : X
X = 1 : zip(X,Y)
Y = 0 : zip(Y,X)

It turns out that the class of streams definable by zip-specifications is precisely the class of 2-automatic sequences. The generalization to k-automatic sequences is immediate using zipk interleaving k arguments:

zipk(x1:s1,...,xk:sk) = x1:...:xk::zipk(s1,...,sk)

Thus zip-specifications can be perceived as a term rewriting syntax for automatic sequences.

Our analysis, based on term rewriting and coalgebraic techniques, moreover leads to a coalgebraic characterization of automatic sequences. This characterization allows for playfully discovering whether a given stream is automatic. Let s be a stream, and assume we want to check whether s is 2-automatic. We construct a graph whose nodes are streams and whose edges are labelled with `even' and `odd'. Initially the graph consists only of the root node s. For every node t, we add outgoing edges `even' and `odd' to streams even(t) and odd(t), respectively, where even(t) is the subsequence of t consisting of the elements at even positions, and odd(t) is the subsequence of t consisting of elements at odd positions. If even(t) or odd(t) are not yet nodes of the graph, then we add these. Then the stream s is 2-automatic if and only if the construction stops and thus the graph is finite. Using term rewriting, `even' and `odd' can be defined in terms of each other as follows:

even(a : s) = a : odd(s)
odd(a : s) = even(s).

Of course this game can also be played using representatives of streams as the nodes instead of streams themselves. If streams are defined by term rewriting, then terms are a natural choice for these representatives. For example, for the zip-specification defining Thue-Morse above, we obtain the following observation graph:



If we replace in this graph `even` by 0 and `odd' by 1, we obtain a 2-DFAO that generates the Thue-Morse sequence M as automatic sequence.

As a natural extension of the class of automatic sequences,we also consider `zip-mix' specifications that use zips of different arities in one specification. For example:

Z = zip2(0:Z,Y)
Y = 1:zip3(Z,Y,0:Z)

The corresponding notion of automaton employs a state-dependent input-alphabet, with a number representation (n)_A = dm...d0 where the base of digit di is determined by the automaton A on input di-1...d0.

★ Research Questions / Open Problems
  • Are there streams definable by zip-mix specifications that are not morphic?
  • Is equivalence of zip-mix specifications still decidable?

For further reading, we refer to:

Clocked Böhm Trees

We are concerned with methods for proving the beta-inconvertibility of lambda terms. The well-known approach via Böhm trees fails if the lambda terms under consideration have the same Böhm trees. For instance all fixed point combinators have the Boehm tree λx.x(x(x(...))). We therefore employ `clocked Böhm Trees', with annotations that convey information of the tempo in which the tree is produced. For example



shows the clocked Böhm trees of Y0f and Y1f where

Y0 = λf.(λx.f(xx))(λx.f(xx))
Y1 = (λx.λf.f(xxf))(λx.λf.f(xxf))

is Curry's and is Turings' fixed point combinator, respectively. The annotations [n] in the clocked Böhm trees describe the number of head steps that were needed for evaluation to head normal form of this position during the formation of the Böhm tree. Böhm trees are thus enriched with an intrinsic clock behaviour, leading to a refined discrimination method for lambda-terms. Note that the clocked Böhm trees of Y0f and Y1f contain infinitely many different annotations. This suffices to conclude that Y0 and Y1 are not beta-convertible.

This refined method allows us to solve a problem of Selinger and Plotkin concerning the existance of a fixed point combinator Y such that

Y(λz.fzz) = Y(λx.Y(λy.fxy))

We show that no such fixed point combinator Y exists.

★ Research Questions / Open Problems
  • The method of clocked Böhm trees can be further refined to atomic clocks that record not only the number of head steps, but also the positions of the steps in the head reduction to head normal form. What about a generalization to other spine reduction strategies? That is, using a different strategy than head reduction to reduce to head normal form. Would this give rise to a stronger discrimination method?
  • The method of clocked Böhm trees is best applicable to simple terms (or terms with simple reducts), which during the reduction to Böhm trees normal form do not duplicate redexes. The notion of simple terms could be refined by focusing on an infinite path in the clocked Böhm trees. Then duplication of redexes may be allowed along other paths, thereby extending the class of terms to which the method is fruitfully applicable.
  • Is it possible to characterize fully cyclic terms using a coinductive version of simple type theory?
  • Can the notion of a clock itself be given a type-theoretic interpretation?
  • Can the clocks method be used to give a quantitative measure for optimization of functional programs?
  • Is it possible, using the clocks method, to extend Intrigila's result from 1997, and prove that there is no fixed point combinator Y and no n such that Y =β Yδ˜n?

For further reading, we refer to:

Termination

For further reading, we refer to:

Productivity

For further reading, we refer to:

Asynchronous Bounded Expected Delay Networks

The commonly used asynchronous bounded delay (ABD) network models assume a fixed bound on message delay. The ABD network model is practically not applicable to real life situations, except for systems on chips. In usual computer networks, the communication delay cannot be bounded; we have to settle with expected delays.

We propose a probabilistic network model, called asynchronous bounded expected delay (ABE) model. Instead of a strict bound, the ABE model requires only a bound on the expected message delay. Note that different links in the network might have different expected delays, and we typically do not want to determine the precise delay of every link. The bound on the expected message delays allows for an overapproximation of the expected delays of all links. While the conditions of ABD networks restrict the set of possible executions, in ABE networks all asynchronous executions are possible, but executions with extremely long delays are less probable.

At the example of an election algorithm, we show that the minimal assumptions of ABE networks are sufficient for the development of efficient algorithms. For anonymous, unidirectional ABE rings of known size N we devise a probabilistic leader election algorithm having average message and time complexity O(N).

★ Research Questions / Open Problems
  • There is a plethora of algorithms to be developed for the ABE network model.
    (Basically everything apart this initial study is open.)
For further reading, we refer to: