Abstract: 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 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 the algorithm in this paper one has to proceed in a data-aware fashion.
Recommendations
Cited in
(11)- Highlights in infinitary rewriting and lambda calculus
- Applications and extensions of context-sensitive rewriting
- A tool proving well-definedness of streams using termination tools
- Well-Definedness of Streams by Termination
- The \Pi^0_2 -Completeness of Most of the Properties of Rewriting Systems You Care About (and Productivity)
- scientific article; zbMATH DE number 7376040 (Why is no real title available?)
- scientific article; zbMATH DE number 7168147 (Why is no real title available?)
- Behavioral rewrite systems and behavioral productivity
- Productivity of Stream Definitions
- Lazy productivity via termination
- Productivity of stream definitions
This page was built for publication: Data-Oblivious Stream Productivity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5505544)
