Is there a reasonable and studied concept of reduction between regular lagnagues?
$begingroup$
Have been any interesting formulations for the concept of reduction between regular langauges, and if yes -- are there regular-complete languages for those reductions?
regular-languages finite-automata
edited 1 min ago
user1767774
1516
asked 2 hours ago
user2304620user2304620
111
New contributor
user2304620 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
Have been any interesting formulations for the concept of reduction between regular langauges, and if yes -- are there regular-complete languages for those reductions?
regular-languages finite-automata
edited 1 min ago
user1767774
1516
asked 2 hours ago
user2304620user2304620
111
New contributor
user2304620 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$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.♦
1 hour ago
$begingroup$
No, just interested if such notions have been studied.
$endgroup$
– user2304620
1 hour ago
$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
1 hour ago
$begingroup$
I have edited the question accordingly.
$endgroup$
– user1767774
1 hour ago
add a comment |
$begingroup$
Have been any interesting formulations for the concept of reduction between regular langauges, and if yes -- are there regular-complete languages for those reductions?
regular-languages finite-automata
edited 1 min ago
user1767774
1516
asked 2 hours ago
user2304620user2304620
111
New contributor
user2304620 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
Have been any interesting formulations for the concept of reduction between regular langauges, and if yes -- are there regular-complete languages for those reductions?
regular-languages finite-automata
regular-languages finite-automata
edited 1 min ago
user1767774
1516
asked 2 hours ago
user2304620user2304620
111
New contributor
user2304620 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 1 min ago
user1767774
1516
asked 2 hours ago
user2304620user2304620
111
New contributor
user2304620 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 1 min ago
user1767774
1516
edited 1 min ago
user1767774
1516
edited 1 min ago
user1767774
1516
1516
asked 2 hours ago
user2304620user2304620
111
New contributor
user2304620 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 2 hours ago
user2304620user2304620
111
asked 2 hours ago
user2304620user2304620
111
111
New contributor
user2304620 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
user2304620 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
user2304620 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$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.♦
1 hour ago
$begingroup$
No, just interested if such notions have been studied.
$endgroup$
– user2304620
1 hour ago
$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
1 hour ago
$begingroup$
I have edited the question accordingly.
$endgroup$
– user1767774
1 hour ago
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.♦
1 hour ago
$begingroup$
No, just interested if such notions have been studied.
$endgroup$
– user2304620
1 hour ago
$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
1 hour ago
$begingroup$
I have edited the question accordingly.
$endgroup$
– user1767774
1 hour ago
$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.♦
1 hour ago
$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.♦
1 hour ago
$begingroup$
No, just interested if such notions have been studied.
$endgroup$
– user2304620
1 hour ago
$begingroup$
No, just interested if such notions have been studied.
$endgroup$
– user2304620
1 hour ago
$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
1 hour ago
$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
1 hour ago
$begingroup$
I have edited the question accordingly.
$endgroup$
– user1767774
1 hour ago
$begingroup$
I have edited the question accordingly.
$endgroup$
– user1767774
1 hour ago
add a comment |
1 Answer
1
active
oldest
votes
$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 1 hour ago
David RicherbyDavid Richerby
69.4k15106195
$endgroup$
$begingroup$
How about local reductions, i.e. NC0 reductions?
$endgroup$
– Yuval Filmus
50 mins ago
add a comment |
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
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
});
}
});
user2304620 is a new contributor. Be nice, and check out our Code of Conduct.
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-lagnagues%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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 1 hour ago
David RicherbyDavid Richerby
69.4k15106195
$endgroup$
$begingroup$
How about local reductions, i.e. NC0 reductions?
$endgroup$
– Yuval Filmus
50 mins ago
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 1 hour ago
David RicherbyDavid Richerby
69.4k15106195
$endgroup$
$begingroup$
How about local reductions, i.e. NC0 reductions?
$endgroup$
– Yuval Filmus
50 mins ago
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 1 hour ago
David RicherbyDavid Richerby
69.4k15106195
$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 1 hour ago
David RicherbyDavid Richerby
69.4k15106195
answered 1 hour ago
David RicherbyDavid Richerby
69.4k15106195
answered 1 hour ago
David RicherbyDavid Richerby
69.4k15106195
answered 1 hour ago
David RicherbyDavid Richerby
69.4k15106195
69.4k15106195
$begingroup$
How about local reductions, i.e. NC0 reductions?
$endgroup$
– Yuval Filmus
50 mins ago
add a comment |
$begingroup$
How about local reductions, i.e. NC0 reductions?
$endgroup$
– Yuval Filmus
50 mins ago
$begingroup$
How about local reductions, i.e. NC0 reductions?
$endgroup$
– Yuval Filmus
50 mins ago
$begingroup$
How about local reductions, i.e. NC0 reductions?
$endgroup$
– Yuval Filmus
50 mins ago
add a comment |
user2304620 is a new contributor. Be nice, and check out our Code of Conduct.
user2304620 is a new contributor. Be nice, and check out our Code of Conduct.
user2304620 is a new contributor. Be nice, and check out our Code of Conduct.
user2304620 is a new contributor. Be nice, and check out our Code of Conduct.
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-lagnagues%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.♦
1 hour ago
$begingroup$
No, just interested if such notions have been studied.
$endgroup$
– user2304620
1 hour ago
$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
1 hour ago
$begingroup$
I have edited the question accordingly.
$endgroup$
– user1767774
1 hour ago