# Publications on Productivity

## 2011

- Lazy Productivity via TerminationJörg Endrullis, and Dimitri HendriksTheoretical 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

- Productivity of Stream DefinitionsJörg Endrullis, Clemens Grabmayer, Dimitri Hendriks, Ariya Isihara, and Jan Willem KlopTheoretical 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

- Complexity of Fractran and ProductivityJörg Endrullis, Clemens Grabmayer, and Dimitri HendriksIn: 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

- Data-Oblivious Stream ProductivityJörg Endrullis, Clemens Grabmayer, and Dimitri HendriksIn: 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

- Productivity of Stream DefinitionsJörg Endrullis, Clemens Grabmayer, Dimitri Hendriks, Ariya Isihara, and Jan Willem KlopIn: 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