All Questions
47,703
questions
20
votes
3
answers
347
views
Extension of SQL capturing $\mathsf{P}$
According to Immerman, the complexity class associated with SQL queries is exactly the class of safe queries in $\mathsf{Q(FO(COUNT))}$ (first-order queries plus counting operator): SQL captures safe ...
- 22.2k
7
votes
1
answer
458
views
Analyzing load balancing schemes to minimize overall execution time
Suppose that a certain parallel application uses a master-slave design to process a large number of workloads. Each workload takes some number of cycles to complete; the number of cycles any given ...
- 12.8k
26
votes
3
answers
3k
views
What are the conditions for a NFA for its equivalent DFA to be maximal in size?
We know that DFAs are equivalent to NFAs in expressiveness power; there is also a known algorithm for converting NFAs to DFAs (unfortunately I do now know the inventor of that algorithm), which in ...
- 2,167
29
votes
3
answers
2k
views
Do subqueries add expressive power to SQL queries?
Does SQL need subqueries?
Imagine a sufficiently generalized implementation of the structured query language for relation databases. Since the structure of the canonical SQL ...
- 12.8k
55
votes
2
answers
7k
views
How to define quantum Turing machines?
In quantum computation, what is the equivalent model of a Turing machine?
It is quite clear to me how quantum circuits can be constructed out of quantum gates, but how can we define a quantum Turing ...
- 20.6k
8
votes
1
answer
1k
views
What Is The Complexity of Implementing a Particle Filter?
In a video discussing the merits of particle filters for localization, it was implied that there is some ambiguity about the complexity cost of particle filter implementations. Is this correct? ...
- 303
23
votes
1
answer
2k
views
How fundamental are matroids and greedoids in algorithm design?
Initially, matroids were introduced to generalize the notions of linear independence of a collection of subsets $E$ over some ground set $I$. Certain problems that contain this structure permit greedy ...
- 3,857
34
votes
2
answers
3k
views
Are there improvements on Dana Angluin's algorithm for learning regular sets
In her 1987 seminal paper Dana Angluin presents a polynomial time algorithm for learning a DFA from membership queries and theory queries (counterexamples to a proposed DFA).
She shows that if you are ...
- 4,812
44
votes
2
answers
2k
views
Determining capabilities of a min-heap (or other exotic) state machines
See the end of this post for some clarification on the definition(s) of min-heap automata.
One can imagine using a variety of data structures for storing information for use by state machines. For ...
- 12.8k
40
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.8k
33
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,167
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
23
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
10k
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
417
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 \...
- 9,036
10
votes
0
answers
133
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
23
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,417
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,078
24
votes
2
answers
338
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
659
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
822
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{\...
101
votes
3
answers
34k
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,323
76
votes
1
answer
15k
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 ...
- 72k
32
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 ...
- 22.2k
19
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,470
11
votes
4
answers
27k
views
Evaluating the average time complexity of a given bubblesort algorithm.
Considering this pseudo-code of a bubblesort:
...
- 571
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,755
31
votes
7
answers
15k
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,327
15
votes
2
answers
385
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,548
383
votes
12
answers
346k
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,505
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,078
10
votes
1
answer
886
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,055
12
votes
3
answers
12k
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
141
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
690
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,141
5
votes
1
answer
876
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
914
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
146
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
38
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 ...
- 783
7
votes
1
answer
801
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
24
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 ...
- 349
11
votes
4
answers
570
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
587
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