Synthesis of Mealy Machines Using Derivatives

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

Research output: Contribution to JournalArticleAcademicpeer-review


In Rutten [Rutten, J., Algebraic specification and coalgebraic synthesis of Mealy machines, Technical Report SENR0514, Centrum voor Wiskunde en Informatica (CWI) (2005), to appear in Proceedings FACS 2005] 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. © 2006 Elsevier B.V. All rights reserved.
Original languageEnglish
Pages (from-to)27-45
JournalElectronic Notes in Theoretical Computer Science
Publication statusPublished - 2006

Bibliographical note

Proceedings title: Proceedings of the 8th Workshop on Coalgebraic Methods in Computer Science (CMCS 2006)
Publisher: Elsevier
Editors: N. Ghani, J. Power


Dive into the research topics of 'Synthesis of Mealy Machines Using Derivatives'. Together they form a unique fingerprint.

Cite this