Data-Oblivious Stream Productivity

DOI10.1007/978-3-540-89439-1_6MaRDI QIDQ5505544zbMATH OpenOpenAlexFDO

Authors Jörg Endrullis, Clemens Grabmayer, Dimitri Hendriks

Publication date 27 January 2009

Published in Logic for Programming, Artificial Intelligence, and Reasoning (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0806.2680

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Specification and verification (program logics, model checking, etc.) (68Q60)

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

• PROVING PRODUCTIVITY IN INFINITE DATA STRUCTURES
• Productivity of Stream Definitions
• Productivity of stream definitions
• Data-oblivious data structures
• Proving equality of streams automatically

Cited in

(11)

• Lazy productivity via termination
• Productivity of Stream Definitions
• Productivity of stream definitions
• 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?)
• Applications and extensions of context-sensitive rewriting
• Behavioral rewrite systems and behavioral productivity
• scientific article; zbMATH DE number 7168147 (Why is no real title available?)
• Highlights in infinitary rewriting and lambda calculus
• A tool proving well-definedness of streams using termination tools
• Well-Definedness of Streams by Termination

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)