2007
Journal article
Open Access
Infinite unfair shuffles and associativity
Maurice H. Ter Beek, Jetty Kleijn
Limit behaviour Computer Science(all) Shuffle Infinite words Shuffles General Computer Science Fairness Theoretical Computer Science Shuffling G.2.1 Combinatorics. Permutations and combinations F.4.3 Formal Languages. Operations on languages Associativity Combinatorics
We consider a general shuffling operation for finite and infinite words which is not necessarily fair. This means that it may be the case that in a shuffle of two words, from some point onwards, one of these words prevails ad infinitum even though the other word still has letters to contribute. Prefixes and limits of shuffles are investigated, leading to a characterization of general shuffles in terms of shuffles of finite words, a result which does not hold for fair shuffles. Associativity of shuffling is an immediate corollary.
Source: Theoretical computer science 380 (2007): 401–410. doi:10.1016/j.tcs.2007.03.030
Publisher: Elsevier, Lausanne ;, Paesi Bassi
[1] K. Abrahamson, Decidability and Expresiveness of Logics of Processes, Ph.D. Thesis, University of Washington, Seattle, 1980.
[2] A. Bailly, M. Clerbout, I. Simplot-Ryl, Component composition preserving behavioural contracts based on communication traces, in: Proceedings CIAA'05, in: LNCS, vol. 3845, Springer-Verlag, Berlin, 2006, pp. 55-66.
[3] M.H. ter Beek, Team Automata - A Formal Approach to the Modeling of Collaboration Between System Components, Ph.D. Thesis, Leiden Institute of Advanced Computer Science, Leiden University, 2003.
[4] M.H. ter Beek, C.A. Ellis, J. Kleijn, G. Rozenberg, Synchronizations in team automata for groupware systems, Computer Supported Cooperative Work-The Journal of Collaborative Computing 12 (1) (2003) 21-69.
[5] M.H. ter Beek, J. Kleijn, Team automata satisfying compositionality, in: Proceedings FM'03, in: LNCS, vol. 2805, Springer-Verlag, Berlin, 2003, pp. 381-400.
[6] M.H. ter Beek, C. Mart´ın-Vide, V. Mitrana, Synchronized shuffles, Theoretical Computer Science 341 (1-3) (2005) 263-275.
[7] J.A. Bergstra, A. Ponse, S.A. Smolka (Eds.), Handbook of Process Algebra, Elsevier Science Publishers, Amsterdam, 2001.
[8] S.L. Bloom, Z. E´sik, Free shuffle algebras in language varieties, Theoretical Computer Science 163 (1996) 55-98.
[9] L. Boasson, M. Nivat, Adherences of languages, Journal of Computer and System Sciences 20 (3) (1980) 285-309.
[10] R. De Simone, Langages infinitaires et produit de mixage, Theoretical Computer Science 31 (1984) 83-100.
[11] E.A. Emerson, Alternative semantics for temporal logics, Theoretical Computer Science 26 (1-2) (1983) 121-130. Cf. also Technical Report TR-182, Department of Computer Sciences, University of Texas, Austin, 1981.
[12] S. Ginsburg, Algebraic and Automata-Theoretic Properties of Formal Languages. Fundamental Studies in Computer Science, vol. 2, NorthHolland Publishing Company, Amsterdam, 1975.
[13] S. Ginsburg, E.H. Spanier, Mappings of languages by two-tape devices, Journal of the ACM 12 (3) (1965) 423-434.
[14] J.L. Gischer, Shuffle languages, petri nets, and context sensitive grammars, Communications of the ACM 24 (1981) 597-605.
[15] M. Jantzen, The power of synchronizing operations on strings, Theoretical Computer Science 14 (1981) 127-154.
[16] T. Kimura, An algebraic system for process structuring and interprocess communication, in: Proceedings STOC'76, ACM Press, New York, 1976, pp. 92-100.
[17] M. Latteux, Y. Roos, Synchronized shuffle and regular languages, in: Jewels are Forever, Springer-Verlag, Berlin, 1999, pp. 35-44.
[18] M. Lothaire, Combinatorics on Words. Encyclopedia of Mathematics and its Applications, vol. 17, Cambridge University Press, Cambridge, 1983.
[19] A. Mateescu, G.D. Mateescu, Fair and associative infinite trajectories, in: Jewels are Forever, Springer-Verlag, Berlin, 1999, pp. 327-338.
[20] A. Mateescu, G. Rozenberg, A. Salomaa, Shuffle on trajectories: Syntactic constraints, Theoretical Computer Science 197 (1-2) (1998) 1-56.
[21] W.F. Ogden, W.E. Riddle, W.C. Rounds, Complexity of expressions allowing concurrency, in: Proceedings POPL'78, ACM Press, New York, 1978, pp. 185-194.
[22] D. Park, On the semantics of fair parallelism, in: Proceedings of the 1979 Copenhagen Winter School on Abstract Software Specifications, in: LNCS, vol. 86, Springer-Verlag, Berlin, 1980, pp. 504-526.
[23] R.R. Redziejowski, Associative Omega-products of traces, Fundamenta Informaticae 67 (1-3) (2005) 175-185.
[24] A.W. Roscoe, The Theory and Practice of Concurrency, Prentice Hall International Series in Computer Science, London, 1997.
[25] G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, Springer-Verlag, Berlin, 1997.
[26] J. Sakarovitch, I. Simon, Subwords, Chapter 6 in [18], 1983, pp. 105-142.
[27] A.C. Shaw, Software descriptions with flow expressions, IEEE Transactions on Software Engineering 4 (3) (1978) 242-254.
[28] J.L.A. van de Snepscheut, Trace Theory and VLSI Design. LNCS, vol. 200, Springer-Verlag, Berlin, 1985.
[29] L. Staiger, ω-languages, Chapter 6 in Volume 3 of [ 25], 1997, pp. 339-387.
[2] A. Bailly, M. Clerbout, I. Simplot-Ryl, Component composition preserving behavioural contracts based on communication traces, in: Proceedings CIAA'05, in: LNCS, vol. 3845, Springer-Verlag, Berlin, 2006, pp. 55-66.
[3] M.H. ter Beek, Team Automata - A Formal Approach to the Modeling of Collaboration Between System Components, Ph.D. Thesis, Leiden Institute of Advanced Computer Science, Leiden University, 2003.
[4] M.H. ter Beek, C.A. Ellis, J. Kleijn, G. Rozenberg, Synchronizations in team automata for groupware systems, Computer Supported Cooperative Work-The Journal of Collaborative Computing 12 (1) (2003) 21-69.
[5] M.H. ter Beek, J. Kleijn, Team automata satisfying compositionality, in: Proceedings FM'03, in: LNCS, vol. 2805, Springer-Verlag, Berlin, 2003, pp. 381-400.
[6] M.H. ter Beek, C. Mart´ın-Vide, V. Mitrana, Synchronized shuffles, Theoretical Computer Science 341 (1-3) (2005) 263-275.
[7] J.A. Bergstra, A. Ponse, S.A. Smolka (Eds.), Handbook of Process Algebra, Elsevier Science Publishers, Amsterdam, 2001.
[8] S.L. Bloom, Z. E´sik, Free shuffle algebras in language varieties, Theoretical Computer Science 163 (1996) 55-98.
[9] L. Boasson, M. Nivat, Adherences of languages, Journal of Computer and System Sciences 20 (3) (1980) 285-309.
[10] R. De Simone, Langages infinitaires et produit de mixage, Theoretical Computer Science 31 (1984) 83-100.
[11] E.A. Emerson, Alternative semantics for temporal logics, Theoretical Computer Science 26 (1-2) (1983) 121-130. Cf. also Technical Report TR-182, Department of Computer Sciences, University of Texas, Austin, 1981.
[12] S. Ginsburg, Algebraic and Automata-Theoretic Properties of Formal Languages. Fundamental Studies in Computer Science, vol. 2, NorthHolland Publishing Company, Amsterdam, 1975.
[13] S. Ginsburg, E.H. Spanier, Mappings of languages by two-tape devices, Journal of the ACM 12 (3) (1965) 423-434.
[14] J.L. Gischer, Shuffle languages, petri nets, and context sensitive grammars, Communications of the ACM 24 (1981) 597-605.
[15] M. Jantzen, The power of synchronizing operations on strings, Theoretical Computer Science 14 (1981) 127-154.
[16] T. Kimura, An algebraic system for process structuring and interprocess communication, in: Proceedings STOC'76, ACM Press, New York, 1976, pp. 92-100.
[17] M. Latteux, Y. Roos, Synchronized shuffle and regular languages, in: Jewels are Forever, Springer-Verlag, Berlin, 1999, pp. 35-44.
[18] M. Lothaire, Combinatorics on Words. Encyclopedia of Mathematics and its Applications, vol. 17, Cambridge University Press, Cambridge, 1983.
[19] A. Mateescu, G.D. Mateescu, Fair and associative infinite trajectories, in: Jewels are Forever, Springer-Verlag, Berlin, 1999, pp. 327-338.
[20] A. Mateescu, G. Rozenberg, A. Salomaa, Shuffle on trajectories: Syntactic constraints, Theoretical Computer Science 197 (1-2) (1998) 1-56.
[21] W.F. Ogden, W.E. Riddle, W.C. Rounds, Complexity of expressions allowing concurrency, in: Proceedings POPL'78, ACM Press, New York, 1978, pp. 185-194.
[22] D. Park, On the semantics of fair parallelism, in: Proceedings of the 1979 Copenhagen Winter School on Abstract Software Specifications, in: LNCS, vol. 86, Springer-Verlag, Berlin, 1980, pp. 504-526.
[23] R.R. Redziejowski, Associative Omega-products of traces, Fundamenta Informaticae 67 (1-3) (2005) 175-185.
[24] A.W. Roscoe, The Theory and Practice of Concurrency, Prentice Hall International Series in Computer Science, London, 1997.
[25] G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, Springer-Verlag, Berlin, 1997.
[26] J. Sakarovitch, I. Simon, Subwords, Chapter 6 in [18], 1983, pp. 105-142.
[27] A.C. Shaw, Software descriptions with flow expressions, IEEE Transactions on Software Engineering 4 (3) (1978) 242-254.
[28] J.L.A. van de Snepscheut, Trace Theory and VLSI Design. LNCS, vol. 200, Springer-Verlag, Berlin, 1985.
[29] L. Staiger, ω-languages, Chapter 6 in Volume 3 of [ 25], 1997, pp. 339-387.
Metrics
Back to previous page
BibTeX entry
@article{oai:it.cnr:prodotti:43992,
title = {Infinite unfair shuffles and associativity},
author = {Maurice H. Ter Beek and Jetty Kleijn},
publisher = {Elsevier, Lausanne ;, Paesi Bassi},
doi = {10.1016/j.tcs.2007.03.030},
journal = {Theoretical computer science},
volume = {380},
pages = {401–410},
year = {2007}
}CNR authorsLaboratories
0000-0002-2930-6367
