Computer Science

Q: ML functions from polymorphic lists to polymorphic lists

12:30 AM

0

I'm learning programming in ML (OCaml), and earlier I asked about ML functions of type 'a -> 'b. Now I've been experimenting a bit with functions of type 'a list -> 'b list. There are some obvious simple examples: let rec loop l = loop l let return_empty l = [] let rec loop_if_not_empty = ...

programming-languages typing

2

Q: Not all Red-Black trees are balanced?

Intuitively, "balanced trees" should be trees where left and right sub-trees at each node must have "approximately the same" number of nodes. Of course, when we talk about Red-Black trees being balanced, we actually mean that they are height balanced and in that sense, they are balanced. I hav...

binary-trees

Any idea what quota we are looking to fulfill? We are almost at 100 questions I think it's looking good :)

@sepp2k I asked two questions today to which I already knew the answer. In particular, I figured out the answer to this question myself not too long ago: cs.stackexchange.com/questions/311/…

@sepp2k That might give you some inspiration

@phwd From what I can see, we've had a surge of questions today.

"statistics": [
  {
   "total_questions": 98,
   "total_unanswered": 20,
   "total_accepted": 36,
   "total_answers": 172,
   "total_comments": 769,
   "total_votes": 1719,
   "total_badges": 506,
   "total_users": 197,
   "questions_per_minute": 0.02,
   "answers_per_minute": 0.03,
   "badges_per_minute": 0.03,
   "views_per_day": 919.57,
   "api_version": {
    "version": "1.1",
    "revision": "2012.3.12.1417"
   }

Quite a few people are asking lower-level questions, and we have a number of people who've become more active from what I can see

Looks pretty good to me. I think Movies.SE was only around 500 views per day

12:43 AM

I'm pretty sure there's no particular number we have to shoot for.

We mainly have to consolidate the scope of the site

Have some more people with higher rep (which I think we got today)

Even the unconventional Area 51 stats are looking good

Yup. We could do with some more answered questions, but we had a few very hard questions initially

discussion voting community

I was also wondering whether the CS community would be open to this

39

Q: Vote early, vote often

I would like to echo a post that Scott Morrison made on Tex.SE. I think this is definitely something we are experiencing here on Math.SE. A link to the post here, and the text of the post: "I'm a moderator from MathOverflow, and this "question" is actually unsolicited advice, based on our experi...

In private beta, we set the standards for voting really

At some point, people will have certain 'levels' of vote counts in their heads that represent certain 'levels' of 'goodness'

Such as: <= 2 votes is a meh or niche question, [3, 6] is a reasonable question, [7, 11] is a great question, 12 <= is awesome

Just to give an arbitrary example

Our standards seem to be reasonably high so far, considering the number of users we have

I'm not sure about the meh/niche category. If a question is niche but well presented that should not prevent someone from receiving votes

Kind of a "I am not sure about this niche topic but it sounds rather interesting"

12:52 AM

True, but sometimes it's hard to judge how good a question is if you know nothing of the topic

Some people will think 'this might be a good question, but I can't judge it, let others judge it who can'

Correct, which is the case for me with most of these questions. But from a different perspective, I think of it as reading a new book (when the answer is there of course)

I'll hazard an example: if I asked you to compare the NQLALR(k) class of languages to the LAR(M) class of languages, would that be a good question or not? I don't think many people will even know what I'm talking about, even on this site.

It's nice to hear that you gain something from reading the questions here :)

Yup, it's a slow process, lots of digesting. I need an efficient way to grab answered questions and read it in some sort of article/book format.

I'm off to bed, it's been nice chatting :)

Laters

Q: Why encrypting with the same one-time-pad is not good?

6:59 AM

0

To encrypt a message $m_1$ with a one-time-pad key $k$ you do $Enc(m_1,k) = m_1 \oplus k$. If you use the same $k$ to encrypt a different message $m_2$ you get $Enc(m_2,k) = m_2 \oplus k$, and if you perform Xor of the two ciphertext you get $$( m_1 \oplus k) \oplus ( m_2 \oplus k) = m_1 \oplus...

crypto encryption otp information

0

Q: What is an intuative way to explain De Morgan's Law, and why does De Morgan's law work?

De Morgan's Law is often introduced in an introductory mathematics for computer science course, and I often see it as a way to turn statements from AND to OR by negating terms, is there a more intuitive explanation for why this works rather than just remembering why it works because of truth tabl...

logic discrete-mathematics

I know that happens to be a very basic question

Ran G.

7:10 AM

are you asking for a proof that it works? or just for the intuition? the title is not clear..

intuition mostly

i mean I know the proof works

although another intresting point is that should discrete mathematics by itself be on-topic for this site

Ran G.

@KenLi I totally agree.

as well as logic, (basic) set theory and AI

and other topics that still have no questions asked.

99 questions :) Just popped in to say that. Milestone coming soon \o/

