TY - JOUR

T1 - Productivity of Stream Definitions

AU - Endrullis, J.

AU - Grabmayer, C.A.

AU - Hendriks, R.D.A.

AU - Ishihara, A.

AU - Klop, J.W.

PY - 2010

Y1 - 2010

N2 - 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. © 2009 Elsevier B.V. All rights reserved.

AB - 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. © 2009 Elsevier B.V. All rights reserved.

U2 - 10.1016/j.tcs.2009.10.014

DO - 10.1016/j.tcs.2009.10.014

M3 - Article

SN - 0304-3975

VL - 411

SP - 765

EP - 782

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 4-5

ER -