All mathematical questions about computer science, including theoretical computer science, formal methods, verification, and artificial intelligence. For questions about Turing computability, please use the (computability) tag instead. For numerical analysis, use the (numerical-methods) tag. For ...

learn more… | top users | synonyms

0
votes
1answer
46 views

Make individuals distinct

I am trying to construct an ALCQ knowledge base (KB) for some sentences. Here is what I have: Abox (Yiannis is a person and he drinks only one kind of a coffee, frappe): Person(YIANNIS) $\forall$ ...
2
votes
2answers
35 views

Could tertiary computation negate the need for large memory?

In normal computers, pointers in code "point" to memory. On a lower level, linking and loading turns those "pointers" into numerical codes which really do point to specific bytes (or bits) of ...
0
votes
1answer
30 views

Constuct DFA from NFA with multiple epsilons

I need to create a Deterministic Finite Automata(DFA) from a Nondeterministic Finite Automata(NFA). I have created the NFA, however i'm having a hard time understanding the steps needed to turn the ...
0
votes
1answer
87 views

Stronger Pumping Lemma for Context Free Languages

Hi Math Stack Exchange, Taking a class in automata theory, and having real trouble proving the following strong automata theorem for context free languages (from Sipser, Problem 2.37): If L is a ...
0
votes
1answer
30 views

Use unification and resolution to justify proof

Prove: If $\neg A(x)\lor B(y),\neg C(x)\lor G(w),\neg G(x)$, and $A(x)$, then $B(x)\land \neg C(w)$ Use resolution and unification to do your proof. Justify each step. I'm not sure ...
0
votes
1answer
46 views

Random graph problem

I'm trying to analyze a network algorithm to get a latency probability distribution. One of the steps is to "calculate the probability distribution of the number of updated nodes in a single hop of a ...
1
vote
1answer
86 views

Coloring/Labelling problem in Polynomial reduction of Isomorphism

** Question :** Notice the inequality inside yellow box. If $i_1$ has $n$ possible vertex, then $j$ has maximum $(n-1)$ vertices. For $\mu_{i_1,j}$ , it should be $1\leq j \leq (n-1)$ . but it is ...
0
votes
2answers
42 views

How to define numbers in a way that a number 'n' is equivalent to the function plus 'n'?

In lambda calculus, is it possible to define (or disprove the existence of) a number system alternative to church numerals such that each number is a function which on application, adds itself to it's ...
0
votes
2answers
43 views

How do I use integral calculus to estimate a discrete sum?

The Algorithms course I am taking on Coursera does not require discrete math to find discrete sums. Dr. Sedgewick recommends replacing sums with integrals in order to get basic estimates. For ...
0
votes
1answer
12 views

Why is the expected length of a chain in hashing equal to $n/m$ (the load factor) due to independence of collisions?

