2007

  1. Productivity of Stream Definitions
    Jörg Endrullis, Clemens Grabmayer, Dimitri Hendriks, Ariya Isihara, and Jan Willem Klop
    In: Proc. Symp. on Fundamentals of Computation Theory (FCT 2007), pp. 274–287, Springer (2007)
    paper

    Summary

    We give an algorithm for deciding productivity of a large and natural class of recursive stream definitions. A stream definition is called `productive' if it can be evaluated continually in such a way that a uniquely determined stream in constructor normal form is obtained as the limit. Whereas productivity is undecidable for stream definitions in general, we show that it can be decided for `pure' stream definitions. For every pure stream definition the process of its evaluation can be modelled by the dataflow of abstract stream elements, called `pebbles', in a finite `pebbleflow net(work)'. And the production of a pebbleflow net associated with a pure stream definition, that is, the amount of pebbles the net is able to produce at its output port, can be calculated by reducing nets to trivial nets.

    An extended journal version of this paper is available from Productivity of Stream Definitions (TCS 2010).

    See research for an overview of my research on productivity.

    Bibtex

    @inproceedings{productivity:streams:2007,
  author = {Endrullis, J\"{o}rg and Grabmayer, Clemens and Hendriks, Dimitri and Isihara, Ariya and Klop, Jan Willem},
  title = {{Productivity of Stream Definitions}},
  booktitle = {Proc.\ Symp.\ on Fundamentals of Computation Theory (FCT~2007)},
  number = {4639},
  pages = {274--287},
  publisher = {Springer},
  series = {LNCS},
  year = {2007},
  doi = {10.1007/978-3-540-74240-1\_24},
  keywords = {rewriting, infinitary rewriting, productivity},
  type = {conference}
}

    Digital Object Identifier

    10.1007/978-3-540-74240-1_24
  2. Root Stabilisation Using Dependency Pairs
    Jörg Endrullis, and Jeroen Ketema
    In: Proc. Workshop on Termination (WST 2007), pp. 17–21 (2007)
    paper

    Bibtex

    @inproceedings{termination:root:2007,
  author = {Endrullis, J\"{o}rg and Ketema, Jeroen},
  title = {{Root Stabilisation Using Dependency Pairs}},
  booktitle = {Proc.\ Workshop on Termination (WST~2007)},
  pages = {17--21},
  year = {2007},
  keywords = {rewriting, infinitary rewriting, termination},
  type = {workshop}
}

    Digital Object Identifier