Abstract
We study various operations for partitioning, projecting and merging streams of data. These operations are motivated by their use in dataflow programming and the stream processing languages. We use the framework of stream calculus and stream circuits for defining and proving properties of such operations using behavioural differential equations and coinduction proof principles. We study the invariance of certain well patterned classes of streams, namely rational and algebraic streams, under splitting and merging. Finally we show that stream circuits extended with gates for dyadic split and merge are expressive enough to realise some non-rational algebraic streams, thereby going beyond ordinary stream circuits.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Arbab, F.: Reo: a channel-based coordination model for component composition. Mathematical Structures in Computer Science 14, 329–366 (2004)
Allouche, J.-P., Shallit, J.: Automatic sequences: theory, applications, generalizations. Cambridge University Press, Cambridge (2003)
Berstel, J., Reutenauer, C.: Rational series and their languages. EATCS Monographs on Theoretical Computer Science, vol. 12. Springer, Heidelberg (1988)
Broy, M., Ştefănescu, G.: The algebra of stream processing functions. Theoret. Comput. Sci. 258(1-2), 99–129 (2001)
Christol, G.: Ensembles presque periodiques k-reconnaissables. Theoret. Comput. Sci. 9(1), 141–145 (1979)
Cobham, A.: On the base-dependence of sets of numbers recognizable by finite automata. Math. Systems Theory 3, 186–192 (1969)
Pytheas Fogg, N.: Substitutions in dynamics, arithmetics and combinatorics. In: Berthé, V., Ferenczi, S., Mauduit, C., Siegel, A. (eds.). Lecture Notes in Math., vol. 1794. Springer, Berlin (2002)
Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete mathematics, 2nd edn. Addison-Wesley, Reading (1994)
Hungerford, T.W.: Algebra. Graduate Texts in Mathematics, vol. 73, Springer, New York (1980); Reprint of the 1974 original
Kahn, G.: The semantics of a simple language for parallel programming. In: Information Processing 74: Proceedings of IFIP Congress 74, Stockholm, August 1974, vol. 74, pp. 471–475. North Holland Publishing Co., Amsterdam (1974)
Kim, J.: Coinductive properties of causal maps. In: Meseguer, J., Roşu, G. (eds.) AMAST 2008. LNCS, vol. 5140, pp. 253–267. Springer, Heidelberg (2008)
Lucanu, D., Roşu, G.: CIRC: A circular coinductive prover. In: Mossakowski, T., Montanari, U., Haveraaen, M. (eds.) CALCO 2007. LNCS, vol. 4624, pp. 372–378. Springer, Heidelberg (2007)
Mak, R.H.: Design and Performance Analysis of Data-independent Stream Processing Systems. PhD thesis, Technische Universiteit Eindhoven (2008)
Rutten, J.J.M.M.: A coinductive calculus of streams. Mathematical Structures in Computer Science 15, 93–147 (2005)
Rutten, J.J.M.M.: A tutorial on coinductive stream calculus and signal flow graphs. Theoretical Computer Science 343(3), 443–481 (2005)
Rutten, J.J.M.M.: Algebraic specification and coalgebraic synthesis of Mealy automata. In: Proceedings of FACS 2005. ENTCS, vol. 160, pp. 305–319. Elsevier Science Publishers, Amsterdam (2006)
Rutten, J.J.M.M.: Rational streams coalgebraically. Logic. Methods in Comput. Sci. 4(3:9), 1–22 (2008)
Uustalu, T., Vene, V.: Comonadic notions of computation. In: Adámek, J., Kupke, C. (eds.) Proc. of CMCS 2008. ENTCS, vol. 203(5), pp. 263–284. Elsevier, Amsterdam (June 2008)
Wilf, H.S.: Generatingfunctionology. Academic Press, London (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Niqui, M., Rutten, J. (2010). Sampling, Splitting and Merging in Coinductive Stream Calculus. In: Bolduc, C., Desharnais, J., Ktari, B. (eds) Mathematics of Program Construction. MPC 2010. Lecture Notes in Computer Science, vol 6120. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13321-3_18
Download citation
DOI: https://doi.org/10.1007/978-3-642-13321-3_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13320-6
Online ISBN: 978-3-642-13321-3
eBook Packages: Computer ScienceComputer Science (R0)