Synthesis of Mealy machines using derivatives

H.H. Hansen, D.F. de Oliveira Costa, J.J.M.M. Rutten

    Research output: Book/ReportReportAcademic


    In Rutten [16] the theoretical basis was given for the synthesis of binary Mealy machines from specifications in 2-adic arithmetic. This construction is based on the symbolic computation of the coalgebraic notion of stream function derivative, a generalisation of the Brzozowski derivative of regular expressions. In this paper we complete the construction of Mealy machines from specifications in both 2-adic and modulo-2 arithmetic by describing how we decide equivalence of expressions via reduction to normal forms; we present a Haskell implementation of this Mealy synthesis algorithm; and a theoretical result which characterises the (number of) states in Mealy machines constructed from rational 2-adic specifications.
    Original languageEnglish
    Place of PublicationAmsterdam
    PublisherCentrum voor Wiskunde en Informatica
    Number of pages24
    Publication statusPublished - 2006

    Publication series

    NameCWI report. SEN-R : software engineering
    ISSN (Print)1386-369X


    Dive into the research topics of 'Synthesis of Mealy machines using derivatives'. Together they form a unique fingerprint.

    Cite this