CompSci Weekend SuperThread (November 23, 2018) Computer Science |
- CompSci Weekend SuperThread (November 23, 2018)
- Brzozowski's derivatives and DFA minimization (cross post from r/AskComputer Science)
- CU Majors as Iconic Horror Films
- Why are program refinement methods like Event-B not used more?
- In queueing, how are events commonly managed?
- For a queue with "leaving times", is it better to search unordered leaving times or order the leaving times?
- Coding a morse code application
- Implementing Doppler Effect in C/C++ or Java
| CompSci Weekend SuperThread (November 23, 2018) Posted: 22 Nov 2018 05:05 PM PST /r/compsci strives to be the best online community for computer scientists. We moderate posts to keep things on topic. This Weekend SuperThread provides a discussion area for posts that might be off-topic normally. Anything Goes: post your questions, ideas, requests for help, musings, or whatever comes to mind as comments in this thread. Pointers
Caveats
[link] [comments]  |
| Brzozowski's derivatives and DFA minimization (cross post from r/AskComputer Science) Posted: 22 Nov 2018 07:14 PM PST I haven't gotten any responses at r/AskComputerScience so I decided I'll try here. I'm trying to understand DFA minimization and I've got a difficult time following the papers out there (I don't have a formal education). According to Wikipedia DFA minimisation works by eliminating two things from a DFA, unreachable states, and indistinguishable states. Further, the description Brzozowski's minimisation mentions that the reverse of a DFA can be non-deterministic. I'll reference this later in my question. I've implemented Brzozowski's derivatives working from the Derivatives Reexamined paper by Turon, Reppy, and Owens. As far as I can tell derivatives introduce indistinguishable states and paths which end in non-accepting states. The latter seems to be primarily a consequence of the former. The observations are empirical, based on manually trying different things and "thinking really intensely", so not very rigorous. So to my questions: Is my observation about the derivatives algorithm correct at all? If it is, does that imply that the "unreachable states" mentioned at the start of the post /don't/ get introduced by derivatives, only non-distinguishable states? To clarify, this question is /not/ about the reverse of the DFA since a state that cannot match would be an unreachable state in the reverse automaton. Lastly, are the indistinguishable states the reason why the reverse of the automaton can be non-deterministic? As an aside which should perhaps be a different post, but I'll take a chance here. The derivatives algorithm is a co-inductive algorithm if I understand some of the papers I've read correctly. Further I understand correctly co-inductive algorithms only deal with the /first/ element, which from my observations seems to be the case for both the string /and/ the expression. How would I determine what the "first" element is for the expression? I've been having a fair amount of trouble with this question hence the poor formulation of it. The obvious intuitive answer would simply be the first operator of the expression. However there is quite a lot happening in the delta function which has thwarted my attempts to work out an answer to this question. Anyway, thanks to all who read this, I hope it's not too poorly formulated. [link] [comments]  |
| CU Majors as Iconic Horror Films Posted: 23 Nov 2018 12:27 AM PST |
| Why are program refinement methods like Event-B not used more? Posted: 22 Nov 2018 07:54 AM PST Recently we have been learning about refinement of specifications to programming language code to ensure safety-critical systems are proven to not contain any bugs (we are learning this with Event-B). Yet I was left wondering why these methods are not more common since having a proven working system at any time seems like quite a desirable trait. Is there an inherent trade-off that I'm missing in these systems? [link] [comments]  |
| In queueing, how are events commonly managed? Posted: 22 Nov 2018 06:08 AM PST In queueing, how are events commonly managed? E.g. if one has one client stream and one server. Then suppose the clients are assigned service times. That means that there will be events for "when to release patient i". However, how would one implement this "notification". An external object that keeps track of "events": e.g. tuples (reltime, client), and that checks when reltime is met => sends release client notice. Or e.g., the server has the the info (e.g. (reltime, client)) and there's no separate "commander" object that commands other entities to do the event actions. [link] [comments]  |
| Posted: 22 Nov 2018 04:52 AM PST I'm trying to model a system which has clients that have times that they will stay in the system. E.g. client1 will stay 25 time units in system1. The time units are drawn randomly, so one will get e.g.: client1 25, client2 5, client3 12, client4 30. If I bring these in the "queue" of the system: [client1, client2, client3, client4] then I have times [25, 5, 12, 30]. Now I know that the order of leaving must be client2, client3, client1, client4. But I wonder, whether I should find this out by succesively finding mins of "times" or whether I should order the clients based on order of leave. That is, the system queue would look like: [client2, client3, client1, client4]. I wonder what to do. [link] [comments]  |
| Coding a morse code application Posted: 22 Nov 2018 06:23 AM PST Im about to code a morse code application for fun and i also want to incorporate a database in it to test my skills. Any idea how i can use a database for this sort of application? [link] [comments]  |
| Implementing Doppler Effect in C/C++ or Java Posted: 22 Nov 2018 09:39 AM PST I don't even know where to start, help me a little PS- I know Doppler effect and the languages [link] [comments]  |
| You are subscribed to email updates from Computer Science: Theory and Application. To stop receiving these emails, you may unsubscribe now. | Email delivery powered by Google |
| Google, 1600 Amphitheatre Parkway, Mountain View, CA 94043, United States | |
No comments:
Post a Comment