who will have the honor of making the 100th question?

Ran G.

Here's a perfect question for the 100: How to prove <something> using induction, and does it work for the infinite case...

discussion tags policy tagging tag-synonyms

7:15 AM

Definitely not me, I'm off to bed my brain is not in thinking mode right now

CS Meta

7:53 AM

1

Q: Discussions about tags

I suspect we will have to discuss tags and their usage on a regular basis. Let us do so here; I propose one answer per instance and discussion in the comments. Note that you can link to tags using a shortcode. For instance, [tag:context-free] becomes context-free. If you suggest tag wiki entrie...

8:10 AM

well we have the 100th question ^^

Q: Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems?

8:20 AM

2

Most of today's encryption, such as the RSA, relies on the integer factorization, which is not believed to be a NP-hard problem, but it belongs to BQP, which makes it vulnerable to quantum computers. I wonder, why has there not been an encryption algorithm which is based on an known NP-hard probl...

complexity-theory np-hard crypto encryption

CS Meta

0

Q: Proposals for tag synonyms

I can suggest tag synonyms now (and others are soon to follow). Every suggestion will need to be upvoted by at least five users with answer score at least 5 for this tag. This will (as I understand it) automatically retag according to the provided rules. Please suggest synonyms, vote on them and...

discussion tag-synonyms

Q: How to verify number with Bob without Eve knowing?

8:51 AM

3

You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob ...

algorithms crypto

12:57 PM

@AlextenBrink @phwd Interesting discussion about voting, and it should maybe be brought up on Meta. I think voting is important to show (especially new) users their contribution is valued. Wordpress.SE is a good negative example; you hardly get votes even for "perfect" answers. Other sites have crazy high numbers, for instance scifi.SE on some topics.
I think we should encourage people to upvote whenever they see a question that is ontopic and well-posed. Often, you can decide both without being an expert. Downvoting should only happen if the question is not well-posed (imho). In other case…

1:20 PM

I just thought of two more good seeding questions. :) Both were eye-openers for me.

Q: What goes wrong with sums of Landau terms?

0

I wrote $\qquad \displaystyle \sum\limits_{i=1}^n \frac{1}{i} = \sum\limits_{i=1}^n \cal{O}(1) = \cal{O}(n)$ but my friend says this is wrong. From the TCS cheat sheet I know that the sum is also called $H_n$ which has logarithmic growth in $n$. So my bound is not very sharp, but is sufficient ...

asymptotics landau-notation

0

Q: How can it be decidable wether $\pi$ has some sequence of digits?

We were given the following exercise. Let $\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$ Prove that $f$ is computable. How is this possible? As far as I know, we do not know wether $\pi...

undecidability

1:47 PM

hey guys

anyone recently read a poorly written article or paper

btw @Raphael I rolled back to your edit again :P

@Ankit I say your comments. No problem, it took me months to figure out that there is this revision history. ;)

