Seeing that in the Chomsky Hierarchy Type 3 languages can be recognised by a DFA (which has no stacks), Type 2 by a DFA with one stack (i.e. a push-down automaton) and Type 0 by a DFA with two stacks (i.e. with one queue, i.e. with a tape, i.e. by a Turing Machine), how do Type 1 languages fit in...

Considering this pseudo-code of an bubblesort: FOR i := 0 TO arraylength(list) STEP 1 switched := false FOR j := 0 TO arraylength(list)-(i+1) STEP 1 IF list[j] > list[j + 1] THEN switch(list,j,j+1) switched := true ENDIF NEXT IF switch...

Let's consider a memory segment (whose size can grow or shrink, like a file, when needed) on which you can perform two basic memory allocation operations involving fixed size blocks: allocation of one block freeing a previously allocated block which is not used anymore. Also, as a requiremen...

Rice's theorem tell us that the only semantic properties of Turing Machines (i.e. the properties of the function computed by the machine) that we can decide are the two trivial properties (i.e. always true and always false). But there are other properties of Turing Machines that are not decidabl...

People often say that LR(k) parsers are more powerful than LL(k) parsers. These statements are vague most of the time; in particular, should we compare the classes for a fixed $k$ or the union over all $k$? So how is the situation really? In particular, I am interested in how LL(*) fits in. As f...

Since the current FAQs say this site is for students as well as professionals, what will the policy on homework be? What are the guidelines that a homework question should follow if it is to be asked? I know on math.se they loosely require that the student make an attempt to solve the question a...

I really like the new beta theme, I guess it is much more attractive to newcomers than the sketchy one (which I also liked). Thanks a lot! However I'm slightly embarrassed because I can't read what I type, both in the title and in the body of a post. I never encountered the problem on other Stac...

This discussion started in my other question "Will Homework Questions Be Allowed?". Should we allow the tag? It seems that some of our sister sites (Programmers, stackoverflow) have not allowed the tag as it isn't constructive to their sites. But other sites (Physics, Mathematics) do allow the s...

I know we have some very useful ones on cstheory.SE and I have seen some amusing ones on Stackoverflow. On other sites such as scifi.SE they seem to be banned. What is our stand?

There have been many questions on CST that were either closed, or just not answered because they weren't considered research level. May those questions (as long as they are of good quality) be reposted or moved here? I have a particular example question in mind: http://cstheory.stackexchange.com...

Ok, so in most introductory Algorithm classes, either BigO or BigTheta notation are introduced, and a student would typically learn to use one of these to find the time complexity. However, there are other notations, such as BigOmega and SmallOmega. Are there any specific scenarios where one not...

Many textbooks cover intersection types in the lambda-calculus. The typing rules for intersection can be defined as follows (on top of the simply typed lambda-calculus with subtyping): $$ \dfrac{\Gamma \vdash M : T_1 \quad \Gamma \vdash M : T_2} {\Gamma \vdash M : T_1 \wedge T_2} ...

I expect to see pseudo code and maybe even HPL code on regular basis. I think syntax highlighting would be a great thing to have. On Stackoverflow, code is highlighted nicely; the schema used is inferred from the respective question's tags. This won't work for us, I think, because we probably wo...

Sudoku generation is hard enough. It is much harder when you have to make an application that makes a completely random Sudoku. The goal is to make a completely random Sudoku in Objective-C (C is welcome). This Sudoku generator must be easily modified, and must support the standard 9x9 Sudoku, a...

I have observed that there are two different types of states in branch prediction. In superscalar execution, where the branch prediction is very important, and it is mainly in execution delay rather than fetch delay. In the instruction pipeline, where the fetching is more problem since the inst...

What should we do about programming questions like this one? Are they on-topic or should they be closed (or migrated to SO)?

Did the smoothed analysis find its way into main stream analysis of algorithms? Is it common for algorithm designers to apply smoothed analysis to their algorithms?

Is there any evidence suggesting that time spent on writing up, or thinking about the requirements will have any effect on the development time? Study done by Standish (1995) suggests that incomplete requirements partially (13.1%) contributed to the failure of the projects. Are there any studies ...

