Yield grammar analysis and product optimization in a domain-specific language for dynamic programming

Sauthoff G, Giegerich R (2014)
Science of Computer Programming 87: 2-22.

Journal Article | Published | English

No fulltext has been uploaded

Abstract
Dynamic programming algorithms are traditionally expressed by a set of matrix recurrences-a low level of abstraction, which renders the design of novel dynamic programming algorithms difficult and makes debugging cumbersome. Bellman's GAP is a declarative, domain-specific language, which supports dynamic programming over sequence data. It implements the algebraic style of dynamic programming and allows one to specify algorithms by combining so-called yield grammars with evaluation algebras. Products on algebras allow to create novel types of analyses from already given ones, without modifying tested components. Bellman's GAP extends the previous concepts of algebraic dynamic programming in several respects, such as an "interleaved" product operation and the analysis of multi-track input. Extensive analysis of the yield grammar and the evaluation algebras is required for generating efficient imperative code from the algebraic specification. This article gives an overview of the analyses required and presents several of them in detail. Measurements with "real-world" applications demonstrate the quality of the code produced. (C) 2013 Elsevier B.V. All rights reserved.
Publishing Year
ISSN
PUB-ID

Cite this

Sauthoff G, Giegerich R. Yield grammar analysis and product optimization in a domain-specific language for dynamic programming. Science of Computer Programming. 2014;87:2-22.
Sauthoff, G., & Giegerich, R. (2014). Yield grammar analysis and product optimization in a domain-specific language for dynamic programming. Science of Computer Programming, 87, 2-22.
Sauthoff, G., and Giegerich, R. (2014). Yield grammar analysis and product optimization in a domain-specific language for dynamic programming. Science of Computer Programming 87, 2-22.
Sauthoff, G., & Giegerich, R., 2014. Yield grammar analysis and product optimization in a domain-specific language for dynamic programming. Science of Computer Programming, 87, p 2-22.
G. Sauthoff and R. Giegerich, “Yield grammar analysis and product optimization in a domain-specific language for dynamic programming”, Science of Computer Programming, vol. 87, 2014, pp. 2-22.
Sauthoff, G., Giegerich, R.: Yield grammar analysis and product optimization in a domain-specific language for dynamic programming. Science of Computer Programming. 87, 2-22 (2014).
Sauthoff, Georg, and Giegerich, Robert. “Yield grammar analysis and product optimization in a domain-specific language for dynamic programming”. Science of Computer Programming 87 (2014): 2-22.
This data publication is cited in the following publications:
This publication cites the following data publications:

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Search this title in

Google Scholar