Let's Make a Difference! (2009)
Endrullis, Joerg, Hendriks, Dimitri, Klop, Jan Willem
We study the behaviour of iterations of the difference operator delta on streams over {0,1}. In particular, we show that a stream sigma is eventually periodic if and only if the sequence of...
Unique Normal Forms in Infinitary Weakly Orthogonal Term Rewriting (2009)
Endrullis, Joerg, Grabmayer, Clemens, Hendriks, Dimitri, Klop, Jan Willem
The theory of finite and infinitary term rewriting is extensively developed for orthogonal rewrite systems, but to a lesser degree for weakly orthogonal rewrite systems. In this note we present some...
Complexity of Fractran and Productivity (2009)
Endrullis, Joerg, Grabmayer, Clemens, Hendriks, Dimitri
In functional programming languages the use of infinite structures is common practice. For total correctness of programs dealing with infinite structures one must guarantee that every finite part of...
Degrees of Undecidability in Rewriting (2009)
Endrullis, Joerg, Geuvers, Herman, Zantema, Hans
Undecidability of various properties of first order term rewriting systems is well-known. An undecidable property can be classified by the complexity of the formula defining it. This gives rise to a...
Data-Oblivious Stream Productivity (2008)
Endrullis, Joerg, Grabmayer, Clemens, Hendriks, Dimitri
We are concerned with demonstrating productivity of specifications of infinite streams of data, based on orthogonal rewrite rules. In general, this property is undecidable, but for restricted formats...