Associativity of Infinite Synchronized Shuffles and Team Automata

• Autorzy: ter Beek M.H. , Kleijn J.
• Języki publikacji: EN

Abstrakty

EN

Motivated by different ways to obtain team automata from synchronizing component automata, we consider various definitions of synchronized shuffles of words. A shuffle of two words is an interleaving of their symbol occurrenceswhich preserves the original order of these occurrences within each of the two words. In a synchronized shuffle, however, also two occurrences of one symbol, each from a different word, may be identified as a single occurrence. In case at least one of the words involved is infinite, a (synchronized) shuffle can also be unfair in the sense that an infinite word may prevail fromsome point onwards even when the other word still has occurrences to contribute to the shuffle. We prove that for the synchronized shuffle operations under consideration, every (fair or unfair) synchronized shuffle can be obtained as a limit of synchronized shuffles of the finite prefixes of the words involved. In addition, it is shown that with the exception of one, all synchronized shuffle operations that we consider satisfy a natural notion of associativity, also in case of unfairness. Finally, using these results, some compositionality results for team automata are established.

Słowa kluczowe

EN

team automata; synchronized shuffling; infinite words; fairness; associativity; compositionality

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 91, nr 3-4
• Strony: 4437--461
• Opis fizyczny: Bibliogr. 41 poz., wykr.

Twórcy

autor

ter Beek M.H.

autor

Kleijn J.

• Istituto di Scienza e Tecnologie dell'Informazione "A. Faedo", CNR Via G. Moruzzi 1, 56124 Pisa, Italy,

Bibliografia

