<p>It is well-known that regular languages can be defined equivalently via many formalisms, among which regular expressions, NFAs, finite monoids, Monadic Second-Order logic (MSO).</p>
<p>The cost (say in size of the objects, but it could be also time complexity) of translating from one of these formalisms to any other are also well-known, e.g. &quot;NFA-&gt;monoid&quot; is exponential, &quot;monoid-&gt;NFA&quot; is linear, &quot;MSO-&gt;(NFA or expression or monoid)&quot; is nonelementary, etc...</p>
<p>I'm looking for references (ideally the least possible amount of distinct works) where these complexities are clearly stated. Most works consider this as folklore, but I'm hoping some people made the effort of gathering this somewhere so that it can be cited in a technical report. My goal here is just to find something to cite for these folklore results, so that I don't have to describe some of the constructions by myself, and so that the interested reader, who is assumed to be a non-specialist, can follow the reference if he wants details about these classical constructions.</p>

CC BY-SA 4.0
2022-08-16T14:19:36.907Z
@PhilipWhite I know how to prove these results, I'm just interested in a reference that can be cited as a go-to for the reader.
Denis
CC BY-SA 4.0
2022-08-16T14:21:11.877Z
I'll make the question clearer to avoid this confusion. Thanks for your messages.
Denis
CC BY-SA 4.0
2022-08-17T07:59:52.460Z
@Denis A short survey summarising such results would be very useful. There are so many results in this direction, since this is such an old and important topic. Right now I'm sitting on a regular language related paper and would benefit a great deal from an up-to-date overview.
Martin Berger
<reference-request><regular-language><complexity><regular-expressions>
Reference for cost of translating between regular language formalisms
Denis
# Reference for cost of translating between regular language formalisms

(Asked by: username_0 on 2022-08-16)

It is well-known that regular languages can be defined equivalently via many formalisms, among which regular expressions, NFAs, finite monoids, Monadic Second-Order logic (MSO).

The cost (say in size of the objects, but it could be also time complexity) of translating from one of these formalisms to any other are also well-known, e.g. "NFA->monoid" is exponential, "monoid->NFA" is linear, "MSO->(NFA or expression or monoid)" is nonelementary, etc...

I'm looking for references (ideally the least possible amount of distinct works) where these complexities are clearly stated. Most works consider this as folklore, but I'm hoping some people made the effort of gathering this somewhere so that it can be cited in a technical report. My goal here is just to find something to cite for these folklore results, so that I don't have to describe some of the constructions by myself, and so that the interested reader, who is assumed to be a non-specialist, can follow the reference if he wants details about these classical constructions.

**Tags:** reference-request, regular-language, complexity, regular-expressions

> **Comments:**
> **username_0**: @PhilipWhite I know how to prove these results, I'm just interested in a reference that can be cited as a go-to for the reader.  
> **username_0**: I'll make the question clearer to avoid this confusion. Thanks for your messages.  
> **username_1**: @username_0 A short survey summarising such results would be very useful. There are so many results in this direction, since this is such an old and important topic. Right now I'm sitting on a regular language related paper and would benefit a great deal from an up-to-date overview.  

---

## 0 answers

