Questions about methods and techniques for proving theorems.

learn more… | top users | synonyms

-1
votes
1answer
30 views

In what context does “definition” arise? [closed]

If I am correct, the concept of a "theorem" doesn't appear until the concept of a formal system is introduced. "Definition" is used more often than "theorem" is. So I wonder if the concept of ...
0
votes
0answers
20 views

How to guess solutions for “divide and conquer” type of recurrences? [duplicate]

I am trying to solve "divide and conquer" recurrence relations of the type $T(n) = a T(n/b) + f(n)$ using the Substitution/Inductive Methods ( NOT the Master Theorem ). Every site I see on the web ...
1
vote
1answer
61 views

Prove that an $n$-length string has $2^n$ i18n-style abbreviations

An i18n-style abbreviation is one in which multiple letters are shortened to that number of letters. E.g., "internationalization" -> "i18n" ("nternationalizatio" is substituted with its length 18). ...
1
vote
2answers
53 views

Proof of an Optimal substructure in Dynammic Programming?

Could someone please explain how exactly the proof of optimal substructure property in dynamic programing problems works?, they usually say that " let's say the global optimal solution is A, and B is ...
0
votes
1answer
67 views

A DFA recognizing my name

How can I know if my DFA is implemented correctly? For example, I need to build a DFA, and then minimize it which will recognize my name. Language which describe my name is: L = {pustai, marius} I ...
0
votes
1answer
104 views

Concept used in the proof [closed]

In the paper "Resolution for Quantified Boolean Formulas", I am unable to understand the proof of theorem 3.4. Please help me with the basic concept used on page 4: The concept that I am referring ...
3
votes
2answers
105 views

Need Help Reducing Subset Sum to Show a Problem is NP-Complete

I want to show that the following problem is NP-Complete: For a set of vectors $v_1,\ldots,v_n \in \mathbb{N}^d$ and an integer $k$, does there exist a subset $S \subseteq \{v_1,\ldots,v_n\}$, such ...
1
vote
2answers
64 views

if (dis)proving a conjecture on graph theory can be done just by a counter example then can every (dis)proof be mapped actually to a counter-example?

Suppose we have a conjecture on graph theory that can be (dis)proved by means of a counter example, then, is it true that every alternative (dis)proof of the conjecture can be mapped to a counter ...
2
votes
1answer
37 views

Is proof of totality of a semantic function for binary numbers cicular?

I think the following proof found in a textbook is circular, since the proof for case n=n'0 assumes the case n=n'1 and vice versa. Am I missing something? Proof that the semantic function N is a ...
0
votes
1answer
52 views

Prove that a proof system is not complete

I want to prove that the proof system A is not complete. A consists of these axioms: ...
1
vote
1answer
318 views

Correctness of proof by induction

