Synthesis of Mealy Machines Using Derivatives

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

doi:10.1016/j.entcs.2006.06.003

Synthesis of Mealy Machines Using Derivatives

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

Research output: Contribution to Journal › Article › Academic › peer-review

Abstract

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 language	English
Pages (from-to)	27-45
Journal	Electronic Notes in Theoretical Computer Science
Volume	164(1)
DOIs	https://doi.org/10.1016/j.entcs.2006.06.003
Publication status	Published - 2006

Bibliographical note

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

Access to Document

10.1016/j.entcs.2006.06.003

Persistent URL (handle)

Persistent link

Cite this

@article{f16a87aa621c459397a397e7992a52c1,

title = "Synthesis of Mealy Machines Using Derivatives",

abstract = "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. {\textcopyright} 2006 Elsevier B.V. All rights reserved.",

author = "H.H. Hansen and {de Oliveira-Costa}, D. and J.J.M.M. Rutten",

note = "HanCosRut:Mealy-CMCS06 Proceedings title: Proceedings of the 8th Workshop on Coalgebraic Methods in Computer Science (CMCS 2006) Publisher: Elsevier Editors: N. Ghani, J. Power",

year = "2006",

doi = "10.1016/j.entcs.2006.06.003",

language = "English",

volume = "164(1)",

pages = "27--45",

journal = "Electronic Notes in Theoretical Computer Science",

issn = "1571-0661",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Synthesis of Mealy Machines Using Derivatives

AU - Hansen, H.H.

AU - de Oliveira-Costa, D.

AU - Rutten, J.J.M.M.

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

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

U2 - 10.1016/j.entcs.2006.06.003

DO - 10.1016/j.entcs.2006.06.003

M3 - Article

SN - 1571-0661

VL - 164(1)

SP - 27

EP - 45

JO - Electronic Notes in Theoretical Computer Science

JF - Electronic Notes in Theoretical Computer Science

ER -

Synthesis of Mealy Machines Using Derivatives

Abstract

Bibliographical note

Access to Document

Persistent URL (handle)

Fingerprint

Cite this