NASA NTRS · 20010106096
Synthesizing Dynamic Programming Algorithms from Linear Temporal Logic Formulae
Abstract
The problem of testing a linear temporal logic (LTL) formula on a finite execution trace of events, generated by an executing program, occurs naturally in runtime analysis of software. We present an algorithm which takes an LTL formula and generates an efficient dynamic programming algorithm. The generated algorithm tests whether the LTL formula is satisfied by a finite trace of events given as input. The generated algorithm runs in linear time, its constant depending on the size of the LTL formula. The memory needed is constant, also depending on the size of the formula.
Keep this discovery
Explore connections, maps & timelines
Rosu, Grigore, Havelund, Klaus. 2001-01-01. Synthesizing Dynamic Programming Algorithms from Linear Temporal Logic Formulae. https://engineeringpapers.com/record/nasa%3A20010106096/synthesizing-dynamic-programming-algorithms-from-linear-temporal-logic-formulae
Citations retain the original authors and DOI and include this site’s record URL. If this discovery service contributed to your research, you can also cite Engineering Papers by Indiciae: BibTeX · RIS.