Author: ignougroup

Problem Detail: The ABD algorithm in paper: Sharing Memory Robustly in Message-Passing Systems can emulate single-writer multi-reader atomic registers in message-passing systems, in the presence of processor or link failures. Looking into the details of this algorithm (in Figure 2, page Read More …

Problem Detail: There’s a lot of debate about what exactly the Church-Turing thesis is, but roughly it’s the argument that “undecidable” should be considered equivalent to “undecidable by a universal turing machine.” I’m wondering if there’s an analogous statement for time Read More …

Problem Detail: Given: $T(n) = T(sqrt{n}) + 1$ (base case $T(x) = 1$ for $x<=2$) How do you solve such a recurrence? Asked By : ajmartin Answered By : ajmartin For the recurrence, $$ T(n) = T(sqrt{n}) + 1 $$ Let $n = Read More …

Problem Detail: Specifications in Kripke structures are verified by Computation tree logic (CTL). However, refering to this Wikipedia article the CTL-operators are relative to a current state. So, when we want to verify if EF q is satisfied in a Kripke Read More …

Problem Detail: Some sorting algorithms like counting sort/insertion sort can work in $O(n)$ time while other algorithms such as quicksort require $O(n log n)$ time. As I understand it, it’s not always possible to use the $O(n)$ sorting algorithms. What are Read More …

Problem Detail: I have been studying Artificial Intelligence and I have noticed that the Bayes’ rule allows us to infer the posterior probability if a variable. But, my question is, what does the word, or phrase, ‘posterior’ mean in this context Read More …

Problem Detail: In proofs of decidability, we often want to simulate another model of computation by a Turing machine. But if I can simulate a $mathsf{DFA}$ by, say, a C program, then is there some result which says that the $mathsf{DFA}$ Read More …

Problem Detail: Is developing an optical character recognition system for an alphabet which has no previous ocr considered a reputable conference or journal worthy research project, given the fact that there are so many commercial ocr system? Though, lots of conference Read More …

Problem Detail: For 2D polygonal meshes, the QuadEdge and HalfEdge data structure representations are sufficient to store and enable efficient query of all topological and incidence information. Are there compact and efficient data structures for 3D polyhedral meshes? I know there Read More …

Problem Detail: The following equation is a matrix expression where $B_i$ and $C_i^T$ are $ntimes n$ matrices and k is a positive integer: $$P = sum_{i=1}^k B_i C_i^T $$ So $P = B_1 C_1^T + B_2 C_2^T + cdots +B_k C_k^T Read More …