Synchronized Shuffle on Backbones

• Autorzy: Manea F. , Mitrana V. , Voinescu D-C.
• Języki publikacji: EN

Abstrakty

EN

In this paper we continue the study on synchronized shuffle started in [5] by introducing the condition that the two words which are to be shuffled have to synchronize on a predefined set of backbones. As far as the language-theoretic properties of this operation are concerned, we prove that in a trio the closure under shuffle is equivalent to the closure under synchronized shuffle on a regular set of backbones. Based on this result we show that a set of backbones is regular if and only if the synchronized shuffle of every two regular languages on that set is also regular. Some relationships between this operation and the synchronized shuffle operations introduced in [5] are presented and some open problem are finally discussed.

Słowa kluczowe

EN

shuffle; synchronized shuffle; backbone; synchronized shuffle on backbones; formal languages

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 73, nr 1-2
• Strony: 191--202
• Opis fizyczny: biblogr. 28 poz.

Twórcy

autor

Manea F.

autor

Mitrana V.

autor

Voinescu D-C.

• Faculty of Mathematics and Computer Science, Bucharest University, Str. Academiei 14, Bucharest, Romania,

Bibliografia

• [1] J.C.M. Baeten, W.P. Weijland: Process Algebra. Cambridge Tracts in Theoretical Computer Science 18, Cambridge University Press, Cambridge, 1990.
• [2] 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.
• [3] 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 (2003), 21-69.
• [4] M.H. ter Beek, J. Kleijn: Team automata satisfying compositionality. In Proceedings of FME 2003: Formal Methods-the 12th International Symposium on Formal Methods Europe, Pisa, Italy (K. Araki, S. Gnesi, D. Mandrioli, eds.), LNCS 2805, Springer-Verlag, Berlin, 2003, 381-400.
• [5] M.H. ter Beek, C.Mart´ın-Vide, V.Mitrana: Synchronized shuffle. Theoretical Computer Science, 341 (2005), 263-275.
• [6] J.A. Bergstra, A. Ponse, S.A. Smolka, eds.: Handbook of Process Algebra. Elsevier Science Publishers, Amsterdam, 2001.
• [7] S.L. Bloom, Z. ésik: Free shuffle algebras in language varieties. Theoretical Computer Science, 163 (1996), 55-98.
• [8] P.C.Y. Chen: A computationalmodel of a class of gene networks with positive and negative controls. BioSystems, 73 (2004), 13-24.
• [9] R. De Simone: Langages infinitaires et produit demixage. Theoretical Computer Science, 31 (1984), 83-100.
• [10] M. Domaratzki: Semantic shuffle on and deletion along trajectories. In Proc. Developments of Language Theory (C. Calude, E. Calude, M. Dinneen, eds.), LNCS 3340, Springer-Verlag, Berlin, 2004, 163-174.
• [11] S. Eilenberg: Automata, Languages, and Machines, Vol. A. Academic Press, New York, 1974.
• [12] S. Ginsburg, E.H. Spanier: Mappings of languages by two-tape devices. Journal of the ACM, 12 (1965), 423-434.
• [13] J.L. Gischer: Shuffle languages, Petri nets, and context sensitive grammars. Communications of the ACM, 24 (1981), 597-605.
• [14] M. Holzer, M. Kutrib: State complexity of basic operations on nondeterministic finite automata. In Implementation and Application of Automata CIAA 2002 (J.-M. Champarnaud, D. Maurel, eds.), LNCS 2608, Springer-Verlag, Berlin, 2003, 148-157.
• [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 of the 8th ACM SIGACT Symposium on Theory of Computing, Hershey, Pennsylvania, ACM Press, New York, 1976, 92-100.
• [17] J. Kleijn: Team automata for CSCW - A survey. In Petri Net Technology for Communication-Based Systems-Advances in Petri Nets (H. Ehrig,W. Reisig, G. Rozenberg, H.Weber, eds.), LNCS 2472, Springer-Verlag, Berlin, 2003, 295-320.
• [18] M. Latteux, Y. Roos: Synchronized shuffle and regular languages. In Jewels are Forever-Contributions on Theoretical Computer Science in Honor of Arto Salomaa (J. Karhumäki, H.A. Maurer, Gh. P˘aun, G. Rozenberg, eds.), Springer-Verlag, Berlin, 1999, 35-44.
• [19] A.Mateescu, G. Rozenberg,A. Salomaa: Shuffle on trajectories: Syntactic constraints. Theoretical Computer Science, 197 (1998), 1-56.
• [20] D. Park: On the semantics of fair parallelism. In Proceedings of the Copenhagen Winter School on Abstract Software Specifications (D. Bjørner, ed.), LNCS 86, Springer-Verlag, Berlin, 1979, 504-526.
• [21] A.W. Roscoe: The Theory and Practice of Concurrency. Prentice Hall International Series in Computer Science, London, 1997.
• [22] G. Rozenberg, A. Salomaa, eds.: Handbook of Formal Languages. Springer-Verlag, Berlin, 1997.
• [23] R. Schaffrath, K. Sasnauskas, P.A. Meacock: Use of gene shuffles to study the cytoplasmic transcription system operating on Kluyveromyces lactis linear DNA plasmids. Enzyme and Microbial Technology, 26 (2000), 664-670.
• [24] A.C. Shaw: Software descriptions with flow expressions. IEEE Transactions on Software Engineering, SE-4 (1978), 242-254.
• [25] J. van de Snepscheut: Trace Theory and VLSI Design. LNCS 200, Springer-Verlag, Berlin, 1985.
• [26] W. Wechler: Universal Algebra for Computer Scientists. EATCS Monographs on Theoretical Computer Science 25, Springer-Verlag, Berlin, 1992.
• [27] S. Yu, Q. Zhuang, K. Salomaa: The state complexities of some basic operations on regular languages. Theoretical Computer Science, 125 (1994), 315-328.
• [28] Y.-X. Zhang, K. Perry, V.A. Vinci, K. Powell, W.P.C. Stemmer, S.B. del Cardayré: Genome shuffling leads to rapid phenotypic improvement in bacteria. Nature, 415 (2002), 644-646.