Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi I have a notation question.

I've recently come across the '*-operation' (star-operation) in the context of a binary operation on two automata e.g., A*B and I'm not sure exactly what it means (and it's rather difficult to google).

In the context of a unary operation on a single transducer/acceptor A* generally refers to the kleene closure, but I'm not familiar with the binary context. Further, in the context of a binary operation, this is distinct from general composition or weighted composition.

edit: after some furious googling, i found that the binary kleene * is described in,

"Representation of Events in Nerve Nets and Finite Automata", Kleene, 1956

http://www.dlsi.ua.es/~mlf/nnafmc/papers/kleene56representation.pdf

from page 24, paragraph 3:

If E and F are sets of tables, E*F ( the iterate of E on F, or briefly E iterate F) shall be in the infinite sum of the sets F, EF, EEF, EEEF, ..., or in self-explanatory symbolism, F v EF v EEF v ... or $\sum_{n=0}^{\infty} E^{n}F$.

share|improve this question
    
Can you describe a bit more about the context in which you found it? Is it the creation of a new automaton multiplying the transition-graphs of the two automatons together, perhaps? –  sleepless in beantown Nov 16 '10 at 3:21
    
Though normally, the composition of two automata is designated by a small circle, e.g. $A \circ B$. –  sleepless in beantown Nov 16 '10 at 3:26
3  
Are you sure that what you're reading is not the concatenation of the Kleene-star closure of $A$ followed by the language of $B$? –  sleepless in beantown Nov 16 '10 at 3:31
1  
The ideal would be for you to give us a reference so that we can see the context. –  Mariano Suárez-Alvarez Nov 16 '10 at 3:48
    
And double check the entire paper, or book, or whatever you're reading. The smart convention, in well written mathematics papers, is to specifically define the notation used so that misunderstandings do not occur. I agree with Mariano Suarez-Alvarez that providing a reference would help others help you, and knowing in which year it was published would help in figuring out if it was old notational convention, and knowing the author's name would help in being able to figure out what the author might have meant... –  sleepless in beantown Nov 16 '10 at 3:53

1 Answer 1

after some furious googling, i found that the binary kleene * is described in,

"Representation of Events in Nerve Nets and Finite Automata", Kleene, 1956

http://www.dlsi.ua.es/~mlf/nnafmc/papers/kleene56representation.pdf

from page 24, paragraph 3:

If E and F are sets of tables, E*F ( the iterate of E on F, or briefly E iterate F) shall be in the infinite sum of the sets F, EF, EEF, EEEF, ..., or in self-explanatory symbolism, F v EF v EEF v ... or $\sum_{n=0}^{\infty} E^{n}F$.

I guess this is what sleepless_in_beantown was referring to, but it is defined as a binary operation in the text I'm reading ("Applied Combinatorics on Words") and several other papers, and it wasn't clear whether it was the same thing or not.

share|improve this answer
2  
@blackkettle, thanks for providing the reference and a link. It would appear that this "binary" usage of the Kleene star over $E$ and $F$ does appear to be equivalent to the interpretation of the Kleene-star as a unary-Kleene-closure over $E$ concatenated with $F$. The beginnings of "regular expressions", I guess. I'll download that link and peruse it. Thanks again for providing the link. –  sleepless in beantown Nov 16 '10 at 4:26
    
@sleepless in beantown I'm always a little bit awed and inspired when my reference searches take me back to one of these early works - it was the same when I found my way to Hopcroft's original description of his minimization algorithm. They are always well-written and pregnant with all manner of gems. i guess im just a real newb. –  blackkettle Nov 16 '10 at 4:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.