Is there a reasonable and studied concept of reduction between regular languages?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
Where would I need my direct neural interface to be implanted?
How to install cross-compiler on Ubuntu 18.04?
What are the G forces leaving Earth orbit?
Expand and Contract
Is it possible to map the firing of neurons in the human brain so as to stimulate artificial memories in someone else?
My ex-girlfriend uses my Apple ID to log in to her iPad. Do I have to give her my Apple ID password to reset it?
Why is the sentence "Das ist eine Nase" correct?
Venezuelan girlfriend wants to travel the USA to be with me. What is the process?
Getting extremely large arrows with tikzcd
Description list Formatting using enumitem
Rotate ASCII Art by 45 Degrees
How exploitable/balanced is this homebrew spell: Spell Permanency?
Do Iron Man suits sport waste management systems?
How do conventional missiles fly?
What Exploit Are These User Agents Trying to Use?
Is there an online compendium of Rav Moshe teshuvos in English that exists?
Should I tell management that I intend to leave due to bad software development practices?
Am I breaking OOP practice with this architecture?
What reasons are there for a Capitalist to oppose a 100% inheritance tax?
Bullying boss launched a smear campaign and made me unemployable
meaning of 腰を落としている
Theorists sure want true answers to this!
Why were 5.25" floppy drives cheaper than 8"?
Car headlights in a world without electricity
Is there a reasonable and studied concept of reduction between regular languages?
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 2 days ago
David Richerby
69.5k15106195
asked 2 days ago
user2304620user2304620
312
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 so -- are there regular-complete languages under those reductions?
regular-languages finite-automata
edited 2 days ago
David Richerby
69.5k15106195
asked 2 days ago
user2304620user2304620
312
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.♦
2 days ago
$begingroup$
No, just interested if such notions have been studied.
$endgroup$
– user2304620
2 days 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
2 days ago
$begingroup$
I have edited the question accordingly.
$endgroup$
– user1767774
2 days ago
$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
2 days ago
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 2 days ago
David Richerby
69.5k15106195
asked 2 days ago
user2304620user2304620
312
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 so -- are there regular-complete languages under those reductions?
regular-languages finite-automata
regular-languages finite-automata
edited 2 days ago
David Richerby
69.5k15106195
asked 2 days ago
user2304620user2304620
312
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 2 days ago
David Richerby
69.5k15106195
asked 2 days ago
user2304620user2304620
312
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 2 days ago
David Richerby
69.5k15106195
edited 2 days ago
David Richerby
69.5k15106195
edited 2 days ago
David Richerby
69.5k15106195
69.5k15106195
asked 2 days ago
user2304620user2304620
312
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 days ago
user2304620user2304620
312
asked 2 days ago
user2304620user2304620
312
312
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.♦
2 days ago
$begingroup$
No, just interested if such notions have been studied.
$endgroup$
– user2304620
2 days 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
2 days ago
$begingroup$
I have edited the question accordingly.
$endgroup$
– user1767774
2 days ago
$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
2 days 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.♦
2 days ago
$begingroup$
No, just interested if such notions have been studied.
$endgroup$
– user2304620
2 days 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
2 days ago
$begingroup$
I have edited the question accordingly.
$endgroup$
– user1767774
2 days ago
$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
2 days 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.♦
2 days 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.♦
2 days ago
$begingroup$
No, just interested if such notions have been studied.
$endgroup$
– user2304620
2 days ago
$begingroup$
No, just interested if such notions have been studied.
$endgroup$
– user2304620
2 days 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
2 days 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
2 days ago
$begingroup$
I have edited the question accordingly.
$endgroup$
– user1767774
2 days ago
$begingroup$
I have edited the question accordingly.
$endgroup$
– user1767774
2 days ago
$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
2 days ago
$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
2 days ago
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 2 days ago
Yuval FilmusYuval Filmus
195k15184349
$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 2 days ago
David RicherbyDavid Richerby
69.5k15106195
$endgroup$
add a comment |
Your Answer
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-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 2 days ago
Yuval FilmusYuval Filmus
195k15184349
$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 2 days ago
Yuval FilmusYuval Filmus
195k15184349
$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 2 days ago
Yuval FilmusYuval Filmus
195k15184349
$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 2 days ago
Yuval FilmusYuval Filmus
195k15184349
answered 2 days ago
Yuval FilmusYuval Filmus
195k15184349
answered 2 days ago
Yuval FilmusYuval Filmus
195k15184349
answered 2 days ago
Yuval FilmusYuval Filmus
195k15184349
195k15184349
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 2 days ago
David RicherbyDavid Richerby
69.5k15106195
$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 2 days ago
David RicherbyDavid Richerby
69.5k15106195
$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 2 days ago
David RicherbyDavid Richerby
69.5k15106195
$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 2 days ago
David RicherbyDavid Richerby
69.5k15106195
answered 2 days ago
David RicherbyDavid Richerby
69.5k15106195
answered 2 days ago
David RicherbyDavid Richerby
69.5k15106195
answered 2 days ago
David RicherbyDavid Richerby
69.5k15106195
69.5k15106195
add a comment |
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-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.♦
2 days ago
$begingroup$
No, just interested if such notions have been studied.
$endgroup$
– user2304620
2 days 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
2 days ago
$begingroup$
I have edited the question accordingly.
$endgroup$
– user1767774
2 days ago
$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
2 days ago