Synthesis of Mealy Machines Using Derivatives

详细信息    查看全文

• 作者：Helle Hvid Hansen ; David Costa ; Jan Rutten
• 关键词：Mealy machine ; synthesis ; derivatives ; streams ; coalgebra
• 刊名：Electronic Notes in Theoretical Computer Science
• 出版年：2006
• 出版时间：20 October 2006
• 年：2006
• 卷：164
• 期：1
• 页码：27-45
• 全文大小：392 K

文摘

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.