@Ankit All the time, what do you have in mind?

@Raphael What do you mean?

@Ankit if you mouse over chat entries, you get highlighted which other messages they refer to.

ok

@Raphael ok got it

@Raphael I am actually taking a course for which I need examples of text where authors have used too many words to explain or write about something simple

@Ankit Hm. I see badly written papers all the time (TCS Journal) but those papers do not qualify as "simple"

2:03 PM

@Raphael I was actually looking for simple not in the idea or the content but from writing perspective. To be more precise something where the authors got verbose and thereby confused a general computing reader. :P

@Ankit I see. Not, I don't a specific one in mind right now, sorry.

combinatorics binary-trees

2:23 PM

2

Q: Counting binary trees

(I'm a student with some mathematical background and I'd like to know how to count the number of a specific kind of binary trees.) Looking at Wikipedia page for Binary Trees, I've noticed this assertion that the number of rooted binary trees of size $n$ would be this Catalan Number: $$C_n = \dfr...

Q: Languages accepted by modified versions of finite automata

3:24 PM

0

A deterministic finite automaton (DFA) is a state machine model capable of accepting all and only regular languages. DFAs can be (and usually are) defined in such a way that each state must provide some transition for all elements of the input alphabet; in other words, the transition function $\d...

formal-languages automata finite-automata

3:37 PM

Hi!

cs.stackexchange.com/questions/376/… can you please suggest a better title for this question?

'Is this language defined using twin primes regular?'

Fair enough, thanks.

@Daniil This question is equivalent to solving the mentioned conjecture, so what is the point?

@Daniil, I'll give you the answer in a second

It is not, actually.

@AlextenBrink I know the answer :D

3:45 PM

@AlextenBrink "defined using X" is not very descriptive

@Raphael: this question is not at all equivalent to the conjecture, in fact, it's a sneaky question just like the digits of pi question :)

@Raphael the language is regular, you can use the same reasoning as in your question: cs.stackexchange.com/questions/367/…

ah, its regular in both cases

haha

:]

The same idea got you again then Raphael? ;)

3:46 PM

finite or co-finite; standard sneaky trick, actually ;)

@AlextenBrink all the time -.-

but in this case, I was just too fast

Oh dear, they broke their CDN again O.o

CDN?

@Daniil I changed your definition of $L$ syntactically, I hope you don't mind.

Content Distribution Network

Content Delivery Network

whatever

Close enough :P

I just guessed

3:51 PM

dito

@Raphael not at all, I really appreciate your edits

en.wikipedia.org/wiki/Content_delivery_network aha

@Daniil Glad to hear that. :)

And bam, three correct answers :)

Within 3 minutes

Heh.

we seem to have < 10 active users; no questions or answers with more upvotes for some days. :-/ No well-earned badges for our seeding crew.

3:53 PM

I am going to accepts Patrick's answer, since he was the first one and you've got a plenty of rep, @AlextenBrink

Go ahead

Q: Is this language defined using twin primes regular?

3

Let $\qquad L = \{a^n \mid \exists_{p \geq n}\ p\,,\ p+2 \text{ are prime}\}.$ Is $L$ regular? This question looked suspicious at the first glance and I've realized that it is connected with the twin prime conjecture. My problem is that the conjecture has not been resolved yet, so I am not sur...

formal-languages automata regular-languages finite-automata

@Raphael Nah, we have more active users than that, looking at the user list, they just might not all be voting a lot

@AlextenBrink Either way, it is painful to see so many contributions voted up to only 8 or 9.

@Raphael Yes, but I suppose that's the way it is in private beta...

4:01 PM

@AlextenBrink Well, if we have 10+ active users, they should either upvote or express their sentiments. It is important we figure out what a "perfect" question or answer it.

Do you guys follow meta.cs.SE at all?

I do follow it to some extent, however, my time is a lot more limited that I'd like :(

I understand. In a way, meta is even more important than the main site, at least some questions.

