All Questions

Filter by
Sorted by
Tagged with
39 votes
2 answers
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 ...
user avatar
  • 12.6k
32 votes
2 answers
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 ...
user avatar
  • 2,147
10 votes
3 answers
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) ...
user avatar
22 votes
2 answers
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 ...
user avatar
39 votes
6 answers
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 ...
user avatar
23 votes
1 answer
397 views

Is there any nongeneral CFG parsing algorithm that recognises EPAL?

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 \...
user avatar
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 ...
user avatar
  • 320
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 ...
user avatar
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 ...
user avatar
  • 3,008
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?
user avatar
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 ...
user avatar
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 ...
user avatar
  • 263
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{\...
user avatar
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 ...
user avatar
  • 1,293
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 ...
user avatar
  • 71k
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 ...
user avatar
  • 21.7k
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 ...
user avatar
11 votes
4 answers
26k views

Evaluating the average time complexity of a given bubblesort algorithm.

Considering this pseudo-code of a bubblesort: ...
user avatar
  • 561
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 ...
user avatar
  • 1,735
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: <...
user avatar
  • 1,287
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 ...
user avatar
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 ...
user avatar
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)$ ...
user avatar
  • 5,325
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 ...
user avatar
  • 3,008
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 ...
user avatar
  • 1,016
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 ...
user avatar
  • 233
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 ...
user avatar
  • 561
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 ...
user avatar
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. ...
user avatar
  • 1,131
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 (); (...
user avatar
  • 151
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?
user avatar
  • 583
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$ ...
user avatar
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 ...
user avatar
  • 237
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.
user avatar
  • 301
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
23 votes
1 answer
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 ...
user avatar
  • 339
11 votes
4 answers
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 ...
user avatar
5 votes
1 answer
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 ...
user avatar
9 votes
3 answers
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 ...
user avatar
6 votes
3 answers
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)
user avatar
9 votes
1 answer
417 views

Euler cycles in biconnected components

If a graph has a Euler cycle, do the biconnected components have Euler cycles as well?
user avatar

15 30 50 per page
1
892 893 894 895
896