# zbMATH — the first resource for mathematics

Shuffle on trajectories: Syntactic constraints. (English) Zbl 0902.68096
Summary: We introduce and investigate new methods to define parallel composition of words and languages as well as of $$\omega$$-words and $$\omega$$-languages. The operation of parallel composition leads to new shuffle-like operations defined by syntactic constraints on the usual shuffle operation. The approach is applicable to concurrency, providing a method to define parallel composition of processes. It is also applicable to parallel computation. The operations are introduced using a uniform method based on the notion of trajectory. As a consequence, we obtain a very intuitive geometrical interpretation of the parallel composition operation. These operations lead in a natural way to a large class of semirings. The approach is amazingly flexible, diverse concepts from the theory of concurrency can be introduced and studied in this framework. For instance, we provide examples of applications to fairness property and to parallelization of non-context-free languages in terms of context-free and even regular languages. This paper concentrates on syntactic constraints. Semantic constraints will be dealt with in a forthcoming contribution.

##### MSC:
 68Q45 Formal languages and automata 68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
##### Keywords:
shuffle; concurrency; parallel computation; formal languages
Full Text:
##### References:
 [1] Aalbersberg, I.J.J.; Rozenberg, G., Theory of traces, Theoret. comput. sci., 60, 1-82, (1988) · Zbl 0652.68017 [2] Axford, T., Concurrent programming fundamental techniques for real time and parallel software design, (1989), Wiley New York · Zbl 1080.68559 [3] Baeten, J.C.M.; Weijland, W.P., Process algebra, (1990), Cambridge University Press Cambridge · Zbl 0716.68002 [4] Bergstra, J.A.; Klop, J.W., Process algebra for synchronous communication, Inform. control, 60, 109-137, (1984) · Zbl 0597.68027 [5] Cohn, P.M., Universal algebra, (1980), D. Reidel New York · Zbl 0424.16002 [6] Dassow, J.; Păun, G., Regulated rewriting in formal language theory, (1989), Springer Berlin [7] () [8] Duchamp, G.; Krob, D., Combinatorics in trace monoids II, (), 83-130 [9] Eilenberg, S., () [10] Ginsburg, S., The mathematical theory of context-free languages, (1966), McGraw Hill New York · Zbl 0184.28401 [11] Ginsburg, S.; Spanier, E.H., Bounded regular sets, (), 1043-1049 · Zbl 0147.25301 [12] Ginsburg, S.; Spanier, E.H., AFL with semilinear property, J. comput. system sci., 5, 365-396, (1971) · Zbl 0235.68029 [13] Golan, J.S., The theory of semirings with applications in mathematics and theoretical computer science, (1992), Longman Scientific and Technical Harlow, Essex · Zbl 0780.16036 [14] Golan, J.S.; Mateescu, A.; Vaida, D., Semirings and parallel composition of processes, J. automata languages combin., 1, 199-217, (1996) · Zbl 0867.68050 [15] Guo, L.; Salomaa, K.; Yu, S., Synchronization expressions and languages, () · Zbl 0843.68055 [16] Haines, L.H., On free monoids partially ordered by embedding, J. combin. theory, 6, 94-98, (1969) · Zbl 0224.20065 [17] Harju, T.; Lipponen, M.; Mateescu, A., Flatwords and post correspondence problem, Theoret. comput. sci., 161, 93-108, (1996) · Zbl 0872.68088 [18] Hennessy, M., Algebraic theory of processes, (1988), The MIT Press Cambridge, MA, London · Zbl 0744.68047 [19] Higman, G.H., Ordering by divisibility in abstract algebras, (), 326-336 · Zbl 0047.03402 [20] lanov, Iu.I.; Muchnic, A.A., On the existence of k-valued closed classes not having a finite base, Dokl. akad. nauk SSSR, 127, 44-46, (1959) [21] Ibarra, O., Simple matrix grammars, Inform. control, 17, 359-394, (1970) · Zbl 0221.68041 [22] Kari, L., On insertion and deletion in formal languages, () [23] Kasai, T., An hierarchy between context-free and context-sensitive languages, J. comput. system sci., 4, 492-508, (1970) · Zbl 0212.02705 [24] Kudlek, M.; Mateescu, A., Distributed catenation and chomsky hierarchy, (), 313-322 [25] Kudlek, M.; Mateescu, A., Rational and algebraic languages with distributed catenation, (), 129-138 · Zbl 1096.68660 [26] Kuich, W., The Kleene and the Parikh theorem in complete semirings, (), 212-225 [27] Kuich, W.; Salomaa, A., Semirings, automata, languages, EATCS monographs on theoretical computer science, (1986), Springer Berlin [28] Lothaire, M., () [29] Mateescu, A., On (left) partial shuffle, (), 264-278 [30] Mateescu, A.; Salomaa, A., Formal languages: an introduction and a synopsis, (), 1-40, Chapter 1 [31] Maurer, H.A.; Rozenberg, G.; Welzl, E., Using string languages to describe picture languages, Inform. control, 3, 155-185, (1982) · Zbl 0523.68065 [32] Mazurkiewicz, A., Concurrent program schemes and their interpretations, DAIMI rep. PB 78, (1977), Aarhus [33] Mazurkiewicz, A., Introduction to trace theory, (), 3-42 [34] Milner, R., A calculus of communicating systems, () · Zbl 0452.68027 [35] Milner, R., Communication and concurrency, (1989), Prentice Hall Englewood Cliffs, NJ · Zbl 0683.68008 [36] Post, E.L., The two-valued iterative systems of mathematical logic, (1941), Princeton University Press NJ · Zbl 0063.06326 [37] Park, D., Concurrency and automata on infinite sequences, (), 167-183 [38] Perrin, D.; Pin, J.E., Mots infinis, Report LITP 93.40, (1993) [39] Raz, D., On slender context-free languages, (), 445-454 · Zbl 1379.68230 [40] Ree, R., Lie elements and an algebra associated with shuffles, Ann. math., 68, 210-220, (1958) · Zbl 0083.25401 [41] Reutenauer, C., Free Lie algebras, (1993), Clarendon Press Oxford · Zbl 0798.17001 [42] Sakarovitch, J.; Simon, I., Subwords, () [43] Salomaa, A., On many-valued systems of logic, Ajatus philos. soc. Finland, 22, 115-159, (1959) [44] Salomaa, A., On infinitely generated sets of operations in finite algebras, Ann. universitatis turkuensis, ser. A I, 74, 13, (1964) · Zbl 0123.00503 [45] Salomaa, A., Formal languages, (1973), Academic Press New York · Zbl 0262.68025 [46] Siromoney, R., On equal matrix languages, Inform. control, 14, 135-151, (1969) · Zbl 0169.31402 [47] Thomas, W., Automata on infinite objects, (), 135-191 · Zbl 0900.68316
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.