On the fundamental limitations of transformational design

    Research output: Contribution to journalArticleAcademicpeer-review

    7 Citations (Scopus)

    Abstract

    The completeness of a collection of design transformations is an important aspect in transformational design. Completeness guarantees that any correct design can in principle be explored using the transformation system. In the field of transformational design the problem of incompleteness is not well understood and it is often believed that complete transformation systems can be constructed. In this article, we show, using a formal framework based on the theory of computation, that this is not the case if the transformation system is based on an expressive general-purpose design language such as VHDL. Only when restrictions are imposed on the design language and correctness relation, a transformation system can be made complete in theory, but this is expected to result in serious practical problems. It is shown that the incompleteness problem in transformational design is closely related to the syntactic variance problem in high-level synthesis and that this latter problem is not solvable in general either.
    Original languageEnglish
    Pages (from-to)533-552
    Number of pages20
    JournalACM Transactions on Design Automation of Electronic Systems
    Volume6
    Issue number4
    DOIs
    Publication statusPublished - 2001

      Fingerprint

    Cite this