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.

  • $\begingroup$ I don't know, but if you're looking at algebraic issues relating to complexity, you might want to look at books like Descriptive Complexity by Neil Immerman or Finite Model Theory by Ebbinghaus and Flum. Even if the books don't contain specific articulations of these results, you might learn some of the tools (in DC in particular) to prove these results yourself; they might be essentially exercises to most TCS folks who see them as obvious and not worth publishing. You might also look at the paper, "Indexing of Subrecursive Classes" by Dexter Kozen. That's all I know. $\endgroup$
    – user1338
    Commented Aug 16, 2022 at 14:17
  • $\begingroup$ "Descriptive Complexity" doesn't address algebraic issues or most of the terms you stated, but it does address the logical tools and the concept of "structures" that you would need to formalize some of those concepts. D.C. is a logical-query-driven way to express Turing machines, and it's a common and very useful alternative to TMs that might be helpful for you to understand if you want to prove results about different indexings of algorithms. $\endgroup$
    – user1338
    Commented Aug 16, 2022 at 14:19
  • $\begingroup$ @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. $\endgroup$
    – Denis
    Commented Aug 16, 2022 at 14:19
  • $\begingroup$ Oh, yeah, I don't know. It sounds like you're asking if someone has already proved it and you would need to cite them...I have no clue, sorry. $\endgroup$
    – user1338
    Commented Aug 16, 2022 at 14:20
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Aug 17, 2022 at 7:59


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.