Say we have inserted $n$ keys and that we have $m$ slots and that the Simple Uniform Hashing Assumption holds (each item to be hashed has an equal probability of being placed into a slot, regardless ...
1
vote
1answer
43 views

MST, Cut in Graph, Some Claims?

I ready for taking a P.hD Entrance Exam. one of old-solution problem of Data Structure is as follows: Which of the following Claims is True about MST of Simple, ...
1
vote
1answer
44 views

Randomized Quick Sort and Partition Probability?

We know about Quick Sort and Randomized Version and Partition. I ran into a Fact when I read my notes. Let $0 < a < 0.5$ be some constant. We have an $n$-element array as input. Randomized ...
1
vote
1answer
67 views

Proof of the PAC generalization error bound using VC dimension

There is a theorem in PAC ("Probably Approximately Correct" model, in computational learning theory) that reads as follows: To guarantee that any hypothesis that perfectly fits the training data ...
0
votes
1answer
48 views

Question on my interpretation of logical notation relating to alphabets, theoretical comp sci.

EDIT: I cross-posted this, and couldn't delete this one as it had some answers. There is a good answer at: http://cs.stackexchange.com/a/53056/46284 $\exists x \in \Sigma^* (t=sx)$ Have I ...
2
votes
1answer
55 views

Is there an hamiltonian path on a $4 \times 4$ chessboard

If you have a $4 \times 4$ chessboard: Is it possible to make a Hamiltonian graph such that each step is like a move of the knight? EDIT: But is an open knight tour? Thus possibly not an Hamiltonian ...
2
votes
1answer
56 views

Shortest Path Via Dynamic Programming Formulation?

We have a directed Graph $G=(V,E)$ with vertex set $V=\left\{ 1,2,...,n\right\}$. weight of each edge $(i,j)$ is shown with $w(i, j)$. if edge $(i,j)$ is not present, set $ w(i,j)= + \infty $. for ...
1
vote
1answer
62 views

Find minimum number of coins with Largest value coins?

There is a greedy algorithm for coin change problem : using most valuable coin as possible. How We can find a quick method to see which of following sets of coin values this algoithms cannot find ...
0
votes
1answer
20 views

Structural Induction with Propositional Variables

I've been stuck on this question and I'm confused as to how to approach it: Let $G$ be a set defined as follows: if $x$ is a propositional variable, then $x \in G$; if $f_1,f_2 \in G$, ...
0
votes
1answer
56 views

Showing set is undecidable with Turing Machines

I'm given the set $T = \{\langle M, w\rangle : M $ is a Turing Machine that accepts $w$ reversed whenever it accepts $w \}$ and I want to show it's undecidable but recognizable. (I'm using the bracket ...
9
votes
1answer
113 views

Mathematics and cinema

I wander if anyone of you have some knowledge about relations between abstract algebra and cinema. I'm not searching for movies about mathematics or algebra; I'm searching for some kind of application ...
0
votes
0answers
19 views

SQL joins and analysis

Say we have a users table and an events table and what sort of analysis can be done? Also, what is some SQL statements to describe the analysis of these 2 tables?
2
votes
2answers
22 views

Comparing the growth of two function by taking logarithms

I was trying to understand how to compare the big-O growth of two functions by taking the logarithm (or some increasing function like $\sqrt{f(n)}$. For example, take $2^{({log_2n})^2}$ vs $ ...
0
votes
1answer
69 views

Using pumping lemma

I'm trying to prove that the language $\mathcal L = \{w \in \{0,1\}^* ∣ w \leq w′ \text{ where }w′ \text{ is any rotation of }w\}$ is not a regular language. Note: The inequality is with respect to ...
1
vote
0answers
23 views

Small tree containing smaller trees

Given $n$, what is the smallest number $N=N(n)$ with the property that there exists a tree on $N$ (unlabelled) vertices that contains a copy of every tree on $n$ vertices? That such $N$ must exist is ...
3
votes
1answer
45 views

Inclusion exclusion principle questions i tried(doing it correct?)

$x_1+x_2+x_3\le10$ how many natural numbers solve this problem if $1\le x_1 \\ 2\le x_2 \\3\le x_3$ What i did: i created $y_1,y_2 , y_3$ so $\\ y_1=x_1-1 \\y_2=x_2-2\\ y_3=x_3 -3$ and then added ...
1
vote
2answers
80 views

Should non mathematicians learn mathematics “just in time” or ahead of time? [closed]

I am wondering how someone that is not exclusively interested in mathematics (but nevertheless aims to become a decent applied mathematician), but for example, a theoretical computer scientist, should ...
0
votes
3answers
45 views

Proving following regular expressions equal to one another?

How would I go about proving the following two regular expressions are equal to one another: $$ ( a + b )^* a ( a + b )^* b( a + b )^* = (a + b)^* ab(a + b)^* $$ I can "see" why they are equal to ...
0
votes
1answer
19 views

Simplify Conjunctive Normal Form?

is there any kind of general rules to follow or algorithm for trying to simplify something in conjunctive normal form? Specifically, I'm trying: (P or Q) and P and (Q or R) and (P or notP or R) and ...
1
vote
2answers
59 views

Is there a way to prove that a Turing machine computes the function we designed it to?

Say we design a simple Turing machine that adds two numbers together. Is there any way to formally prove that the machine actually computes the function we 'know' it does? Is there a general method ...
0
votes
2answers
81 views

Is it possible to have logic without syntax (with only semantic proof methods)?

In one paper I have read a note "Thus, unlike approaches which make use of full first order logic, unprovability of a formulae with respect to a agent specification can be shown by each of two ...
0
votes
1answer
53 views

Convert hexadecimal to binary scientific notation using IEEE 754 single-precision floating point

I am trying to convert these numbers to binary scientific notation, but I cannot figure out the process. Could someone please the process of going about solving this? For IEEE 754 single precision ...
0
votes
2answers
42 views

Whats bigger? lim n->infinity n^x or lim n->infinity x^n

What is bigger? lim n->infinity n^x or lim n->infinity x^n I have a relationship where I am trying to find the lim n->infinity (2^n + n^20) / 3^n and am having a hard time deciphering it.
2
votes
1answer
58 views

Converting programming logic to mathematical notation

How do I go about converting programming logic to mathematic notation? For example, I read a question that asks: ...
1
vote
0answers
49 views

Graphs of (un)bounded color valence

Talking about colored graphs there is a definition given for graphs with bounded color valence. This definition is as follows: A vertex-colored graph $G=(V,E)$ has bounded color valence, if there ...
1
vote
0answers
62 views

How to find $1^k+2^k+…+n^k$?

I know how to come up with $F(n, k) = \sum \limits_{p=1}^n p^k$ recursively knowing $F(n, k-1)$. But what if I want to find it in a very short time? I know how to find fast $f_n = ...
2
votes
1answer
13 views

Savitch theorem and its assumption

famous Savitch theorem states: For any function $f\in\Omega(\log(n)), \text{NSPACE}(f(n)) \subseteq > \text{DSPACE}((f(n))^2).$ Why we need an assumption that $f\in\Omega(\log(n))$? Thank ...
2
votes
0answers
34 views

Are binary bit-strings the most efficient representation of integers?

There is no format more popular in the world than the representation of Integers: 32-bit and 64-bit strings are used by basically every single computer in existence and there's no practical reason to ...
0
votes
1answer
54 views

Find the order of elimination in Josephus Problem

Josephus Problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game. People are standing in a circle waiting to be executed. Counting begins at the first ...
0
votes
0answers
18 views

Hypercontractivity Lemma

In the proof of the Hypercontractivity Lemma here http://www.cs.cmu.edu/~odonnell/boolean-analysis/lecture13.pdf (3.4) what does it mean to split $p$ into $r + x_n*s$, why can we do this?
-1
votes
2answers
44 views

$f(x) \geq g(x) \Leftarrow \lim_{x \rightarrow \infty}\frac{g(x)}{f(x)}=0 $?

I want to know if function $f(x)$ is greater or equal than $g(x)$. If I prove that $\lim_{x \rightarrow \infty}\frac{g(x)}{f(x)}=0$ then is it so?
1
vote
1answer
59 views

Proving L is regular or not using pumping lemma

So I'm trying to prove that the language L = {$1^n$ | n is composite} is either regular or non-regular using the pumping lemma. I wanted to ask if I'm on the right track. So I assume that L is ...
0
votes
1answer
30 views

Geometric Meaning behind the algorithm (slope of the line + ray casting)

I'm trying to dissect the classic algorithm for finding if a point is inside a (simple) polygon. Please see: http://erich.realtimerendering.com/ptinpoly/ and ...
0
votes
0answers
9 views

What is the complexity of the arithmetic operations in base $b$?

Fix a number $n$. We want an algorithm which takes a positive integer $x$, represented as a base $b$ string, and outputs the base $b$ representation of $nx$. Note that if $n$ is a power of $b$, there ...
3
votes
1answer
102 views

The Mathematics of Finite State Automata

I am a final year undergraduate mathematics student preparing to undertake my BSc-HONS project, provisionally titled for the time being, "Finite State Automata and Regular Languages". Having had a ...
1
vote
2answers
27 views

Time Complexity Calculation

I'm currently working a few exam question, and got stuck at this point. I am given that a Quicksort algorithm has a time complexity of $O(nlog(n))$. For a particular input size, the time to sort the ...
0
votes
1answer
49 views

Find the equation of a non-linear relation given 2 points

So I ask my question, let me just begin by stating that I'm in grade 9, and have decided to start learning calculus to aid me in the development of an undisclosed project that I am working on. Now, ...
0
votes
1answer
63 views

Evaluate truth value of formula

I am not sure about this question? Domain = {1, 2} Assignment of constants: a = 1 and b = 2 Assignment of functions: f(1) = 2 and f(2) = 1 Assignment for predicate P: P(1, 1) = T; P(1, 2) = T; ...
0
votes
1answer
80 views

Function such that $f(a, b) = c$, but even if I knew $c$ and $b$ I cannot (practically) find $a$? [closed]

I need a function where $f(a, b) = c$. a,b,c are all positive integers. But even if you knew $b$ and $c$ you cannot practically discover $a$ or narrow $a$ down to fewer than ~1 billion ...
2
votes
2answers
44 views

Solving for the positions of vertices of 3 line segments

I have 3 line segments of lengths p,q,r joined at their ends. Let's call the vertices A, B, C, and D. Suppose D is fixed at the origin. Suppose that A is constrained to move only in the Y direction. ...
0
votes
1answer
18 views

an array A[1..N] how many indexes (i,j) are there such that cumulative sum(i,j)%K = 0?

Lets say I have an array A[x1,x2,x3,...xN] of size N. for N = 4 , A = {x1,x2,x3,x4}. [1 based index] Now,I have to tell how many tuples (i,j) are there such that i<=j and cumulative sum(i,j) is ...