Hostname: page-component-745bb68f8f-s22k5 Total loading time: 0 Render date: 2025-02-03T08:32:44.023Z Has data issue: false hasContentIssue false
  • English
  • Français

Languages under concatenation and shuffling

Published online by Cambridge University Press:  04 March 2009

Steven T. Tschantz
Steven T. Tschantz
Affiliation:
Department of Mathematics, Vanderbilt University, Nashville, TN 37240
Get access Rights & Permissions [Opens in a new window]

Extract

The shuffle product of two words u and v, denoted u‖v, is the set of all words of the form x1y1x2y2…xnyn for some n and for some (possible empty) words x1, …xn, y1, …yn, such that u = x1x2…xn, and v = y1y2…yn. In other words, u‖v is the set of all possible words that can be obtained by merging u and v so that the letters of u and v separately maintain their original orders but are allowed to alternate arbitrarily. The shuffle product of languages L and M, denoted L‖M, is the union of all u‖v for u ∈ L and v ∈ M.

Type
Research Article
Information
Mathematical Structures in Computer Science , Volume 4 , Issue 4 , December 1994 , pp. 505 - 511
Copyright
Copyright © Cambridge University Press 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Gischer, J. L. (1988) The equational theory of pomsets. Theoretical Computer Science 61 199–224.CrossRefGoogle Scholar
Valdes, J., Tarjan, R. E. and Lawler, E. L. (1982) The recognition of series-parallel digraphs. SIAM J. Comput. 11 298–313.CrossRefGoogle Scholar