# All Questions

44,794 questions
Filter by
Sorted by
Tagged with
6k views

### Are there inherently ambiguous and deterministic context-free languages?

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 ...
1k views

### Equivalence of Büchi automata and linear $\mu$-calculus

It's a known fact that every LTL formula can be expressed by a Büchi $\omega$-automaton. But, apparently, Büchi automata are a more powerful, expressive model. I've heard somewhere that Büchi automata ...
4k views

### Algorithm to test whether a binary tree is a search tree and count complete branches

I need to create a recursive 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) ...
3k views

### Recursive definitions over an inductive type with nested components

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 ...
9k views

### Clock synchronization in a network with asymmetric delays

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 ...
397 views

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 \... 10 votes 0 answers 129 views ### Applying the graph mining algorithm Leap Search in an unlabeled setting 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 ... 22 votes 1 answer 1k views ### Natural candidates for the hierarchy inside NPI Let's assume that$\mathsf{P} \neq \mathsf{NP}$.$\mathsf{NPI}$is the class of problems in$\mathsf{NP}$which are neither in$\mathsf{P}$nor in$\mathsf{NP}$-hard. You can find a list of problems ... 15 votes 2 answers 3k views ### Time spent on requirement and its effect on project success and development time 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 ... 24 votes 2 answers 331 views ### Is Smoothed Analysis used outside academia? 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? 11 votes 2 answers 628 views ### Which kind of branch prediction is more important? 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 ... 13 votes 2 answers 5k views ### Random Sudoku generator I want to generate a completely random Sudoku. Define a Sudoku grid as a$9\times9$grid of integers between$1$and$9$where some elements can be omitted. A grid is a valid puzzle if there is a ... 30 votes 2 answers 749 views ### Characterization of lambda-terms that have union types 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{\... 99 votes 3 answers 32k views ### How does one know which notation of time complexity analysis to use? In most introductory algorithm classes, notations like O (Big O) and \Theta are introduced, and a student would typically learn to use one of these to find the time complexity. However, there are ... 74 votes 1 answer 14k views ### Language theoretic comparison of LL and LR grammars 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 ... 31 votes 1 answer 2k views ### Rice's theorem for non-semantic properties 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 ... 18 votes 3 answers 2k views ### Clever memory management with constant time operations? 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 ... 11 votes 4 answers 26k views ### Evaluating the average time complexity of a given bubblesort algorithm. Considering this pseudo-code of a bubblesort: ... 35 votes 9 answers 4k views ### What is the significance of context-sensitive (Type 1) languages? Seeing that in the Chomsky Hierarchy Type 3 languages can be recognised by a state machine with no external memory (i.e., a finite automaton), Type 2 by a state machine with a single stack (i.e. a ... 30 votes 7 answers 14k views ### Generating Combinations from a set of pairs without repetition of elements I have a set of pairs. Each pair is of the form (x,y) such that x,y belong to integers from the range [0,n). So, if the n is 4, then I have the following pairs: <... 15 votes 2 answers 348 views ### Which method is preferred for storing large geometric objects in a quadtree? When placing geometric objects in a quadtree (or octree), you can place objects that are larger than a single node in a few ways: Placing the object's reference in every leaf for which it is ... 19 votes 4 answers 2k views ### Does cooperative scheduling suspend processes when they perform an I/O operation? Many operating systems references say that with cooperative (as opposed to preemptive) multitasking, a process keeps the CPU until it explicitly voluntarily suspends itself. If a running process ... 368 votes 12 answers 339k views ### Why is quicksort better than other sorting algorithms in practice? In a standard algorithms course we are taught that quicksort is O(n \log n) on average and O(n^2) in the worst case. At the same time, other sorting algorithms are studied which are O(n \log n) ... 19 votes 2 answers 1k views ### Does the 'difference' operation add expressiveness to a query language that already includes 'join'? The set difference operator (e.g., EXCEPT in some SQL variants) is one of the many fundamental operators of relational algebra. However, there are some databases ... 10 votes 1 answer 857 views ### Algorithm to translate a deterministic Büchi automaton to LTL (when possible) Linear temporal logic and deterministic Büchi automata are incomparable: DBA cannot express FGa, and LTL cannot express "at least each odd letter is 'a'". But sometimes it is interesting to know ... 12 votes 3 answers 11k views ### All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete? My book states this If a decision problem B is in P and A reduces to B, then decision problem A is in P. A decision problem B is NP-complete if B is in NP and for every problem in A in ... 16 votes 1 answer 137 views ### Methods to evaluate a system of written rules I was trying to come up with a system that would evaluate bylaws for an organization as to determine their underlying logic. I think a first-order predicate system would work for representing the ... 7 votes 1 answer 672 views ### How to convert a non-embedding context free grammar to regular grammar? A context-free grammar is said to be self-embedding if and only if contains a derivation of the form \xi\stackrel*\Rightarrow u\xi v, where \xi is a non-terminal and u, v are some non-empty ... 6 votes 3 answers 3k views ### Closure of Deterministic context-free languages under prefix For a formal language L \subseteq \Sigma^{*} I define the set Pref(L) to be: \text{pref}(L) = \{\alpha \in \Sigma^{*} : \exists \beta \in \Sigma^{*} \text{ such that } \alpha \beta \in L\} ie. ... 5 votes 1 answer 851 views ### Double-nested loop with bitwise operation I have this little exercise: for ( i = 0; i < 2 * n; i += 2 ) for ( j = 1; j <= n; j <<= 1 ) if ( j & i ) foo (); (... 13 votes 1 answer 7k views ### Is there a context free, non-regular language L, for which L^* is regular? I know that there are non-regular languages, so that L^* is regular, but all examples I can find are context-sensitive but not context free. In case there are none how do you prove it? 21 votes 2 answers 859 views ### Are universal types a sub-type, or special case, of existential types? I would like to know whether a universally-quantified type T_a:$$T_a = \forall X: \left\{ a\in X,f:X→\{T, F\} \right\}$$is a sub-type, or special case, of an existentially-quantified type$T_e$... 8 votes 1 answer 142 views ### Find all the special graphs which can reduced to the shortest paths graph I have a directed weighted graph$G = (V, E, W)$. There is always an edge from a vertex$i$to another one$j$, the weight$w(i,j)$could be positive infinity, and there does not exist any negative ... 20 votes 1 answer 4k views ### Proving that the conversion from CNF to DNF is NP-Hard How can I prove that the conversion from CNF to DNF is NP-Hard? I'm not asking for an answer, just some suggestions about how to go about proving it. 8 votes 1 answer 3k views ### Subset sum, pseudo-polynomial time dynamic programming solution? I found the P vs NP problem some time ago and I have recently worked on the subset sum problem. I have read Wikipedia article on the Subset Sum problem as well as the question Subset Sum Algorithm I ... 25 votes 6 answers 4k views ### Algorithm to solve Turing's "Halting problem‍​" "Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist" Can I find a general algorithm to solve the halting problem for ... 37 votes 2 answers 14k views ### Is there a difference between top-down and bottom-up dynamic programming? Is there a fundamental difference between top-down and bottom-up dynamic programming? In particular, is there a problem which can be solved bottom-up but not top-down? Or is the bottom-up approach ... 7 votes 1 answer 776 views ### Converting a context free grammar to a PDA -- is my solution correct? I'm reviewing for my midterm and wanted to post this to see if anyone can spot any errors. Im supposed to make a PDA that recognizes this CFG:$\qquad\begin{align} S &\to R1R1R1 \\ R &\to ... 1k views

### Compression of domain names

I am curious as to how one might very compactly compress the domain of an arbitrary IDN hostname (as defined by RFC5890) and suspect this could become an interesting challenge. A Unicode host or ...
481 views

### Can you specify a programming language without implementation?

Is it theoretically possible to specify a programming language for which no implementation could exist? A programming language is a way of defining functions. An implementation means a method to ... 503 views

### Decidability of Machines

I cannot understand decidability really well. I have been reading from books and internet, but I am little bit confused. According to the book (as I understood), we can decide on decidability of a ... 3k views

### Unique path in a directed graph

I'm designing an algorithm for a class that will determine if a directed graph is unique with respect to a vertex $v$ such that for any $u \ne v$ there is at most one path from $v$ to $u$. I've ... 240 views

### Can two neighbors in a graph be at the same depth in a DFS tree?

In an undirected graph, can two nodes at an identical distance n from the root of a DFS tree be neighbors in the original graph? I'm thinking no, but I'm not sure (because of back edges)  