Re: How to prove "Cfls are not closed under shuffling"

On Apr 15, 8:21 pm, "hampe...@xxxxxxxxx" <hampe...@xxxxxxxxx> wrote:
Thanks filip*,

acturally i have constructed a similar counter-example as yours.
However, the result of shuffling is a like a set of all possible
combinations while retaining previous order. eg.

shuffle $ab$ with $cd$ may get

abcd, acbd, cdab

That's not the same result I would have expected... I referred to the
following definition of the shuffle operator:

The shuffle A$B of languages A and B is the language consisting of
strings of the form u_{1}v_{1}u_{2}v_{2}...u_{n}v_{n} such that
u_{1}u_{2}...u_{n} is a string in A and v_{1}v_{2}...v_{n} is a string
in B. In other words, the shuffle of A and B consists of the
interleavings of all pairs of strings. [found at
http://groups.google.it/group/sci.math.research/browse_thread/thread/7ccf49f1b20c93c6/ef8dcecfeed7ed7b?lnk=st&q=shuffle+operator&rnum=1&hl=it#ef8dcecfeed7ed7b
]

So if L1 = {ab} and L2 = {cd}, then L1 & L2 = {acbd}. If L3 = {a, aaa}
and L4 = {bb}, then L3 & L4 = void_set because L3 and L4 have no
string with the same length.
Am I right? Have I misunderstood the definition? Did you refer to a
different one?

In your solution, we have one counter-example, but does that suffice?
Because the subset of a CFL is not necessarily c.f.

Because L_3 which you have constructed is a subset of shuffle, does
that suffice to prove the claim?

Obviously it doesn't! It sounds like another funny exercise
considering the definition you posed.

thanks again:)

Thank to you.

.

Relevant Pages

  • one-party shuffling
    ... let's say party A has n Strings a_1,...a_n. ... "A Verifiable Secret Shuffle of Homomorphic Encryptions" from J. Groth. ... with the circuits quiet well. ...
    (sci.crypt)
  • Re: How to prove "Cfls are not closed under shuffling"
    ... combinations while retaining previous order. ... In your solution, we have one counter-example, but does that suffice? ... Because L_3 which you have constructed is a subset of shuffle, ...
    (comp.theory)