Problem Detail: I’ve read first-order logic is in general undecidable, and that could be decidable only when working with unary operators. (I think that’s propositional logic, correct me if I am wrong) The question is why arity leads to undecidable problems? Read More …
Category: Uncategorized
[Solved]: Best starter resources for learning about AI
Problem Detail: I want to start learning of AI and have an idea to program “social evolution simulator” but want to hear any advice to avoid creation “well known bicycles” and get strong knowledge-base. Will be grateful for online resources and/or Read More …
[Solved]: Are syntax and semantic just 2 structures such that one is a model of the other?
Problem Detail: The syntax of a language is a structure. The semantic of a language is a structure. The semantic of a language is a model of its syntax. And that’s all ? The duality syntax/semantic is just model theory Read More …
[Solved]: Show that $0^i$ where $i$ is a power of 2 is not context free
Problem Detail: I’m having difficulty trying to use the pumping lemma in order to show that $L= {0^i mid i text{ is a power of 2 }} $ is not context free. I”m starting by stating that $ s = 0^p$ Read More …
[Solved]: Term for binary search tree using hashes?
Problem Detail: I was looking for a way to easily store and access a symbol table using the least memory and code as possible and I went with a BST. Symbols, however, tend to be defined in order as in foo0, Read More …
[Solved]: How to understand the storing mechanism used in external merge sort
Problem Detail: I was reading about external merge sort from the wikipedia article link, according to it: External sorting is required when the data being sorted do not fit into the main memory of a computing device (usually RAM) and instead Read More …
[Solved]: How to generate graphs with a Hamiltonian path?
Problem Detail: I need to create a graph generator for my next project. Generally algorithms are trying to find a Hamiltonian path in a graph. So I can create a graph generator, generate a graph, and then I can decide whether Read More …
[Solved]: Are $log_{10}(x)$ and $log_2(x)$ in the same big-O class of functions?
Problem Detail: Are $log_{10}(x)$ and $log_{2}(x)$ in the same big-O class of functions? In other words, can one say that $log_{10}(x)=O(log x)$ and $log_{2}(x)=O(log x)$? Asked By : David Faux Answered By : Dave Clarke Yes. Because they differ only by a constant Read More …
[Solved]: Independent set where two vertices need to have distance >= c
Problem Detail: An independent set (IS) in a graph is a set $V’ subseteq V(G)$ of pairwise non-adjacent vertices. I am interested in the generalization $c$-IS where two nodes in $V’ subseteq V(G)$ need to have distance at least $c$ to Read More …
[Solved]: Implications of polynomial time reductions
Problem Detail: I’m reviewing for finals and have a sample problem that I think I understand, but would like someone to bless my understanding or smack me and tell me why I’m wrong. I’m presented with a problem $Pi$ of unknown Read More …
