Transducers, multiple of cross product vs cross product of multiple

Transducers, multiple of cross product vs cross product of multiple

par Justyna Anna Czestochowska,
Number of replies: 5

On the last handson in morphology we were considering cross products of languages and their regexes, for example: A = {a} and B = {b}
(A+ cross product B+) gives us sequences: ab, aab, aaab, abb, abbb, aabb and so on

we defined as well that:

(A cross product B) + gives us only pairs of same length ab, aabb, aaabbb and so on.

Intuitively it doesn't seem right if we first create a cross product which in this case is "ab" and then apply + we would expect sequences ab,abab, ababab and so on. How to interpret or how to think about it, that + of cross product outputs only same length sequences?

Tags:
In reply to Justyna Anna Czestochowska

Re: Transducers, multiple of cross product vs cross product of multiple

par Jean-Cédric Chappelier,

I think your problem relates only to the convention of writing pairs (= transductions).
I'm not sure what you really mean by "ab, aabb, aaabbb and so on" as opposed to "ab,abab, ababab and so on" because none of these two makes sense (or then, both makes the SAME sense) related to A \otimes B.
Let me try to explain:
transduction means you have an input language and an output one ; which can be EQUIVALENTLY written either as a "n-cartesian product of "pairs"" ( (A x B) ^ n ) or as a ""pair" of  n-cartesian product" ( (A^n  x B^n) ).
Let's take one single example out of these sets: a transduction of the same length, to make it simpler:
aaa  --> bbb
can be written equivalently either as (a,b)(a,b)(a,b)  (element of (A x B) ^ n) or as (aaa, bbb) (element of A^n  x B^n)

Thus, to me, both your "ab, aabb, aaabbb"  and  "ab,abab, ababab" either don't mean anything, or do both mean the same thing:  a --> b, aa --> bb, aaa --> bbb, i.e.
(a,b), (aa, bb), (aaa, bbb).

This, regardless of the regular expressions you were referring to. From what I understood, it was not so much a question about the transducer regular expressions themselves but about the meaning of how transductions are mathematically written.

Is it clear now? (otherwise I can also explain the regular expressions themselves)

In reply to Jean-Cédric Chappelier

Re: Transducers, multiple of cross product vs cross product of multiple

par Justyna Anna Czestochowska,

I was probably too chaotic in my question. Let me make it more precise. My understanding is that if we have two regular languages A+ and B+, where A = {a} and B= {b}, A+ consists of sequences of characters: A+ = {a, aa, aaa, aaaa, ...} while B+ = {b, bb, bbb, bbbb,...}, in my understanding cross product of two regular languages products new language, meaning new set of sequences. In case of cross product of two regular languages A+ cross product B+ should give set of sequences: {ab, abb, abbb, abbbb, aab, aabb, aabbb, aabbbb, ...} consisting of all possible combinations of set A+ and B+. On slide 19 in morphology slides it is written that  A+ cross product B+ is not equal to (A cross product B) +. In my understanding (A cross product B) + should produce language of form {ab, abab, ababab, ...} but during handson session we said that (A cross product B) + produces set of following sequences {ab, aabb, aaabbb}. Please correct me if I'm wrong at any stage of my reasoning. The final question is what sequences does  (A cross product B) + produce?

In reply to Justyna Anna Czestochowska

Re: Transducers, multiple of cross product vs cross product of multiple

par Jean-Cédric Chappelier,

> cross product of two regular languages products new language, meaning new set of sequences.

As I tried to explain, I think your confusion comes from there: NO, not really, if your last word "sequence" has the usual meaning: it's NOT a sequence of **letters** : a cross product will give a sequence of PAIRS (which is actually the WHOLE story : pairs : input language TO output language)
It's NOT {ab, abb, abbb, abbbb, aab, aabb, aabbb, aabbbb, ...} if you mean it the usual way, but it's {(a,b), (a, bb), (a, bbb), ....} which mean : { a --> b, a --> bb, a --> bbb, ... } : not a set of "sequences" (in the usual sense) but a set of TRANSDUCTIONS.
Does it make more sense?

In reply to Jean-Cédric Chappelier

Re: Transducers, multiple of cross product vs cross product of multiple

par Justyna Anna Czestochowska,

It does I can see I confused those terms. In the end (A cross product B)+ is ({(a,b)})+ which gives {(a,b), (aa,bb), (aaa,bbb)} while 
A+ cross product B+ is:  {a, aa, aaa, aaaa,...} cross product {b, bb, bbb} which gives {(a,b), (aa,b), (aaa,b), (a,bb), (a,bbb), ...}