To reason about whether a language is R, RE, or co-RE, we can use many-one reductions to show how the difficulty (R, RE, or co-RE-ness) of one language influences the difficulty of another. To reason about whether a language is in P, NP, or co-NP, we can use polynomial-time many-one reductions to show how the difficulty (P, NP, or co-NP-ness) of one language influences the difficulty of another.

Is there are similar type of reduction we can use for regular languages? For example, is there some type of reduction $\le_R$ such that if $L_1 \le_R L_2$ and $L_2$ is regular, then $L_1$ is regular? Clearly we could arbitrarily define a very specific class of reductions such that this property holds, but is there a known type of reduction with this property?


  • $\begingroup$ I'm not quite clear on what you're asking for. What would be an example of a 'type of reduction'? $\endgroup$ – Tara B Jun 8 '12 at 21:16
  • $\begingroup$ @TaraB- By "type of reduction," I mean a class of functions (analogous to, say, computable functions, polynomial-time computable functions, etc.) such that we define L_1 <=R L_2 iff there is a function of this type where w in L_1 iff f(w) in L_2. Does that clarify things? Or should I try to elaborate a bit further? $\endgroup$ – templatetypedef Jun 8 '12 at 21:18
  • $\begingroup$ Sorry about that misplaced answer: it belonged with another question altogether that I had open at the same time. $\endgroup$ – Brian M. Scott Jun 8 '12 at 21:18
  • $\begingroup$ @templatetypedef: I think it clarifies things, although what it mainly clarified for me was that I'm quite tired and am not going to think about this right now. =] $\endgroup$ – Tara B Jun 8 '12 at 21:23
  • $\begingroup$ I would recommend crossposting this to cstheory stackexchange, even if an answer is already given, for future users' convenience. Be sure to mention that you crossposted it on both sites if you do. $\endgroup$ – chazisop Jun 14 '12 at 12:52

There is a very natural model of finite-state reduction, namely the most general finite-state transducer -- one input tape, one output tape, non-deterministic, transitions can be labelled with arbitrary regular sets (with empty strings) on both the input and output side. This can be shown equivalent to Henning's single-symbol operations, but allows for much more intuitive reductions, still within the finite-state realm. The ambiguity Henning speaks of is just the non-determinism.

You can even allow such a transducer to have secondary storage (like a Turing Machine, pushdown automaton, etc) as long as there is a uniform constant bound on the size of the secondary storage.

Taking that a step further, you can use transformations that do arbitrary computations, but again show that the size of memory needed over all inputs is uniformly bounded, that is, there's a $k$ not depending on the input that limits the size of all memory used. Thus you can use pseudo-code, Java or whatever formalism you like, including forking, that is, non-determinism -- as long as you have:

  • one input and one output tape/stream
  • both streams processed in a single pass
  • total memory is uniformly bounded across all forks/threads

In other words, you don't have to model finite-state transformations with transitions on a finite graph, which is a very brittle and finicky programming model. You can use any convenient programming formalism or model with any structuring of memory you like, as long as it satisfies those criteria.

In fact, I propose that as a sort of finite-state equivalent of the Turing-Church thesis. Not quite as crisp as the Turing-Church Thesis in the world of recursive functions, but very useful.


In general, for reductions to be a useful reasoning concept, we need to require that the reduction function is easy enough to compute that it can be done within the same resource constraints as the complexity class we're ultimately interested in. Because the class of regular languages correspond to the very weak computational model of finite-state machines, any permissible reductions would have to be similarly weak.

More precisely, we'd need to consider reductions that can be expressed as finite state machines themselves: something like a machine with a state drawn from a finite set, where each transition (determined by the current state and the scanned input symbol) can either be to move to the next input symbol or output a given output symbol.

Another way to express these transformations is that they are the functions that can be programmed using only a finite number of global variables each of which has a finite value set, with a "read one symbol" command, a "print one symbol" command, and a basic set of control structures (if, goto, while, switch, do-while, and non-recursive subroutines).

Arguing through such reductions would clearly work, but since they are so restricted, I think it will often be just as hard to convince oneself that the reduction one has in mind is permissible as it would to be to argue from first principles that the initial language is regular.

This might be different if there were a more natural model for FSM transformations -- perhaps some kind of output-annotated regular expressions. But it's not clear to me exactly that would work, since regular expressions can be ambiguous. Perhaps speaking about "one-many reductions" could make it work, though.

  • 1
    $\begingroup$ Don't regular expression homomorphisms correspond to just the sort of reductions you discuss? It is quite common to show that some language is regular by showing that it is equivalent to a known language under reverse homomorphism. $\endgroup$ – MJD Jun 8 '12 at 22:28
  • $\begingroup$ @Mark: Perhaps. What is a "regular expression homomorphism"? There are only a few google hits. $\endgroup$ – hmakholm left over Monica Jun 8 '12 at 22:32
  • $\begingroup$ I misspoke, but the idea is real. A homomorphism is a replacement of single symbols with fixed strings. Homomorphic images of regular languages are regular, as are inverse homomorphic images of regular languages. See for example pp 14–24 of these notes by Jeffrey Ullman $\endgroup$ – MJD Jun 8 '12 at 23:15
  • $\begingroup$ @Mark, if would have helped if you said "monoid homomorphism". $\endgroup$ – hmakholm left over Monica Jun 9 '12 at 14:06

The important property that guarantees such reductions make sense is composition: a polynomial-time reduction works because the composition of an P/NP/co-NP Turing machine with a P machine is again a P/NP/co-NP machine.

We can define composition for finite state automata too: see Wikipedia on finite state transducers. Then $L_1\le_R L_2$ iff there is a finite state transducer mapping words from $L_1$ to words from $L_2$ and words from $\Sigma_1^*\setminus L_1$ to words from $\Sigma_2^*\setminus L_2$. This reduction satisfies your requirements.

Of course, you can do similar things with all other kinds of automata, or really anything where you can define composition. For composition to exist, you need to be able to represent functions from words to words, which is why we needed to work with transducers instead of classic finite automata.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.