Computer Science

Excavator

 Excavator
Edit first post that was inactive for 6 months.
Awarded 489 times.
Can any computably enumerable set be generated by a prefix-free set?
Awarded 2 days ago
Show that $L = \{1^n w 1^n | n > 0 \text{ and } w ∈ \{0,1\}^*\}$ is regular
Awarded Jun 15 at 4:27
Are LR(k) languages and DCFLs equivalent?
Awarded Jun 9 at 5:27
CFG that generates $1^*$ is decidable
Awarded Jun 3 at 5:10
Without Rare Metals
Awarded Jun 2 at 4:15
Circuits for Modular Arithmetic
Awarded May 30 at 4:04
How to generate, validate, and invalidate a set/list of numbers in O(1) time and space?
Awarded May 26 at 4:35
Is there a complexity metric for finite state machines?
Awarded May 26 at 4:35
Does two languages being in P imply reduction to each other?
Awarded May 21 at 4:21
Find a weighted median for unsorted array in linear time
Awarded May 17 at 4:31
Proving that recursively enumerable languages are closed against taking prefixes
Awarded May 15 at 4:45
How can there be undecidable languages in P/1?
Awarded Apr 28 at 4:07
Solving $T(n) = 3T(\frac{n}{3})+\sqrt{n}$ using master method
Awarded Apr 23 at 4:26
NFA with exponential number of states when determinized
Awarded Apr 22 at 6:14
There are pretty much no algorithms in P
Awarded Apr 22 at 6:14
Floyd's Cycle detection algorithm | Determining the starting point of cycle
Awarded Apr 20 at 8:53
Existence of non-context free but decidable languages
Awarded Apr 20 at 8:53
Half-SAT intractability proof
Awarded Apr 16 at 5:42
What is the definition of P, NP, NP-complete and NP-hard?
Awarded Apr 10 at 5:12
Proving that the shortest simple path problem between two vertices $s$ and $t$ in a graph is NP-complete
Awarded Apr 7 at 5:47
What is a forwarding pointer? [closed]
Awarded Apr 5 at 4:06
Which research languages have a stronger typesystem than Haskell and why?
Awarded Mar 22 at 5:25
(post deleted or otherwise unavailable)
Awarded Mar 21 at 4:08
Why are so many internet protocols text-based?
Awarded Mar 19 at 4:32
Checking equality of integers: O(1) in C but O(log n) in Python 3?
Awarded Mar 13 at 4:26
Minimum number of processes for the deadlock?
Awarded Mar 5 at 6:51
Why are CFLs not closed under intersection?
Awarded Mar 3 at 4:56
Instruction Set Architecture (ISA) design
Awarded Mar 1 at 5:33
Can I simplify log(n+1) before showing that it is in O(log n)?
Awarded Feb 26 at 4:15
Is a balanced binary tree a complete binary tree?
Awarded Feb 22 at 4:17
Is “super-exponential” a precise definition of algorithmic complexity?
Awarded Feb 20 at 6:33
What's the difference between a stream and a queue?
Awarded Feb 18 at 4:20
Difference between Turing machine and Universal Turing machine
Awarded Feb 17 at 5:49
A reference for pseudocode for Monge-Elkan algorithm?
Awarded Jan 31 at 5:01
What is decider?
Awarded Jan 28 at 4:21
Finding Permutations with Exclusions
Awarded Jan 21 at 4:40
Solving the min edge cover using the maximum matching algorithm
Awarded Jan 19 at 5:21
Showing that deciding whether a given TM accepts a word of length 5 is undecidable
Awarded Jan 15 at 5:05
Understanding a paper on polynomial recursion in all finite types
Awarded Jan 7 at 4:52
Is the set of strings with equal number of 010’s and 101’s regular?
Awarded Jan 6 at 19:52
Dijkstra without decrease key
Awarded Dec 31 '20 at 4:37
Non-deterministic Büchi vs Rabin: Automaton size for LTL->automaton
Awarded Dec 30 '20 at 4:12
Algorithm to check whether a complete, undirected graph is fullfilling the triangle inequality
Awarded Dec 28 '20 at 4:16
Graphs that cause DFS and BFS to process nodes in the exact same order
Awarded Dec 28 '20 at 4:16
Is a Turing Machine “by definition” the most powerful machine?
Awarded Dec 21 '20 at 6:34
Are expert systems outdated, what are better alternatives to them, if any?
Awarded Dec 17 '20 at 4:48
A variant of travel salesman problem in grid graph
Awarded Dec 8 '20 at 4:55
How to prove the optimization version problem (whose decision version is NP-complete) can be solved in poly-time iff P=NP?
Awarded Nov 23 '20 at 4:05
Where does entanglement fit into quantum computing?
Awarded Nov 13 '20 at 6:50
Why is the Mersenne Twister regarded as good?
Awarded Nov 1 '20 at 4:33
Why does every member $f(n) \in \Theta(g(n))$, and $g(n)$ have to be asymptotically non-negative?
Awarded Oct 29 '20 at 6:16
Why is every finite language A ⊆ Σ* regular
Awarded Oct 29 '20 at 6:16
Example of two undecidable languages that cannot be mapping reduced to each other
Awarded Oct 29 '20 at 6:16
Checking if there is a single path that visits all nodes in a directed graph
Awarded Oct 23 '20 at 5:48
If the Halting Problem was solvable, and we solved it, what would be its implications?
Awarded Oct 23 '20 at 5:48
How to prove greedy algorithm is correct
Awarded Oct 17 '20 at 4:34
Counting the number of words accepted by an acyclic NFA
Awarded Oct 10 '20 at 4:56
Algorithm for checking if all subarrays have an unique element
Awarded Oct 7 '20 at 5:34
Decidability of dependent typing on primitive recursive languages
Awarded Sep 17 '20 at 5:37
Demonstrating that for every monotonic grammar there is an equivalent context-sensitive grammar
Awarded Sep 5 '20 at 4:41
1
2 3 4 5
…
9

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.