<p>I'm trying to understand "Edit Distance of Weighted Automata" by Mehryar Mohri: [83], [93] and [99] at <a href="http://www.cs.nyu.edu/~mohri/pub/" rel="nofollow">http://www.cs.nyu.edu/~mohri/pub/</a> (they are virtually identical so which of them doesn't matter).</p>

<p>Could  anyone help me understand the main differences between the algorithm for the tropical semiring and that for the probabilistic semiring? </p>

<p>Right now I could, maybe, basically explain what happens, but I can't explain the idea behind it. Thank you so much!</p>

CC BY-SA 2.5
2011-01-19T21:19:01.613Z
While this is not homework in the literal sense, it's the same in spirit. You have to make a presentation and you're asking for help "solving" it. Normally, this would be grounds for closing: however, you do have a very specific concrete question in the second paragraph. I'd recommend rephrasing the question to focus attention on that aspect (not on "summarizing the algorithm"), in which case it's a reasonable question to ask.
Suresh Venkat
CC BY-SA 2.5
2011-01-19T21:21:54.560Z
I didn't know that homework is grounds for closing here. Other SE sites even have a "homework" tag. But yes, I'll edit it, thanks for the notice.
Felix Dombek
CC BY-SA 2.5
2011-01-20T00:47:00.017Z
this site is for research-level questions, the policy is similar to MathOverflow. People asking homework level questions are directed to Math.SE and they are acceptable there.
Kaveh
CC BY-SA 2.5
2011-01-20T04:16:25.667Z
I think the question is more focused and more reasonable now.
Suresh Venkat
<fl.formal-languages><automata-theory><edit-distance>
Edit-Distance of weighted automata
Felix Dombek
# Edit-Distance of weighted automata

(Asked by: username_0 on 2011-01-19)

I'm trying to understand "Edit Distance of Weighted Automata" by Mehryar Mohri: [83], [93] and [99] at <http://www.cs.nyu.edu/~mohri/pub/> (they are virtually identical so which of them doesn't matter).

Could anyone help me understand the main differences between the algorithm for the tropical semiring and that for the probabilistic semiring?

Right now I could, maybe, basically explain what happens, but I can't explain the idea behind it. Thank you so much!

**Tags:** fl.formal-languages, automata-theory, edit-distance
> **Comments:**
> **username_1**: While this is not homework in the literal sense, it's the same in spirit. You have to make a presentation and you're asking for help "solving" it. Normally, this would be grounds for closing: however, you do have a very specific concrete question in the second paragraph. I'd recommend rephrasing the question to focus attention on that aspect (not on "summarizing the algorithm"), in which case it's a reasonable question to ask.  
> **username_0**: I didn't know that homework is grounds for closing here. Other SE sites even have a "homework" tag. But yes, I'll edit it, thanks for the notice.  
> **username_2**: this site is for research-level questions, the policy is similar to MathOverflow. People asking homework level questions are directed to Math.SE and they are acceptable there.  
> **username_1**: I think the question is more focused and more reasonable now.  

---

## 0 answers

