6
$\begingroup$

Have been any interesting formulations for the concept of reduction between regular langauges, and if so -- are there regular-complete languages under those reductions?

$\endgroup$
  • $\begingroup$ Once you define a notion of reduction, there automatically becomes a notion of complete languages. Did you have any particular kind of reduction in mind? Or any aspect of regular languages you want to use it to shed light on? $\endgroup$ – D.W. Mar 31 at 16:03
  • $\begingroup$ No, just interested if such notions have been studied. $\endgroup$ – user2304620 Mar 31 at 16:07
  • $\begingroup$ As indicated by D.W., the right question to ask is, is there a reasonable and interesting notion of reduction for regular language? I recommend you to update your post with that question. $\endgroup$ – Apass.Jack Mar 31 at 16:09
  • $\begingroup$ I have edited the question accordingly. $\endgroup$ – user1767774 Mar 31 at 16:39
  • $\begingroup$ @D.W. Even with a notion of reduction, there might not be complete problems. For example, there are no known complete problems for TFNP. $\endgroup$ – David Richerby Mar 31 at 20:52
8
$\begingroup$

Barrington, Compton, Straubing and Thérien showed, in their paper Regular languages in $\mathsf{NC^1}$, that if the syntactic monoid of a regular language contains a nonsolvable finite group then the language is $\mathsf{NC^1}$-complete with respect to $\mathsf{AC^0}$-reductions (these are reductions computed by polynomial size, constant depth circuits with unbounded fan-in). Barrington's theorem implies that all regular languages are in $\mathsf{NC^1}$, and so such regular languages are complete for the set of regular languages under $\mathsf{AC^0}$-reductions.

Since we know that $\mathsf{AC^0} \neq \mathsf{NC^1}$ (for example, the parity function is in the latter but not in the former), regular languages in $\mathsf{AC^0}$ cannot be complete. For example, the language $a^*b^*$ isn't complete. Similarly, $\mathsf{AC^0}[p] \neq \mathsf{NC^1}$, showing that the language $(aa)^*$ isn't complete.

The simplest example of a language which satisfies the condition above is the language of all words over $S_5$ (the symmetric group on 5 elements) which multiply to the identity. The syntactic monoid of this language is $S_5$, which is a nonsolvable finite group. The slightly smaller alternating group $A_5$ would also work.

$\endgroup$
7
$\begingroup$

It only makes sense to talk about reductions between languages if the reduction are allowed to use less resources than the languages we're talking about. For example, when we reduce between problems in NP, we use (deterministic) polynomial-time reductions, or even log-space reductions. (OK, we don't know that those are less powerful than NP, but they seem to be.) If you don't use reductions that are weaker than the class of problems you're interested in, you end up with the boring result that everything except $\emptyset$ and $\Sigma^*$ is complete.

All regular languages can be decided in linear time and constant space. It's hard to imagine any weaker resource bound that you could use to perform the reductions, so the concept of reductions probably isn't interesting, here.

$\endgroup$

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.