`quasi'-periodic functions on N

Discussion in 'Math Research' started by Clemens Grabmayer, Jun 6, 2007.

  1. In connection with work concerning the problem of deciding
    productivity for (co-)recursive stream definitions
    ( cf. http://fspc282.few.vu.nl/productivity/ in the framework
    of project "Infinity": http://fspc282.few.vu.nl/infinity/ )
    we are interested in non-decreasing, and in particular,
    "quasi-periodic" functions on the natural numbers (see definition below)
    and have devised algorithms for computing their composition,
    fixed points, as well as pointwise minima and maxima (on "eventually
    periodic representations").

    Also, we constructed an algorithm for computing the pointwise minimum
    and maximum of all non-decrasing functions on the naturals that are
    described by the edge-label sequences of infinite paths in finite,
    directed graphs with natural number labeled edges (again see below for
    more details).

    Because in particular the last mentioned problem appears quite `natural'
    to us, we wonder whether it has been studied, and possibly solved,
    before. At the moment we are not aware of work in a similar direction,
    but would like to learn about related work of others.

    The problem described in a little more formal detail

    By N we denote the natural numbers including zero.

    There is an obvious bijective correspondence between non-decreasing
    functions f: N -> N and infinite sequences over N: every such function f
    is mapped to the sequence
    [f(0), f(1) - f(0), f(2) - f(1), ..., f(i+1) - f(i),...] ;
    conversely, every infinite sequence [a_0, a_1, a_2, ... ] in N
    is mapped to the function on N with values a_0, a_0 + a_1,
    a_0 + a_1 + a_2,... on the values 0,1,2, ... , respectively.

    We call a non-decreasing function f on N "quasi-periodic" if it
    corresponds to an eventually periodic infinite sequence on N.
    Furthermore, we call an expression like [7,8,13,<7,12>] an eventual
    periodic representation of the infinite sequence [7,8,13,7,12,7,12,...].

    By a "rooted, directed graph with natural number labeled edges" we mean
    a triple G = (V,E,r) consisting of a set V of vertices, a vertex r in V
    called the "root", and a set E of natural number labeled edges, a subset
    of V x N x V. Such a graph is finite if both of the sets V and E are
    finite. For an edge e = (v,n,w) we call v the "source", w the "target",
    and n the "label" of e.

    We established the following lemma.

    LEMMA. Let G = (V,E,r) be a finite, rooted, directed graph with natural
    number labeled edges. Suppose that every vertex in G is the source of
    at least one edge.
    Let pmin, pmax: N -> N be defined as the pointwise minimum, and resp.
    the pointwise maximum, of the set of non-decreasing functions on N that
    correspond to edge-label sequences of infinite paths in G from the
    Then pmin and pmax are quasi-periodic functions. Also, eventually
    periodic representations of pmin and pmax can be computed
    algorithmically from the input of G.

    (*) Note that pmin and pmax themselves do not have to correspond to
    edge-label sequences of infinite paths in G.

    In the proof, which is not difficult, we use Higman's lemma to guarantee
    the existence of loops of vertical `strips' of respectively lowest
    points corresponding to vertex-visits in the graphs of all functions
    on N that are generated by edge-label sequences of infinite paths in G.


    We would be very thankful for any indications or references to known
    work dealing with this problem or similar ones.

    Many thanks for any hints on this!

    Joerg Endrullis
    Clemens Grabmayer
    Clemens Grabmayer, Jun 6, 2007
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.