Timeline for Language equivalence between deterministic and non-deterministic counter net
Current License: CC BY-SA 4.0
55 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Feb 17 at 0:53 | history | suggested | the_tomato | CC BY-SA 4.0 |
Change the title, use latex, correct citation etc.
|
| Feb 17 at 0:53 | review | Suggested edits | |||
| S Feb 17 at 0:53 | |||||
| Aug 4, 2023 at 16:03 | vote | accept | Lionheart | ||
| Aug 4, 2023 at 8:03 | answer | added | Patrick Totzke | timeline score: 5 | |
| S Aug 1, 2023 at 19:01 | history | bounty ended | CommunityBot | ||
| S Aug 1, 2023 at 19:01 | history | notice removed | CommunityBot | ||
| Jul 29, 2023 at 11:54 | comment | added | Joel David Hamkins | Well, I wish you good luck. | |
| S Jul 29, 2023 at 11:15 | history | suggested | Marzio De Biasi | CC BY-SA 4.0 |
made the question more explicit
|
| Jul 29, 2023 at 11:15 | review | Suggested edits | |||
| S Jul 29, 2023 at 11:15 | |||||
| Jul 29, 2023 at 9:33 | comment | added | Lionheart | @JoelDavidHamkins For which A and D are we to answer? -- The A and D are which are I define in my question. I need one answer which explain computably decidable and also decidable. | |
| Jul 29, 2023 at 2:36 | comment | added | Joel David Hamkins | To illustrate what I am talking about, consider the problem of primality testing. The decision problem is: given a number p, decide if it is prime. A 2nd natural question is: what is the computational complexity of primality testing? Notice that these are two different inquiries. One is a scheme of questions about numbers and whether they are prime, and the other asks about the running time of algorithms correctly answering all instances of the 1st problem. You have a similar situation, a decision problem and an inquiry about its complexity, but your posts unfortunately mix these together. | |
| Jul 29, 2023 at 1:32 | comment | added | Joel David Hamkins | The newly edited question seems to be a relatively clear statement of the decision problem that your question is concerned with. But I believe that this is not your actual question. After all, what kind of answer are we to give to the question you have asked? For which A and D are we to answer? Your actual question, I think, is the question whether the decision problem defined by that question is computably decidable. For this reason, unfortunately, the current formulation continues to conflate the decision problem with the question whether it is decidable. | |
| Jul 28, 2023 at 19:39 | comment | added | Lionheart | @JoelDavidHamkins Very helpful! Both of these problems are variants of the determinization problem, which I've already studied (in the paper1 that I mentioned in question).arxiv.org/abs/1404.5157 The problem at hand is: Given an OCN A and a DOCN D, is L(A,0)=L(D,0)? See the updated question. | |
| Jul 28, 2023 at 19:34 | history | edited | Lionheart | CC BY-SA 4.0 |
deleted 177 characters in body
|
| Jul 28, 2023 at 10:17 | history | edited | Lionheart | CC BY-SA 4.0 |
added 10 characters in body
|
| Jul 26, 2023 at 20:27 | history | edited | Lionheart | CC BY-SA 4.0 |
added 10 characters in body
|
| S Jul 24, 2023 at 17:03 | history | bounty started | the_tomato | ||
| S Jul 24, 2023 at 17:03 | history | notice added | the_tomato | Authoritative reference needed | |
| Jul 23, 2023 at 23:13 | comment | added | Joel David Hamkins | It's a little better, but still not there. The key aspect for me is that decidability is ONE question, whereas the decision problem is a scheme of infinitely many questions ranging over all possible inputs. To specify the decidability question is to state explicitly the nature of the input and the desired correct answer. The decidability question is to ask whether there is a computable procedure which answers correctly in all those cases, giving the correct output for any of the allowed given inputs. Decidability is about a uniform computability issue, not a case-by-case computability issue. | |
| Jul 23, 2023 at 23:05 | history | edited | Lionheart | CC BY-SA 4.0 |
added 4 characters in body
|
| Jul 23, 2023 at 22:47 | comment | added | Lionheart | @JoelDavidHamkins I restructured the question. | |
| Jul 23, 2023 at 22:45 | comment | added | Joel David Hamkins | In my view, the question conflates the decision problem with the question whether it is decidable. I had objected to this on the previous version of the question, but this objection was never adequately addressed and is repeated in this question. It may seem a picky point, but in my experience, for sensible discussion one must formulate the decision problem correctly. For any fixed A, D, c, c', the question "is L(A)=L(D)?" as stated by the OP has a Y/N answer—each instance computable by a trivial algorithm. But that isn't what OP wants to know, and so the question has not been properly asked. | |
| Jul 23, 2023 at 22:42 | comment | added | Lionheart | @Carl-FredrikNybergBrodda I have written it mathematically. | |
| Jul 23, 2023 at 22:38 | history | edited | Lionheart | CC BY-SA 4.0 |
added 860 characters in body
|
| Jul 23, 2023 at 20:44 | comment | added | Carl-Fredrik Nyberg Brodda | @AlokMaity This may be a language issue, but saying things like "give me ideas" comes across as quite demanding, and will almost certainly have the opposite effect. If you write a clear, mathematically precise question, then people will engage with your question if they have ideas to give. Otherwise, you may end up with comment chains of 40+ comments (like on your previous question), and having to expend that much time and patience to figure out what you mean (like @ Gro-Tsen has valiantly done!) is very dissuading to anyone who might be able to answer your question. | |
| Jul 23, 2023 at 20:35 | history | edited | Lionheart | CC BY-SA 4.0 |
added 40 characters in body
|
| Jul 23, 2023 at 20:25 | history | undeleted | Lionheart | ||
| Jul 23, 2023 at 19:25 | history | deleted | Lionheart | via Vote | |
| Jul 23, 2023 at 19:24 | history | undeleted | Lionheart | ||
| Jul 23, 2023 at 19:19 | history | deleted | Lionheart | via Vote | |
| Jul 23, 2023 at 19:18 | history | undeleted | Lionheart | ||
| Jul 23, 2023 at 18:37 | history | deleted | Lionheart | via Vote | |
| Jul 23, 2023 at 18:33 | history | undeleted | Lionheart | ||
| Jul 23, 2023 at 18:31 | history | deleted | Lionheart | via Vote | |
| Jul 23, 2023 at 18:30 | comment | added | Gro-Tsen | What I just said is that I don't know and that I suspect that nobody knows. I can't give you ideas. | |
| Jul 23, 2023 at 18:24 | comment | added | Gro-Tsen | I don't know the answer, but I suspect this is an open question, because in the paper “Parametrized Universality Problems for One-Counter Nets” by Almagor, Boker, Hofman and Totzke, at the end of the introduction (“related work”), they state that ①“language inclusion is undecidable for […] OCNs” whereas ②“universality is decidable for the special case of OCNs”: if the answer to your question were known they would surely have mentioned it (as it lies between ① and ②) — since they did not, I suspect it is unknown. | |
| Jul 23, 2023 at 15:40 | comment | added | Lionheart | Yes that's correct. | |
| Jul 23, 2023 at 15:23 | comment | added | Gro-Tsen | First, this is not very important, but when you cite a paper you need to name the authors and the complete title (and ideally the place where published and the date, if published), and link to an official PDF, not to a copy of the PDF on some Google Drive file of yours. Second, and this is more important, it is still not clear where and what the quantifiers are in your question: are you asking whether the question “given $A$ an OCN, $D$ a DOCN, $c$ and $c'$ integers, is $L(A,c) = L(D,c')$?” is decidable? or something else? | |
| Jul 23, 2023 at 13:48 | comment | added | Lionheart | @Gro-Tsen The counter value when for both the machines are accepting the same string should be anything. That's also a difference from weighted automata: it's a Boolean model, either accept or reject. The end counter value is irrelevant. | |
| Jul 23, 2023 at 11:56 | history | edited | Lionheart | CC BY-SA 4.0 |
added 60 characters in body
|
| Jul 23, 2023 at 11:51 | comment | added | Lionheart | @Gro-Tsen in their theorem 6 , in 0-Det,L(A, 0)=L(D, 0), both have inital counter value 0, but in my case counter value 0 or above 0. | |
| Jul 23, 2023 at 9:50 | history | edited | Lionheart |
edited tags
|
|
| S Jul 23, 2023 at 6:07 | history | suggested | the_tomato | CC BY-SA 4.0 |
Make meaning precise
|
| Jul 23, 2023 at 6:07 | review | Suggested edits | |||
| S Jul 23, 2023 at 6:07 | |||||
| Jul 23, 2023 at 0:59 | comment | added | Lionheart | @Gro-Tsen "one-Deterministic Counter Net " Hyperlink is your intended pdf, I already given. And I am not asking theorem 6, I am asking equivalence between deterministic and non-deterministic OCN. I hope you understand me what I actually want from previous question, if you have any doubt regarding question, you are welcome to edit my question. In your previous answer only one mistake i.e. counter issue at every state should be 0 or above 0. | |
| Jul 22, 2023 at 22:07 | comment | added | Gro-Tsen | Additionally, you ought to explain why theorem 6 in the aforementioned paper by Almagor and Yeshurun doesn't answer your question, because as far as I understand it you're asking exactly the question that their theorem 6 answers, so, again, I'm confused! | |
| Jul 22, 2023 at 22:05 | comment | added | Gro-Tsen | In the comments of the previous question, you linked to this paper by Almagor and Yeshurun which is precisely about this sort of questions, so I don't understand why you don't link it here. At the very least, you should imitate their style of writing the definition (and/or the one I had suggested in the previous question) because, once again, what you wrote is more examples than actual definition. | |
| Jul 22, 2023 at 19:13 | history | edited | Lionheart | CC BY-SA 4.0 |
added 369 characters in body
|
| Jul 22, 2023 at 18:51 | history | edited | Lionheart |
edited tags
|
|
| Jul 22, 2023 at 16:59 | history | edited | Lionheart | CC BY-SA 4.0 |
added 31 characters in body
|
| Jul 22, 2023 at 15:30 | history | edited | Lionheart | CC BY-SA 4.0 |
edited title; edited title
|
| Jul 22, 2023 at 15:20 | history | edited | Lionheart | CC BY-SA 4.0 |
deleted 44 characters in body
|
| Jul 22, 2023 at 15:14 | history | edited | Lionheart | CC BY-SA 4.0 |
deleted 2 characters in body
|
| S Jul 22, 2023 at 15:12 | review | First questions | |||
| Jul 22, 2023 at 15:13 | |||||
| S Jul 22, 2023 at 15:12 | history | asked | Lionheart | CC BY-SA 4.0 |