Symbolic Synthesis of Mealy Machines from Arithmetic Bitstream Functions

Published in Volume XX, 2010, pages 97-130

Authors: H.H. Hansen and J. Rutten

Abstract

In this paper, we describe a symbolic synthesis method which given an algebraic expression that specifies a bitstream function f, constructs a (minimal) Mealy machine that realises f. The synthesis algorithm can be seen as an analogue of Brzozowski’s construction of a finite deterministic automaton from a regular expression. It is based on a coinductive characterisation of the operators of 2-adic arithmetic in terms of stream differential equations.

Full Text (PDF)

References

[1] V. Antimirov. Partial derivatives of regular expressions, and finite automaton constructions. Theoretical Computer Science, 155(2):291- 319, 1996.

[2] F. Bartels. On Generalised Coinduction and Probabilistic Specification Formats. PhD thesis, Vrije Universiteit Amsterdam, 2004.

[3] J.A. Brzozowski. Derivatives of regular expressions. Journal of the ACM, 11(4):481-494, 1964.

[4] S. Eilenberg. Automata, Languages and Machines (Vol. A). Academic Press, 1974.

[5] F.Q. Gouvˆea. p-adic Numbers: An Introduction. Springer, 1993.

[6] H.H. Hansen. Coalgebraic Modelling: applications in automata theory and modal logic. PhD thesis, Vrije Universiteit Amsterdam, 2009.

[7] H.H. Hansen and D. Costa. Diffcal. Tool webpage (source code, documentation, executable) currently available at: http://homepages.cwi.nl/~costa/projects/diffcal, 2005.

[8] H.H. Hansen, D. Costa, and J.J.M.M. Rutten. Synthesis of Mealy machines using derivatives. In Proceedings of CMCS 2006, volume 164(1) of Electronic Notes in Theoretical Computer Science, pages 27- 45. Elsevier Science Publishers, 2006.

[9] H.H. Hansen and B. Klin. Pointwise extensions of GSOS-defined operations. To appear in Mathematical Structures in Computer Science.

[10] E.C.R. Hehner and R.N. Horspool. A new representation of the rational numbers for fast easy arithmetic. SIAM Journal on Computing, 8:124- 134, 1979.

[11] B. Jacobs. A bialgebraic review of deterministic automata, regular expressions and languages. In Algebra, Meaning and Computation: Essays dedicated to Joseph A. Goguen on the Occasion of his 65th Birthday, volume 4060 of Lecture Notes in Computer Science, pages 375-404. Springer, 2006.

[12] S. Lombardy and J. Sakarovitch. Derivatives of rational expressions with multiplicity. Theoretical Computer Science, 332:141-177, 2005.

[13] G.N. Raney. Sequential functions. Journal of the ACM, 5(2):177-180, April 1958.

[14] J.J.M.M. Rutten. Automata, power series, and coinduction: taking input derivatives seriously (extended abstract). In J. Wiedermann, P. van Emde Boas, and M. Nielsen, editors, Proceedings of the 26th International Colloquium on Automata, Languages and Programming (ICALP 1999), volume 1644 of Lecture Notes in Computer Science, pages 645-654, 1999.

[15] J.J.M.M. Rutten. Universal coalgebra: a theory of systems. Theoretical Computer Science, 249:3-80, 2000.

[16] J.J.M.M. Rutten. Behavioural differential equations: a coinductive calculus of streams, automata and power series. Theoretical Computer Science, 308(1):1-53, 2003.

[17] J.J.M.M. Rutten. Algebra, bitstreams, and circuits. In Proceedings of AAA68 Workshop on General Algebra, volume 16 of Contributions to General Algebra, pages 231-250. Verlag Johannes Heyn, Klagenfurt, 2005.

[18] J.J.M.M. Rutten. Algebraic specification and coalgebraic synthesis of Mealy machines. In Proceedings of FACS 2005, volume 160 of Electronic Notes in Theoretical Computer Science, pages 305-319, 2006.

[19] A.M. Silva, M.M. Bonsangue, and J.J.M.M. Rutten. Kleene coalgebras. Technical Report SEN-1001, Centrum Wiskunde & Informatica, 2010.

[20] D. Turi and G.D. Plotkin. Towards a mathemathical operational semantics. In Proceedings of LICS 1997, pages 280-291. IEEE Computer Society, 1997.

Bibtex

@article{sacscuza:hansen2010ssommfabf,
  title={Symbolic Synthesis of Mealy Machines from Arithmetic Bitstream Functions},
  author={H.H. Hansen and J. Rutten},
  journal={Scientific Annals of Computer Science},
  volume={20},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2010},
  pages={97--130},
  publisher={``A.I. Cuza'' University Press}
}