What is an efficient algorithm to find the least common multiple of two numbers?

NPI is the class of NP problems without any polynomial time algorithms and not known to be NP-hard. I'm interested in problems such that a candidate problem in NPI is reducible to it but it is not known to be NP-hard and there is no known reduction from it to the NPI problem. Are there any known ...

I am reading Mining Significant Graph Patterns by Leap Search (Yan et al., 2008), and I am unclear on how their technique translates to the unlabeled setting, since $p$ and $q$ (the frequency functions for positive and negative examples, respectively) are omnipresent. On page 436 however, the au...

This is my first time to be involved in a site beta, and I would like to gauge the community's opinion on this subject. On StackOverflow (and possibly Math.SE), questions on introductory formal language and automata theory pop up... questions along the lines of "How do I show language L is/isn't...

This is my first time to be involved in a site beta, and I would like to gauge the community's opinion on this subject. Certainly, there are many kinds of questions which we could expect to (eventually) be asked on CS.SE; lots of candidates were proposed during the lead-up to the Beta, and a few...

This is somewhat related to this discussion, but different enough to deserve its own thread, I think. What would be the site policy regarding questions that are generally considered "easy", but may be asked during the first semester of studying computer science. Example: "How do I get the symme...

The question came up: Are questions about Software Engineering ontopic?

How should we behave and what behaviour should we encourage during beta specifically in order to make our site successful?

EPAL, the language of even palindromes, is defined as the language generated by the following unambiguous context-free grammar: $S \rightarrow a a$ $S \rightarrow b b$ $S \rightarrow a S a$ $S \rightarrow b S b$ EPAL is the 'bane' of many parsing algorithms: I have yet to enc...

Assume a computer has a precise clock which is not initialized. That is, the time on the computer's clock is the real time plus some constant offset. The computer has a network connection and we want to use that connection to determine the constant offset $B$. The simple method is that the compu...

Consider an inductive type which has some recursive occurrences in a nested, but strictly positive location. For example, trees with finite branching with nodes using a generic list data structure to store the children. Inductive LTree : Set := Node : list LTree -> LTree. The naive way of d...

I was editing a question and I was about to tag it bubblesort, but it occurred to me that tag might be too specific. I almost tagged it sorting but its only connection to sorting is that the algorithm happens to be a type of sort, it's not about sorting per se. So should we tag questions on a pa...

To what extent are questions about proof assistants on-topic? I see four main classes of questions: Modeling a problem in a formal setting; going from the object of study to the definitions and theorems. Proving theorems in a way that can be automated in the chosen formal setting. Writing a co...

Should topics in applied CS be on topic? These are not really considered part of TCS, examples include: Computer architecture (Operating system, Compiler design, Programming language design) Software engineering Artificial intelligence Computer graphics Computer security Source: http://en.wik...

I have an assignment for my data structures class. I need to create an algorithm to see if a binary tree is a binary search tree as well as count how many complete branches are there (a parent node with both left and right children nodes) with an assumed global counting variable. So far I have ...

It's a known fact that every LTL formula can be expressed by a Buchi $\omega$-automata. But, apparently, Buchi automata is a more powerful, expressive model. I've heard somewhere that Buchi automata are equivalent to linear-time $\mu$-calculus (that is, $\mu$-calculus with usual fixpoints and onl...

Let us call a context-free language deterministic if and only if it can be accepted by a deterministic push-down automaton, and nondeterministic otherwise. Let us call a context-free language inherently ambiguous if and only if all context-free grammars which generate the language are ambiguous,...

One can imagine using a variety of data structures for storing information for use by state machines. For instance, push-down automata store information in a stack, and Turing machines use a tape. State machines using queues, and ones using two multiple stacks or tapes, have been shown to be equi...

What will the policy on providing code be? In my question it was commented that it might not be on topic as it seemes like I was asking for working code. I wrote my algorithm in pseudo-code because my problem didnt ask for working C++ or whatever language. Should we only allow pseudo-code here?...