# All Questions

9,921 questions
18 views

### Automata as term rewriting systems

It came to my mind that automata (say to start DFA) can be thought as a special kind of rewriting systems. So if one has a word w , one tries to reduce it to the $\epsilon$ word. In other words ...
19 views

### What is the difference between a Top type and a Unit type

Wikipedia defines a Top type: (edited for readability) The Top type [...] is the universal supertype, as all other types in any given type system are subtypes of Top However, the article goes on ...
32 views

### How can we solve the recurrence $T(n) = T(n/2) + log^2(n)$ [on hold]

I am trying to solve the following recurrence: $T(n) = T(n/2) + log^2(n)$ So far I have come up with the following expression $T(n) = \sum^{log(n)}_0 2^klog(n/2^k)$ I cannot figure out a way to ...
19 views

### Prove that language in L

How to prove that $L = \{(\phi,x) | \space Boolean \space formula \space \phi \space is \space true \space on \space a \space set \space of \space x\}$ lies in L?
126 views

### When a type is a value?

In functional programming and in the theoretical setting of the $\lambda$-calculus it is standard to consider a lambda abstraction $\lambda x.M$ as a value. In my understanding, the intuitive reason ...
54 views

### What is the competitive ratio of a $d$-way associative LRU cache?

In a caching problem, items arrive online, and the algorithm needs to decide which elements to keep in the cache. If the current item is not cached, we pay a penalty of $1$. It is well known that for ...
140 views

64 views

### Why can't a left-recursive, non-deterministic, or ambiguous grammar be LL(1)?

I've learned from several sources that an LL(1) grammar is: unambiguous, not left-recursive, and, deterministic (left-factorized). What I can't fully understand is why the above is true for any LL(1)...
74 views

### Prove that if A is NP-complete and B is coNP-complete, than AxB is NP-, coNP-complete

AxB means cartesian product of A and B. May someone help me with this? I even have no idea how to prove that AxB belongs to NP or coNP
430 views

### Feel dissatisfied after each submission

I am a third year graduate student at a "top-20" university who works on fine-grained complexity (lots of playing with 3-SUM, OV and the usual popular hardness conjectures). I have been fairly ...
98 views

### Grid-Minor Theorem of Robertson and Seymour and its Algorithmic Applications

Graph-Minor Theorem of Robertson and Seymour [1] states that if graph G has large treewidth, then it contains a large grid as minor. Most approximation results on general classes of graphs with ...
84 views

### Maximum Weight Independent Set on a Changing Graph?

Suppose I have an optimal solution to the maximum weight independent/stable set problem on an arbitrary graph. If I were to induce a clique among a subset of its vertices (and perhaps add in some ...
48 views

### The definition of weakest precondition for a non-deterministic language

In the classical IMP language, the definition of weakest precondition is: definition "wp c Q s ≡ ∃t. (c,s) ⇒ t ∧ Q t" This is stating that from state s, after ...
99 views

### Strong seeded randomness extractors with low entropy loss

I would like to implement a strong seeded randomness extractor for flat sources as a part of my project. Most of the literature on seeded extractors is concentrated on minimizing seed length. ...
159 views

### What is a good route for a math student to self study computer science systematically and efficiently?

I decided to ask this question after being attracted by how much one can do with the knowledge in computer science, including iOS application development, game(or mods) development, website creating, ...
110 views

### Separating words and graph isomorphism

I wonder if there are any known implications of Babai's recent quasi-polynomial time algorithm for Graph Isomorphism to separating words by DFA's. In both cases the ultimate goal is to differentiate ...
91 views

### Busy Beaver Equivalent for the Untyped Lambda Calculus

In the same way that the Busy Beaver function is defined for Turing Machines, we could define a similar function for the untyped lambda calculus: Over all terms in the ULC composed of ...
39 views

### How to prove that models of indirect and direct RAM machines are equivalent?

as in the title, I am looking for a formal proof how to show that models of indirect and direct RAM (random-access) machines are equivalent. I would really appreciate your help.
151 views

### Hamiltonian cycle vs co-NP [closed]

I am trying to understand co-NP and its implications properly. The French Wikipedia page describing co-NP provides the "complementary" version of the Hamiltonian cycle in co-NP as follows: ...
74 views

### Is it there any cellular automata model of the universe where uncomputable things could happen?

There are several papers that propose that the universe itself is analogous to a cellular automata. Obviously, these papers assume that the universe is computable. But is it there any cosmological ...