Skip to main content

All Questions

Filter by
Sorted by
Tagged with
2 votes
1 answer
124 views

Proof of dynamic programming calculation of Levenshtein distance

Let s1 and s2 are 2 arbitrary strings with lengths l1 and ...
St.Antario's user avatar
7 votes
1 answer
494 views

Normal form for terms in language with two ring structures

Suppose I have two different ring structures on the same domain $\langle R,+,\cdot,0,1\rangle$, $\langle R,\oplus,\otimes,\bar 0,\bar 1\rangle$ and I throw the structures together into a single common ...
Joel David Hamkins's user avatar
2 votes
1 answer
197 views

Varieties of rational languages and (pseudo-)varieties of finite monoids, question regarding closure property

Let $\mathcal Rat(A)$ denote the class of rational (or regular) languages over the alphabet $A$, a subset $\mathcal V(A) \subseteq \mathcal Rat(A)$ is called a variety of (rational) languages iff ...
StefanH's user avatar
  • 798