|
The literal and the initial literal shuffle have been introduced
to model the behavior of two synchronized processes.
However, it is not possible to describe the synchronization of multiple processes.
Furthermore, both restricted forms of shuffling
are not associative.
Here, we extend the literal shuffle and the initial literal shuffle to multiple arguments.
We also introduce iterated versions,
much different
from the iterated ones previously introduced for the binary literal and initial literal shuffle.
We investigate formal properties, and show that in terms of expressive power, in a full trio,
they coincide with the general shuffle. Furthermore, we look at closure properties
with respect to the regular, context-free, context-sensitive, recursive and recursively
enumerable languages for all operations introduced.
Then, we investigate various decision
problems motivated by analogous problems for the (ordinary) shuffle operation.
Most problems we look at are tractable, but we also identify one intractable decision problem.
|
