Timeline for Deciding homomorphic images of De Bruijn graphs
Current License: CC BY-SA 4.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 12 at 16:41 | answer | added | Miroslav Olšák | timeline score: 2 | |
| Nov 9, 2023 at 18:34 | vote | accept | Sam van G | ||
| S Aug 14, 2023 at 13:52 | history | suggested | Jules Lamers | CC BY-SA 4.0 |
corrected spelling, see https://en.wikipedia.org/wiki/Dutch_name#Tussenvoegsels
|
| Aug 14, 2023 at 12:40 | review | Suggested edits | |||
| S Aug 14, 2023 at 13:52 | |||||
| Aug 14, 2023 at 9:44 | answer | added | no_hurry | timeline score: 4 | |
| Aug 12, 2023 at 11:04 | comment | added | Carl-Fredrik Nyberg Brodda | @SamvanG No problem. And of course -- welcome to MO, Sam, it's nice to see you here! :) | |
| Aug 12, 2023 at 10:43 | comment | added | Sam van G | Thank you very much for this reference, Carl-Fredrik. It does look relevant and related, not sure how to use it yet. | |
| Aug 12, 2023 at 7:41 | comment | added | Carl-Fredrik Nyberg Brodda | Only somewhat related, but counting the number of homomorphic images of de Bruijn graphs is a very difficult problem (see §6 of arXiv:2004.08478). Perhaps some useful ideas can be found in there. | |
| Aug 12, 2023 at 7:10 | history | edited | Sam van G | CC BY-SA 4.0 |
added 2 characters in body
|
| Aug 12, 2023 at 5:12 | answer | added | Ville Salo | timeline score: 6 | |
| Aug 11, 2023 at 18:50 | answer | added | 1001 | timeline score: 8 | |
| Aug 11, 2023 at 17:08 | comment | added | Ville Salo | My first guess is that this is decidable, with a "first periodic and aperiodic points, then transitions" type argument, similar to the proofs of the factor/embedding theorems (of symbolic dynamics). | |
| Aug 11, 2023 at 15:36 | history | edited | Sam van G | CC BY-SA 4.0 |
added 555 characters in body; edited tags
|
| Aug 11, 2023 at 15:06 | comment | added | Sam van G | Thanks, you're right, I added "and "no" otherwise" just to be sure... | |
| Aug 11, 2023 at 15:06 | history | edited | Sam van G | CC BY-SA 4.0 |
added 20 characters in body
|
| Aug 11, 2023 at 15:04 | comment | added | Joel David Hamkins | Your "that is" statement of decidability is incorrect, since you only state the positive requirement. This defines semi-decidability, and indeed your problem is semi-decidable, since we can just search for an $n$ and say Yes when (and if) we find one for which there is a homomorphism using that $B_n$. This will fulfill your "that is" statement, and shows that the problem is computably enumerable (semi-decidable). But decidability should also mean that you say No if and only if there is no such homomorphism. That is, you want the decision procedure to terminate with Yes or No in finite time. | |
| S Aug 11, 2023 at 14:45 | review | First questions | |||
| Aug 11, 2023 at 14:52 | |||||
| S Aug 11, 2023 at 14:45 | history | asked | Sam van G | CC BY-SA 4.0 |