Synthesis of Mealy Machines Using Derivatives
The work
| Authors | Helle Hvid Hansen; David Costa; Jan Rutten |
|---|---|
| Editors | |
| Type | article |
| Year | 2006 |
| Citekey | hansen2006synthesis |
Where it appeared
| Published in | Electronic Notes in Theoretical Computer Science |
|---|---|
| Publisher | Elsevier |
| Volume | 164 |
| Issue | 1 |
| Pages | 27--45 |
Identifiers
| DOI | 10.1016/j.entcs.2006.06.003 |
|---|---|
| OpenAlex | W2507909447 |
Access
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.
Cite it as
@article{hansen2006synthesis,
title = {Synthesis of Mealy Machines Using Derivatives},
author = {Helle Hvid Hansen and David Costa and Jan Rutten},
year = {2006},
journal = {Electronic Notes in Theoretical Computer Science},
publisher = {Elsevier},
volume = {164},
number = {1},
pages = {27--45},
doi = {10.1016/j.entcs.2006.06.003},
}
This record lives at https://refs.drheap.org/hansen2006synthesis/ and will keep doing so.