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.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Abstract / Bemerkung
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.
Stichworte
RNA structure prediction; Compiler optimization; grammar; Regular tree; Algebraic dynamic programming; Domain-specific language
Erscheinungsjahr
2014
Zeitschriftentitel
Science of Computer Programming
Band
87
Seite(n)
2-22
ISSN
0167-6423
Page URI
https://pub.uni-bielefeld.de/record/2681698

Zitieren

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. doi:10.1016/j.scico.2013.09.011
Sauthoff, Georg, and Giegerich, Robert. 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.
Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®
Suchen in

Google Scholar