All Questions
44,794
questions
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 ...
- 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 ...
- 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) ...
- 435
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 ...
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 ...
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 \...
- 8,956
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 ...
- 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 ...
- 4,313
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 ...
- 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?
user20
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 ...
user123
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 ...
- 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{\...
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 ...
- 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 ...
- 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 ...
- 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 ...
- 1,450
11
votes
4
answers
26k
views
Evaluating the average time complexity of a given bubblesort algorithm.
Considering this pseudo-code of a bubblesort:
...
- 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 ...
- 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:
<...
- 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 ...
- 251
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 ...
- 1,536
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)$ ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
dalibocai
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. ...
- 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 ();
(...
- 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?
- 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$ ...
stakx
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 ...
- 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.
- 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 ...
user1094566
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 ...
user11775
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 ...
- 773
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 ...
jfisk
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 ...
- 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 ...
meisam
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 ...
Marigi Maskere
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 ...
el diablo
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)
el diablo
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?
el diablo