Is there a reasonable and studied concept of reduction between regular languages? Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern) Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?Are there regular languages between every two non-regular languages?The number of different regular languagesGenerators of families of langauges?Regular languages and sets proofRegular languages that can't be expressed with only 2 regex operationsRegular languages and constructing a regular grammarClosure under reversal of regular languages: Proof using AutomataUndecidable Problem for Regular LanguagesUnderstanding facts about regular languages, finite sets and subsets of regular languagesConstructive proof to show the quotient of two regular languages is regular
What was the last x86 CPU that did not have the x87 floating-point unit built in?
Active filter with series inductor and resistor - do these exist?
Biased dice probability question
Are my PIs rude or am I just being too sensitive?
Windows 10: How to Lock (not sleep) laptop on lid close?
What can I do if my MacBook isn’t charging but already ran out?
Why use gamma over alpha radiation?
How to say that you spent the night with someone, you were only sleeping and nothing else?
Is above average number of years spent on PhD considered a red flag in future academia or industry positions?
Can the prologue be the backstory of your main character?
New Order #5: where Fibonacci and Beatty meet at Wythoff
Simulating Exploding Dice
Can I throw a longsword at someone?
Is there a service that would inform me whenever a new direct route is scheduled from a given airport?
Slither Like a Snake
Who can trigger ship-wide alerts in Star Trek?
Estimate capacitor parameters
When is phishing education going too far?
Autumning in love
What do you call the holes in a flute?
Can a zero nonce be safely used with AES-GCM if the key is random and never used again?
How to politely respond to generic emails requesting a PhD/job in my lab? Without wasting too much time
Statistical model of ligand substitution
What's the point in a preamp?
Is there a reasonable and studied concept of reduction between regular languages?
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)
Announcing the arrival of Valued Associate #679: Cesar Manara
Unicorn Meta Zoo #1: Why another podcast?Are there regular languages between every two non-regular languages?The number of different regular languagesGenerators of families of langauges?Regular languages and sets proofRegular languages that can't be expressed with only 2 regex operationsRegular languages and constructing a regular grammarClosure under reversal of regular languages: Proof using AutomataUndecidable Problem for Regular LanguagesUnderstanding facts about regular languages, finite sets and subsets of regular languagesConstructive proof to show the quotient of two regular languages is regular
$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?
regular-languages finite-automata
edited Mar 31 at 18:45
David Richerby
70.4k16107196
asked Mar 31 at 15:37
user2304620user2304620
312
$endgroup$
add a comment |
$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?
regular-languages finite-automata
edited Mar 31 at 18:45
David Richerby
70.4k16107196
asked Mar 31 at 15:37
user2304620user2304620
312
$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
add a comment |
$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?
regular-languages finite-automata
edited Mar 31 at 18:45
David Richerby
70.4k16107196
asked Mar 31 at 15:37
user2304620user2304620
312
$endgroup$
Have been any interesting formulations for the concept of reduction between regular langauges, and if so -- are there regular-complete languages under those reductions?
regular-languages finite-automata
regular-languages finite-automata
edited Mar 31 at 18:45
David Richerby
70.4k16107196
asked Mar 31 at 15:37
user2304620user2304620
312
edited Mar 31 at 18:45
David Richerby
70.4k16107196
asked Mar 31 at 15:37
user2304620user2304620
312
edited Mar 31 at 18:45
David Richerby
70.4k16107196
edited Mar 31 at 18:45
David Richerby
70.4k16107196
edited Mar 31 at 18:45
David Richerby
70.4k16107196
70.4k16107196
asked Mar 31 at 15:37
user2304620user2304620
312
asked Mar 31 at 15:37
user2304620user2304620
312
asked Mar 31 at 15:37
user2304620user2304620
312
312
$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
add a comment |
$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
$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$
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$
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$
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$
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
$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
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Barrington, Compton, Straubing and Thérien showed, in their paper Regular languages in $mathsfNC^1$, that if the syntactic monoid of a regular language contains a nonsolvable finite group then the language is $mathsfNC^1$-complete with respect to $mathsfAC^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 $mathsfNC^1$, and so such regular languages are complete for the set of regular languages under $mathsfAC^0$-reductions.
Since we know that $mathsfAC^0 neq mathsfNC^1$ (for example, the parity function is in the latter but not in the former), regular languages in $mathsfAC^0$ cannot be complete. For example, the language $a^*b^*$ isn't complete. Similarly, $mathsfAC^0[p] neq mathsfNC^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.
answered Mar 31 at 18:08
Yuval FilmusYuval Filmus
197k15185349
$endgroup$
add a comment |
$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.
answered Mar 31 at 16:11
David RicherbyDavid Richerby
70.4k16107196
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f106297%2fis-there-a-reasonable-and-studied-concept-of-reduction-between-regular-languages%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Barrington, Compton, Straubing and Thérien showed, in their paper Regular languages in $mathsfNC^1$, that if the syntactic monoid of a regular language contains a nonsolvable finite group then the language is $mathsfNC^1$-complete with respect to $mathsfAC^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 $mathsfNC^1$, and so such regular languages are complete for the set of regular languages under $mathsfAC^0$-reductions.
Since we know that $mathsfAC^0 neq mathsfNC^1$ (for example, the parity function is in the latter but not in the former), regular languages in $mathsfAC^0$ cannot be complete. For example, the language $a^*b^*$ isn't complete. Similarly, $mathsfAC^0[p] neq mathsfNC^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.
answered Mar 31 at 18:08
Yuval FilmusYuval Filmus
197k15185349
$endgroup$
add a comment |
$begingroup$
Barrington, Compton, Straubing and Thérien showed, in their paper Regular languages in $mathsfNC^1$, that if the syntactic monoid of a regular language contains a nonsolvable finite group then the language is $mathsfNC^1$-complete with respect to $mathsfAC^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 $mathsfNC^1$, and so such regular languages are complete for the set of regular languages under $mathsfAC^0$-reductions.
Since we know that $mathsfAC^0 neq mathsfNC^1$ (for example, the parity function is in the latter but not in the former), regular languages in $mathsfAC^0$ cannot be complete. For example, the language $a^*b^*$ isn't complete. Similarly, $mathsfAC^0[p] neq mathsfNC^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.
answered Mar 31 at 18:08
Yuval FilmusYuval Filmus
197k15185349
$endgroup$
add a comment |
$begingroup$
Barrington, Compton, Straubing and Thérien showed, in their paper Regular languages in $mathsfNC^1$, that if the syntactic monoid of a regular language contains a nonsolvable finite group then the language is $mathsfNC^1$-complete with respect to $mathsfAC^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 $mathsfNC^1$, and so such regular languages are complete for the set of regular languages under $mathsfAC^0$-reductions.
Since we know that $mathsfAC^0 neq mathsfNC^1$ (for example, the parity function is in the latter but not in the former), regular languages in $mathsfAC^0$ cannot be complete. For example, the language $a^*b^*$ isn't complete. Similarly, $mathsfAC^0[p] neq mathsfNC^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.
answered Mar 31 at 18:08
Yuval FilmusYuval Filmus
197k15185349
$endgroup$
Barrington, Compton, Straubing and Thérien showed, in their paper Regular languages in $mathsfNC^1$, that if the syntactic monoid of a regular language contains a nonsolvable finite group then the language is $mathsfNC^1$-complete with respect to $mathsfAC^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 $mathsfNC^1$, and so such regular languages are complete for the set of regular languages under $mathsfAC^0$-reductions.
Since we know that $mathsfAC^0 neq mathsfNC^1$ (for example, the parity function is in the latter but not in the former), regular languages in $mathsfAC^0$ cannot be complete. For example, the language $a^*b^*$ isn't complete. Similarly, $mathsfAC^0[p] neq mathsfNC^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.
answered Mar 31 at 18:08
Yuval FilmusYuval Filmus
197k15185349
answered Mar 31 at 18:08
Yuval FilmusYuval Filmus
197k15185349
answered Mar 31 at 18:08
Yuval FilmusYuval Filmus
197k15185349
answered Mar 31 at 18:08
Yuval FilmusYuval Filmus
197k15185349
197k15185349
add a comment |
add a comment |
$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.
answered Mar 31 at 16:11
David RicherbyDavid Richerby
70.4k16107196
$endgroup$
add a comment |
$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.
answered Mar 31 at 16:11
David RicherbyDavid Richerby
70.4k16107196
$endgroup$
add a comment |
$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.
answered Mar 31 at 16:11
David RicherbyDavid Richerby
70.4k16107196
$endgroup$
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.
answered Mar 31 at 16:11
David RicherbyDavid Richerby
70.4k16107196
answered Mar 31 at 16:11
David RicherbyDavid Richerby
70.4k16107196
answered Mar 31 at 16:11
David RicherbyDavid Richerby
70.4k16107196
answered Mar 31 at 16:11
David RicherbyDavid Richerby
70.4k16107196
70.4k16107196
add a comment |
add a comment |
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f106297%2fis-there-a-reasonable-and-studied-concept-of-reduction-between-regular-languages%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$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