An exercise in transformational programming: Backtracking and Branch-and-Bound

M.M. Fokkinga

    Research output: Contribution to journalArticleAcademicpeer-review

    5 Citations (Scopus)
    106 Downloads (Pure)


    We present a formal derivation of program schemes that are usually called Backtracking programs and Branch-and-Bound programs. The derivation consists of a series of transformation steps, specifically algebraic manipulations, on the initial specification until the desired programs are obtained. The well-known notions of linear recursion and tail recursion are extended, for structures, to elementwise linear recursion and elementwise tail recursion; and a transformation between them is derived too.
    Original languageUndefined
    Article number10.1016/0167-6423(91)90022-P
    Pages (from-to)19-48
    Number of pages30
    JournalScience of computer programming
    Issue number1
    Publication statusPublished - Jul 1991


    • IR-66236
    • EWI-6292

    Cite this