Suppose a person states the following: $n^2 = (n * n), \forall n > 0$. One can check such equality by saying, via proof by induction, that: for $n := 0:\ 0^2 = (0 * 0)$; for $n := 1:\ 1^2 = (1 * ...
3
votes
4answers
867 views

How to prove that problem is not in P

Given some abstract problem how can I prove that this problem is not in P. I mean, what is the method for proving such thesis?
1
vote
0answers
16 views

How does supercompilers relate to macro tree transducers?

Supercompilers can be used as a generalisation of deforestation of a functional program. Macro Tree Transducers composition can be used to the same effect, using a completely different approach. What ...
2
votes
1answer
43 views

Choose $n/2$ vertices and guarantee $3/4$ of edges are accounted for proof

Give a polynomial-time algorithm that finds ceil(V/2) vertices that collectively account for at least three-fourths (3/4) of the edges in an arbitrary undirected graph. The algorithm I have come up ...
4
votes
1answer
34 views

Should we not reuse constants in tableaux proofs?

I am trying to understand the proof of the following using tableaux: $$ \exists x\forall y.r(x,y) \to \forall x \exists y . r(x,y) $$ This is how it works out: $$ (1) \space \exists x \forall y ...
0
votes
1answer
34 views

How does one figure out where a class of languages falls under some complexity class? [closed]

I was wondering how can someone prove that one class of languages is of a certain complexity? For example, how could I show the Turing-recognizable languages are in P? Would I have to come up with ...
-1
votes
1answer
72 views

induction proof for kleene star

i posted this on mathematics stack exchange here before i realised this one existed. i am going through some past exam paper questions on regular languages for some revision, and i am having a bit of ...
1
vote
1answer
68 views

Proving that a language does not belong to a language class by using more specific instances of that language

You have a description of a language that you have to prove is regular, context free, or other. In order to prove that it does not belong to a certain class of languages, you might think that it will ...
1
vote
1answer
58 views

Prove not context free

How can we prove that: $$ L = \{ w_1\#w_2 \mid w_1 \in w_2;\; |w_2| > |w_1|;\; w_1 , w_2 \in \{0, 1\}^*\} $$ is not context-free? The language defines $w_1$ as a sub-string of $w_2$, and they ...
0
votes
1answer
31 views

Finding a finite model

Hello I am having difficulty with this question, I am not even sure what strategy one would go about proving something like this: Suppose $L$ is a language which includes an infinite list ...
3
votes
1answer
30 views

LK-$\phi$ proof of $\exists y Pby$

I am having difficulty with the concept of $LK-\Phi$ proofs, here is a question I have been working on: Let $\Phi = \{Pafa\}$, where $P$ is a binary predicate symbol and $f$ is a unary function ...
35
votes
2answers
2k views

Is there a system behind the magic of algorithm analysis?

There are lots of algorithm-analysis questions around. Many are similar, for instance those asking for an analysis of nested loops or divide & conquer algorithms, but most answers seem to be ...
3
votes
2answers
58 views

Constructively deciding whether a decidable predicate holds universally

I am trying to obtain the proof of the proposition: $(\forall x \in \mathbb{N}, P(x)) \vee (\neg \forall x, P(x))$ given that the property $P$ is decidable for every $x \in \mathbb{N}$, i.e. ...
0
votes
1answer
14 views

How to prove the following properties of Small-step semantics?

I have to prove the following 2 properties of the Small-step semantics of the WHILE programming language: If $\langle C_1; C_2, s\rangle \rightarrow^k s'$ then there is a state $s''$ and natural ...
1
vote
3answers
237 views

How to find whether a grammar's language is finite or infinite?

I have this context-free grammar and I want to find out whether its language is finite or infinite. ...
2
votes
1answer
56 views

Proving that the continuation of a non-regular language is not ω-regular

I want to prove that a language is not $\omega$-regular. The language I'm working with can be defined as: $$L = \{ a_1 \dots a_n x^\omega ~ | ~ n > 0, a_1 \dots a_n \in L^\prime \}$$ where ...
1
vote
4answers
96 views

How can I prove $P \rightarrow (Q \rightarrow R)$ is equivalent to $(P \wedge Q) \rightarrow R$

I'm a freshman CS student at my university and i'm struggling with understanding my professor through his thick accent. I've asked him to explain the proof for this multiple times and still have ...
3
votes
1answer
54 views

Polynomial Reduction 3SAT to K-Clique

I am reading the reduction given by Sipser in his textbook "Introduction to the Theory of Computation," on page 303. The reduction is: \begin{equation} 3SAT \leq_p KCLIQUE \end{equation} I am really ...
7
votes
0answers
99 views

Proof of PCP theorem

I am reading the proof of PCP theorem in Proof Verication and Hardness of Approximation Problems. The following paragraph appears in section 3 (page 4), "Outline of the Proof of the Main Theorem". ...
3
votes
0answers
36 views

What are methods for showing that concurrent objects are not linearizable?

Linearizability is a well-known correctness condition for concurrent objects. It provides the illusion that each operation applied by concurrent processes takes effect instantaneously at some point ...
-1
votes
2answers
71 views

Induction proof, base case not working but induction step works? [closed]

$1+3+5+...+(2n+3)=n^2+4n$ For this series using induction proof. Base case 1,2,3,.. not working. But induction step works well. Base case is not given in question.
2
votes
0answers
39 views

Proof of contention of the wait-free consensus algorithm

I know that this is a known theorem but I can't find its proof. The theorem is: The write-contention of any $n$-process wait-free consensus algorithm (implemented from any read-modify-write ...
2
votes
2answers
123 views

How to apply the substitution method to n/2?

I recently was introduced to solving recurrence bounds by substitution but there's something i don't understand about it. In standard induction proofs you prove a base case, assume it holds for n ...
4
votes
0answers
29 views

What are the properties of the unsided fold?

Foldl and folr are 2 very important functions for FP and Haskell, but I have never heard much about the unsided fold: fold f [a,b,c,d] = (f (f a b) (f c d)) That ...
1
vote
0answers
45 views

Equivalency of two pushdown automata

How would one go about proving that one PDA that may only pop one symbol from its stack per transition, is equivalent to a second PDA that is allowed to pop any number of symbols? That is a PDA with ...
3
votes
1answer
152 views

Euclidean Algorithm in Coq

Question How do I write more intuitive proofs of the two following results in Coq? ...
7
votes
2answers
268 views

How to prove that a language is context-free?

There are many techniques to prove that a language is not context-free, but how do I prove that a language is context-free? What techniques are there to prove this? Obviously, one way is to exhibit ...
-1
votes
2answers
59 views

BST Successor Proof

I'm studying for my CS final and I can't seem to get the anywhere with one of the questions. This is the question: Prove that if a node in a BST has a successor, but has no right child, then its ...
2
votes
1answer
96 views

How to prove that the minimum square partition of a 3X2 rectangle has 3 squares

This question is motivated by an older question about tiling an orthogonal polygon with squares.         Given a $3\times 2$ rectangle like the first image, the ...
1
vote
1answer
113 views

Is my proof for a context free language correct? Same number of a's as b's

I have the following grammar G: $$ \begin{align*} &S \to aB|bA \\ &A \to a|aS|bAA \\ &B \to b|bS|aBB \end{align*} $$ I am going to prove that this language L(G) consists of words with the ...
0
votes
1answer
71 views

What is wrong in this proof? [closed]

I stumbled upon this wikipage that has got this proof : I rechecked sum rule of differentiation. And i can not understand where is this wrong. Any Tips ? I think that the second line x^2 = x + ...
1
vote
1answer
64 views

Prove language is not regular? [duplicate]

I know how to use the pumping lemma to do so, but I don't think that can be used for this language: $$L = \{x \in \{0,1\}^* : \text{no prefix of $x$ has more $1$'s than $0$'s}\}. $$ What other ...
2
votes
1answer
87 views

Recommendations for machine learning book?

I am a microbiologist and I am currently self-studying machine learning from some open lecture videos. I am finding it pretty difficult to understand proofs that are somewhat "obvious", my poor ...
3
votes
2answers
429 views

Proof that there is unambigous grammar for every regular language

How can I prove, or where can I find proof that for every regular language there is unambigous grammar?
0
votes
1answer
72 views

Reference for an undecidability proof [duplicate]

I'm searching for a reference of an undecidability proof that is as simple as possible and starts "from scratch". With "from scratch" I mean that it does not use some other undecidable problem to ...
0
votes
1answer
69 views

trouble with bijection definition [closed]

I have a bijection problem that I cannot get my head around. It goes like this: let f: A -> B and g: B -> C be functions such that g o f is a bijection. Prove that f must be one-to-one and that g ...
3
votes
0answers
53 views

How to prove that the composite strategy is prefix-closed and respects the alternation condition?

I'm doing some research on game semantics using these notes. Currently I'm trying to prove that the definition of composite-strategy is indeed a strategy. I have already proved all the conditions of ...
1
vote
1answer
372 views

Proving the language $L= \{0^n 1^m \space | \space m \equiv 0 \space mod \space n, \space n \geq 2 \}$ is not regular using the pumping lemma

I am trying to learn about applying the pumping lemma and I'm not really sure how to go about proving this language isn't regular with the pumping lemma: $L= \{0^n 1^m \space | \space m \equiv 0 ...
1
vote
1answer
44 views

Help with recurrence solutions

We started learning recurrences and I am having trouble with some of the problems. Our professor is having us substitute in $n=2^m$ and $S(m)=T(2^m)$ then writing down equations and summing them all ...
5
votes
3answers
126 views

Is it possible to prove thread safety?

Given a program consisting of variables and instructions which modify these variables, and a synchronization primitive (a monitor, mutex, java's synchronized or C#'s lock), is it possible to prove ...