Welcome to MathOverflow

Question

0

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$.

edited Nov 16 2010 at 4:17

asked Nov 16 2010 at 2:53

blackkettle
33●6

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 2010 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 2010 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 2010 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 2010 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 2010 at 3:53

show 2 more comments

blackkettle · Answer 1 · 2010-11-16 04:21:08Z UTC

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.

What does the *-operation signify in the binary context of two automata?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.