Extensions of rooted trees and their applications

Informally, an almost-tree is a rooted graph which has the form of a tree in which some leaves are bent back to earlier nodes of the branch on which they sit. The paper provides a construction for unfurling any finite rooted graph to obtain a strong homomorphic image with desirable properties. As an application, it is shown that for each flow-diagram G there can be constructed an unfurling G¹ which is an almost-tree with semantic properties equivalent to those of G in a very strong sense.