I followed the discussions about the level of the questions, but I still want to read the posts Shog9 linked for instance

I do hope to get more time in the future

These questions about different types of automatons are strangely addictive :P

@AlextenBrink True. Maybe because they are grasped so easily but are (potentially) incredibly hard

Pattern languages are another good candidate for such riddles

Ohh, we should have some questions about them!

Q: Which questions can be tagged with "algorithms" tag?

I don't think I've heard of Pattern languages yet

CS Meta

4:21 PM

0

There are two views: Each question in computer science belongs to an area of computer science. Algorithms is one of the main areas, therefore questions in this area (including question which may not directly talk about any algorithms but may be about tools used for analysis of algorithms) can b...

discussion tags

@AlextenBrink Your loss!

The wikipedia article is useless, though

basically, you have variables X and symbols \Sigma. A pattern is some string over X \cup \Sigma. The language generated by a pattern contains exactly the words that are the image of some homomorphism X \to \Sigma^* applied to the pattern.

that's it. The first interesting thing is that is makes a huge difference wether you allow to replace variables with the empty word (as above) or not.

meta.math.stackexchange.com/questions/1088/… - tex support for chat

2

In case anyone is interested

Homomorphism from X to $\Sigma^2$? What algebraic structure is X in that case? A semigroup with concatenation?

4:38 PM

X is just some (infinite) set of variables, no structure at all.

think of them as nonterminals

but all occurrences of the same variable have to be mapped to the some string

uli

I was so waiting for the counting of binary trees question :D

@Daniil Hm, I'll see wether I can make this into a userscript

@uli Hrhr, I thought so.

uli

However, as it happens all the time I was unable to give a short answer. ;)

@uli Good lord no! You could have restricted yourself to one of the four cases, you know... O.o

hmm, from what I have seen so far I guess discrete mathematics is on-topic

4:46 PM

And another automaton type has been analyzed: cs.stackexchange.com/questions/374/…

@Daniil I appreciate your efforts regarding tag wiki. Can you try and be a bit more descriptice? For instance "Computational logic and mathematical logic with applications in computer science." for logic -- the description is somewhat circular

sepp2k

@Raphael Those are strictly less powerful than regular expressions with backreferences, right?

@AlextenBrink you can see those suggestions now, too, right?

@Raphael Yes, I can see tag suggestions now

@sepp2k In other words, they are not Turing complete, no. ;)

@AlextenBrink what are your thoughts on @Daniil's suggestion? Maybe I am too zealous.

4:48 PM

@Raphael Though I'm a bit unsure what to do with them - I haven't had much experience with tags and tag wikis

sepp2k

Regular expressions with backreferences aren't Turing complete.

Let's see

@Raphael Right, I'll try to stick to that, but I can't find a way to describe logic in a couple of sentences.

"Mathematical logic is an area of mathematics dealing with formal reasoning"

"On CS.SE we are primarily interested in computational logic"

Context-free tag suggestion "Questions about CF-languages, that is, languages described by context-free grammars." - I think the tag is not specifically about either languages or grammars?

It isn't? Sorry then

uli

4:52 PM

@Raphael While I was on it I wanted to mention, the rotation correspondence and the lagrange inversion theorem and the true catalan function so the tale grew in the telling :)

@Daniil I'm just guessing - I see that the questions that use the tag are about languages

Finite model theory: "Finite model theory is especially useful in computer science, since we usually deal with finite structures." - as I understand it, the tag wiki excerpt should be a short description what the tag refers to, and stating that the topic is useful does not describe the topic, so I think I

'll reject that one, if Raphael agrees (I'm a bit of a newb with regard to these things)

So are those excerpts being shown on the little blue bubbles when you hover your mouse over the tag?

Because I don't understand how can you fit a full definition in that little window

Yes, I think that's the idea

Aye, that's a hard job :P