• [1] Abrahamson, K.: Decidability and Expresiveness of Logics of Processes, Ph.D. Thesis, University of Washington, Seattle, 1980.
• [2] Bailly, A., Clerbout, M., Simplot-Ryl, I.: Component Composition Preserving Behavioural Contracts Based on Communication Traces, Proceedings of the Tenth International Conference on Implementation and Application of Automata (CIAA'05), Sophia Antipolis, France (J. Farré, I. Litovsky, S. Schmitz, Eds.), Lecture Notes in Computer Science 3845, Springer-Verlag, Berlin, 2006, 55-66.
• [3] ter Beek, M. H. (webmaster): Team Automata webpage, http://fmt.isti.cnr.it/˜mtbeek/TA.html
• [4] ter Beek, M. H.: 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.
• [5] ter Beek, M. H., Ellis, C. A., Kleijn, J., Rozenberg, G.: Synchronizations in team automata for groupware systems, Computer Supported Cooperative Work-The Journal of Collaborative Computing, 12(1), 2003, 21-69.
• [6] ter Beek, M. H., Gadducci, F., Janssens, D.: A calculus for team automata, Proceedings of the Ninth Brazilian Symposium on Formal Methods (SBMF'06), Natal, Rio Grande do Norte, Brazil (A. Martins Moreira, L. Ribeiro, Eds.), Electronic Notes in Theoretical Computer Science 195, Elsevier Science Publishers, Amsterdam, 2007, 41-55.
• [7] ter Beek, M. H., Kleijn, J.: Team Automata Satisfying Compositionality, Proceedings of FME 2003: Formal Methods- The Twelfth International Symposium of Formal Methods Europe, Pisa, Italy (K. Araki, S. Gnesi, D. Mandrioli, Eds.), Lecture Notes in Computer Science 2805, Springer-Verlag, Berlin, 2003, 381-400.
• [8] ter Beek, M. H., Kleijn, J.: Infinite Unfair Shuffles and Associativity, Theoretical Computer Science, 380(3), 2007, 401-410.
• [9] ter Beek,M. H.,Mart´ın-Vide, C.,Mitrana, V.: Synchronized Shuffles, Theoretical Computer Science, 341(1-3), 2005, 263-275.
• [10] Bergstra, J. A., Ponse, A., Smolka, S. A. (Eds.): Handbook of Process Algebra, Elsevier Science Publishers, Amsterdam, 2001.
• [11] Bloom, S. L., ésik, Z.: Free Shuffle Algebras in Language Varieties, Theoretical Computer Science, 163(1-2), 1996, 55-98.
• [12] Boasson, L., Nivat, M.: Adherences of Languages, Journal of Computer and System Sciences, 20(3), 1980, 285-309.
• [13] Carmona, J., Cortadella, J.: Input/Output Compatibility of Reactive Systems, Proceedings of the Fourth International Conference on Formal Methods in Computer-Aided Design (FMCAD'02), Portland, Oregon (M. D. Aagaard, J. W. O'Leary, Eds.), Lecture Notes in Computer Science 2517, Springer-Verlag, Berlin, 2002, 360-377.
• [14] De Simone, R.: Langages Infinitaires et Produit deMixage, Theoretical Computer Science, 31, 1984, 83-100.
• [15] Drusinsky, D., Harel, D.: On the Power of Bounded Concurrency I-Finite Automata, Journal of the ACM, 41(3), 1994, 517-539.
• [16] Duboc, C.: Mixed Product and Asynchronous Automata, Theoretical Computer Science, 48(3), 1986, 183-199.
• [17] Ellis, C. A.: Team Automata for Groupware Systems, Proceedings of the International ACM SIGGROUP Conference on Supporting Group Work-The Integration Challenge (GROUP'97), Phoenix, Arizona (S. C. Hayne,W. Prinz, Eds), ACM Press, New York, 1997, 415-424.
• [18] Emerson, E. A.: Alternative Semantics for Temporal Logics, Theoretical Computer Science, 26(1-2), 1983, 121-130. (See also Technical Report TR-182, Department of Computer Sciences, University of Texas, Austin, 1981.)
• [19] Ginsburg, S.: Algebraic and Automata-Theoretic Properties of Formal Languages, Fundamental Studies in Computer Science 2, North-Holland Publishing Company, Amsterdam, 1975.
• [20] Ginsburg, S., Spanier, E. H.: Mappings of Languages by Two-Tape Devices, Journal of the ACM, 12(3), 1965, 423-434.
• [21] Gischer, J. L.: Shuffle Languages, Petri Nets, and Context Sensitive Grammars, Communications of the ACM, 24, 1981, 597-605.
• [22] Jantzen, M.: The Power of Synchronizing Operations on Strings, Theoretical Computer Science, 14, 1981, 127-154.
• [23] Jonsson, B.: Compositional Specification and Verification of Distributed Systems, ACM Transactions on Programming Languages and Systems, 16(2), 1994, 259-303.
• [24] Karhumäki, J., Maurer, H. A., Păun, Gh., Rozenberg, G. (Eds.): Jewels are Forever-Contributions on Theoretical Computer Science in Honor of Arto Salomaa, Springer-Verlag, Berlin, 1999.
• [25] Kimura, T.: An Algebraic System for Process Structuring and Interprocess Communication, Proceedings of the Eighth ACM SIGACT Symposium on Theory of Computing (STOC'76), Hershey, Pennsylvania, ACM Press, New York, 1976, 92-100.
• [26] Lanotte, R., Maggiolo-Schettini, A., Peron, A.: Timed Cooperating Automata, Fundamenta Informaticae, 42(1-4), 2000, 1-21.
• [27] Latteux, M., Roos, Y.: Synchronized Shuffle and Regular Languages, In [24], 1999, 35-44.
• [28] Lothaire, M.: Combinatorics on Words, Encyclopedia of Mathematics and its Applications 17, Cambridge University Press, Cambridge, 1983.
• [29] Lynch, N. A., Tuttle,M. R.: An Introduction to Input/OutputAutomata, CWI Quarterly, 2(3), 1989, 219-246. (Also appeared as Technical Memo MIT/LCS/TM-373, Massachusetts Institute of Technology, Cambridge, Massachusetts, 1988.)
• [30] Manea, F., Mitrana, V., Voinescu, D.-C.: Synchronized Shuffle on Backbones, Fundamenta Informaticae, 73(1-2), 2006, 191-202.
• [31] Mateescu, A., Mateescu, G. D.: Fair and Associative Infinite Trajectories, In [24], 1999, 327-338.
• [32] Mateescu, A., Rozenberg, G., Salomaa, A.: Shuffle on Trajectories: Syntactic Constraints, Theoretical Computer Science, 197(1-2), 1998, 1-56.
• [33] Ogden,W. F., Riddle, W. E., Rounds,W. C.: Complexity of Expressions Allowing Concurrency, Conference Record of the Fifth Annual ACM Symposium on Principles of Programming Languages (POPL'78), Tucson, Arizona, ACM Press, New York, 1978, 185-194.
• [34] von Oheimb, D., Lotz, V.: Formal Security Analysis with Interacting StateMachines, Proceedings of the Seventh European Symposium on Research in Computer Security (ESORICS'02), Zürich, Switzerland (D. Gollmann, G. Karjoth, M. Waidner, Eds.), Lecture Notes in Computer Science 2502, Springer-Verlag, 2002, 212-228.
• [35] Park, D.: On the semantics of fair parallelism, Proceedings of the Copenhagen Winter School on Abstract Software Specifications (D. Bjørner, Ed.), Lecture Notes in Computer Science 86, Springer-Verlag, Berlin, 1979, 504-526.
• [36] Perrin, D., Pin, J. - E.: Infinite Words-Automata, Semigroups, Logic and Games, Pure and Applied Mathematics 141, Elsevier Science Publishers, Amsterdam, 2004.
• [37] Redziejowski, R. R.: Associative Omega-products of Traces, Fundamenta Informaticae, 67(1-3), 2005, 175-185.
• [38] Roscoe, A. W.: The Theory and Practice of Concurrency, Prentice Hall, London, 1997.
• [39] Sakarovitch, J., Simon, I.: Subwords, Chapter 6 in [28], 1983, 105-142.
• [40] Shaw, A. C.: Software Descriptions with Flow Expressions, IEEE Transactions on Software Engineering, 4(3), 1978, 242-254.
• [41] van de Snepscheut, J. L. A.: Trace Theory and VLSI Design, Lecture Notes in Computer Science 200, Springer-Verlag, Berlin, 1985.