2011

  1. Lazy Productivity via Termination
    Jörg Endrullis, and Dimitri Hendriks
    Theoretical Computer Science , 412 (28) , pp. 3203–3225 (2011)
    paper

    Bibtex

    @article{productivity:termination:2011,
  author = {Endrullis, J\"{o}rg and Hendriks, Dimitri},
  title = {{Lazy Productivity via Termination}},
  journal = {Theoretical Computer Science},
  volume = {412},
  number = {28},
  pages = {3203--3225},
  year = {2011},
  doi = {10.1016/j.tcs.2011.03.024},
  keywords = {rewriting, infinitary rewriting, productivity, termination},
  type = {journal}
}

    Digital Object Identifier

    10.1016/j.tcs.2011.03.024

2010

  1. Productivity of Stream Definitions
    Jörg Endrullis, Clemens Grabmayer, Dimitri Hendriks, Ariya Isihara, and Jan Willem Klop
    Theoretical Computer Science , 411 (4-5) , pp. 765–782 (2010)
    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.

    This paper is an extended version of Productivity of Stream Definitions (2007) (FCT 2007).

    See research for an overview of my research on productivity.

    Bibtex

    @article{productivity:streams:2010,
  author = {Endrullis, J\"{o}rg and Grabmayer, Clemens and Hendriks, Dimitri and Isihara, Ariya and Klop, Jan Willem},
  title = {{Productivity of Stream Definitions}},
  journal = {Theoretical Computer Science},
  volume = {411},
  number = {4-5},
  pages = {765--782},
  year = {2010},
  doi = {10.1016/j.tcs.2009.10.014},
  keywords = {rewriting, infinitary rewriting, productivity},
  type = {journal}
}

    Digital Object Identifier

    10.1016/j.tcs.2009.10.014

2009

  1. Complexity of Fractran and Productivity
    Jörg Endrullis, Clemens Grabmayer, and Dimitri Hendriks
    In: Proc. Conf. on Automated Deduction (CADE 2009), pp. 371–387, Springer (2009)
    paper

    Bibtex

    @inproceedings{complexity:productivity:2009,
  author = {Endrullis, J\"{o}rg and Grabmayer, Clemens and Hendriks, Dimitri},
  title = {{Complexity of Fractran and Productivity}},
  booktitle = {Proc.\ Conf.\ on Automated Deduction (CADE~2009)},
  volume = {5663},
  pages = {371--387},
  publisher = {Springer},
  series = {LNCS},
  year = {2009},
  doi = {10.1007/978-3-642-02959-2\_28},
  keywords = {rewriting, undecidability, productivity},
  type = {conference}
}

    Digital Object Identifier

    10.1007/978-3-642-02959-2_28

2008

  1. Data-Oblivious Stream Productivity
    Jörg Endrullis, Clemens Grabmayer, and Dimitri Hendriks
    In: Proc. Conf. on Logic for Programming Artificial Intelligence and Reasoning (LPAR 2008), pp. 79–96, Springer (2008)
    paper

    Summary

    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 computable sufficient conditions can be obtained. The usual analysis, also adopted here, disregards the identity of data, thus leading to approaches that we call data-oblivious. We present a method that is provably optimal among all such data-oblivious approaches. This means that in order to improve on our algorithm one has to proceed in a data-aware fashion.

    See research for an overview of my research on productivity.

    Bibtex

    @inproceedings{productivity:data:oblivious:2008,
  author = {Endrullis, J\"{o}rg and Grabmayer, Clemens and Hendriks, Dimitri},
  title = {{Data-Oblivious Stream Productivity}},
  booktitle = {Proc.\ Conf.\ on Logic for Programming Artificial Intelligence and Reasoning (LPAR~2008)},
  number = {5330},
  pages = {79--96},
  publisher = {Springer},
  series = {LNCS},
  year = {2008},
  doi = {10.1007/978-3-540-89439-1\_6},
  keywords = {rewriting, infinitary rewriting, productivity},
  type = {conference}
}

    Digital Object Identifier

    10.1007/978-3-540-89439-1_6

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