I think it's mainly so that people know that the tag doesn't refer to something entirely different that just happens to have the same name

@sepp2k But close? Anyway, pattern language can not describe finite languages, so they are orthogonal to pretty much every other class.

@uli I see.

@AlextenBrink agreed

@Daniil For logic, how about "Formalisation of statements that are either true or false."

5:08 PM

Ah, there are tag wiki excerpts guidelines: blog.stackoverflow.com/2011/03/redesigned-tags-page

@Raphael what about many-valued logic?

Hello Dave

sepp2k

@Raphael There's context free languages that you can't match with regular expressions with backreferences (well-matched parentheses for example, though you can match those if you also allow recursion), so I'd say no. Though it depends on how you define "close" of course.

I think I may have an example that accepts $a^*$

No wait, this doesn't work either

These automatons are so addictive...

Hi. Let me know when you see the light. Your counter-example gives all the information you need. From any state both transitions need to go to a distinct state, but to accept you need to go to the same state.

5:14 PM

I'm starting to get convinced you're right

If you take a transition to an accepting state, the state you came from must have a second transition to a different state, ergo you end in more than one accepting state

So the only languages you'll accept are the two you mentioned

1

Q: Path to formal methods

It is not uncommon to see students starting their PhDs with only a limited background in mathematics and the formal aspects of computer science. Obviously it will be very difficult for such students to become theoretical computer scientists, but it would be good if they could become savvy with us...

formal-methods education

It was a fun question. A race to unravel all of the ingredients.

Yup, quite similar to cs.stackexchange.com/questions/110/…

BTW: who are you working with in Eindhoven?

I'm just a master's student here, so I'm not really working with anyone, though we start doing more and more projects with some of the staff

5:20 PM

OK. That's cool.

Did you have anyone in particular in mind?

I've had courses from people like Jan Friso Groote, Mark van den Brand and others

lucky grad students

Oh, I know a few people there, like Jan Friso Groote, MohammadReza Mousavi, and Wil van de Aalst. And probably a few others just by name. I was at CWI in Amsterdam for a while and crossed paths with a number of these people (and others).

I've had courses from all three :)

Right, I'm off for dinner - thank you for saving me from vainly trying to construct an example of a language that is recognized by type-2 DDFA :)

Me too. A baby awaits at home (probably on the brink of screaming). Dag.

5:29 PM

I would go to grad school as well but I don't really like doing researching, I just like to learn about what we already know in TCS

I off, too. See you!

later

Q: Proving properties of min-heap automata

8:32 PM

1

In a previous question about exotic state machines, Alex ten Brink and Raphael addressed the computational capabilities of a peculiar kind of state machine: min-heap automata. They were able to show that the set of languages accepted by such machines ($HAL$) is neither a subset nor a superset of ...

formal-languages automata

Q: Proving closure under complementation of min-heap automata

9:53 PM

0

In a previous question about exotic state machines, Alex ten Brink and Raphael addressed the computational capabilities of a peculiar kind of state machine: min-heap automata. They were able to show that the set of languages accepted by such machines ($HAL$) is neither a subset nor a superset of ...

formal-languages automata

@Patrick87 Did you consider the slight adaption in heap automata I suggested? (preorder instead of order on heap alphabet, heap stable for symbols with same priority)

Q: Computational power of deterministic versus nondeterministic min-heap automata

10:23 PM

1

In a previous question about exotic state machines, Alex ten Brink and Raphael addressed the computational capabilities of a peculiar kind of state machine: min-heap automata. They were able to show that the set of languages accepted by such machines ($HAL$) is neither a subset nor a superset of ...

formal-languages automata

Patrick87

10:35 PM

@Raphael I have considered it, and agree that it is a natural extension. If you would like to answer any of the second round of questions in that light, I would be very much interested in any results. Indeed, if you think it would be best for me to make clear the two interpretations and settle on one (yours would seem more appropriate, in that case) I would be receptive to that idea.