Synthesis of Mealy Machines Using Derivatives
The work
| Title | Synthesis of Mealy Machines Using Derivatives |
|---|---|
| Authors | Helle Hvid Hansen; David Costa; Jan Rutten |
| 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.
Copy held
| Kind | PDF, 423.7 kB |
|---|---|
| Retrieved | 2026-08-12 |
| Held | local, for personal reference |
| Where it came from | https://doi.org/10.1016/j.entcs.2006.06.003 |
Where this came from
| How it got here | already cited · cited in bibtex |
|---|---|
| First seen | 2026-08-12 |
| Record | reviewed by a person |
| Approved | 2026-08-16 |
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},
volume = {164},
number = {1},
pages = {27--45},
publisher = {Elsevier},
doi = {10.1016/j.entcs.2006.06.003},
url = {https://www.sciencedirect.com/science/article/pii/S1571066106004683/pdf},
}
This record lives at https://refs.drheap.org/hansen2006synthesis/ and will keep doing so.