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

1
vote
1answer
23 views

Alphabet on homomorphism

So I am trying to learn for an exam, and I found an exercise but without solutions and I can't really get behind the topic: Let $G = (V,E)$ be a connected graph with $v \geq 2$ Vertices. $P(G)$ is ...
2
votes
2answers
36 views

How to evaluate this infinite series arising from a CS problem? [duplicate]

$$\sum_{i=1}^{\infty}i\cdot((1-\frac{1}{N!})^{i-1}\cdot\frac{1}{N!})$$ where N is an integer and $N \geq 2$? I obtained this series from the following problem: Given a sequence of $N > 2$ unique ...
1
vote
2answers
17 views

Growth function and one misunderstanding point?!

I have a question about Growth and Asymptotic notation topic. My question is as follows: $2^n$ > $n^{log_2{(n)}}$ is True. anyone could say how we can deduce that this fact is true?
0
votes
1answer
23 views

Big O notation for summation function

May be I am missing something very simple but I am finding it hard to understand why Big O for summation is O(n^2). I know that Big O for summation comes from fact that sum(1 to n) = n(n+1)/2. But if ...
0
votes
0answers
21 views

Explaining something in Kraft-McMilan inequality proof

I was asked to present the Kraft-McMillan inequality, but I have trouble in understanding why in the following segment of the proof: there is a $$k\ge0 $$such that: $$ a^{-l_1}+a^{-l_2}+.....+(k+1)a^{...
3
votes
4answers
70 views

Does this thing I'm calling 'the operationalization of $x$' have an accepted name?

Given a set $X$ and an element $x \in X$, we can turn $x$ into a function denoted $\tilde{x}$ as follows: for any set $Y$ and any function $f : X \rightarrow Y$, define $$\tilde{x}(f) = f(x).$$ For ...
0
votes
1answer
17 views

Is there any approach to computer vision that doesn't make use of geometry?

I've long been interested in applying my background in functional analysis (especially wavelets) and other related areas to actually create something with "real world" value (not that I don't enjoy ...
0
votes
1answer
22 views

is this k-SAT or 3-SAT reduction?

On introduction to the theory of computation - 2nd edition by Michael Sipser, there's this question with the solution: Question: "7.31: In the following solitaire game, you are given an m x m board. ...
1
vote
1answer
40 views

pumping lemma - choice of partition

there is some thing in pumping lemma that I don't understand it. I think about application to prove irregularity of language. We have for each word (actual length) find partition: $xyz$ such that $\...
0
votes
0answers
19 views

3d pattern matching for object recognition? [on hold]

How do i measure the similarities between two set of 3d points made by group of points in 3d? Is their any mathematical equation? In keypoint detection i get set of keypoints from 3d point cloud, now ...
0
votes
0answers
20 views

Henkin theory follow complete

Assume that Γ is a a Henkin theory. For any two constants c,d, either $\Gamma \vdash c=d$ or $\Gamma \vdash c \neq d$. There are two constants a,b such that $\Gamma \vdash a\neq b$.Show that Γ is a ...
0
votes
1answer
24 views

Which one of the following is true of this relation?

Consider the set of A all the people who are living down Italy."x lives in the same house as y" is a relation on the set A.Consider the following properties of a relation on a set: a)Symmetric b)...
1
vote
1answer
85 views

Contradiction in Davis–Putnam–Logemann–Loveland (DPLL) Method?!

As we see on page $10,11$ and $12$ on Google Books we know about Unit Clause (UC) and Pure Literal (PL) in DPLL Algorithms. in the following example if assign value $0$ to variables is prior to ...
0
votes
0answers
9 views

Change In Time from Bidirectional Turing Machine to Standard Turing Machine

I'm reading this book on Computational Complexity and on page 37, it has a proof that a bidirectional TM $M$ running in $T(n)$ time can be converted to a unidirectional TM $\widetilde M$ running $4T(n)...
1
vote
1answer
28 views

Proving that $A+B - (A \cap B) = A \cup B$ for binary integers

I hope computing questions are fine here. I'm trying to show that for all binary numbers $A$ and $B$, $A+B - (A \cap B) = A \cup B$. It's confusing me firstly because I'm not sure what the "set ...
0
votes
1answer
13 views

How can I show a set B with 8 elements and two operations (huntington axioms)

How can I show a set B with 8 elements and two operations, such that the axioms of huntington for boolean algebra holds? I found it with set of 2 elemtnts. but can't understand how to start with 8 ...
-1
votes
0answers
33 views

i dont understand how theorem calculation proofs work please help [closed]

I do not understand hilbert style proofs and how they work. Can someone please explain them to me? some things i need to know are: • Write theorem-calculations from Γ (equivalently, Γ−...
0
votes
1answer
37 views

Help in proving inequalities in information theory-Kraft-McMillan

I was given a task of proving some inequalities that are related to Kraft-McMillan's inequalities, and i have been scratching my head for quite some time trying to prove it: $$ F(x)= \frac{1}{1-Q(x) }...
0
votes
0answers
18 views

Defining the right number of columns for a website interface

While working on a website interface (I'm a web developer), I came across an interesting problem. 1/ SOME DEFINITIONS In web design, for maintaining a coherent flow of the different elements of the ...
1
vote
1answer
24 views

Floating point numbers

In a certain computer represents numbers in base2, if the distance between 7 and the next largest floating-point number is $2^{-12}$. What is the distance between 70 and the next largest floating ...
0
votes
0answers
16 views

Primitive recursive function, constructing a proof

I've came upon an example in the book that is not that clear to me. The disparity function is proved to be primitive recursive in the following way: $$disparity(x_0,x_1)=(x_0-x_1)-(x_1-x_0) = add(...
0
votes
0answers
29 views

Negative representation of a binary number

I saw online that if you want to convert a binary number to a negative binary number, you add 1.However, I don't understand why you do that.In a forum I saw someone explaining the following: ...
0
votes
1answer
36 views
+50

A question about many-one reducibility of two sets

We want to show that $ \big\{x:W_{x}$ is finite }$=Fin \leq _m Cof=\big\{x : W_{x}$ is cofinite}. But I really have not any idea. Would be grateful for your help.
0
votes
1answer
34 views

comparing two strings with Turing Machine

Reading about Multitape Turing Machines and coming across this exercise: Construct a Turing Machine, that can "tell" if a word w1 on strip 1 matches w2 on strip 2. Given approach : Compare the states ...
0
votes
0answers
31 views

How to show that a function is primitive recursive?

If we have a function $g ~:~ \mathbb{N}^{k+1} \rightarrow \mathbb{N}$ which is primitive-recursive. How to show that the function $f ~:~ \mathbb{N}^{k+1} \rightarrow \mathbb{N} $ with $f(x_1, ~...~, ...
11
votes
4answers
1k views

How many bit strings of length 8 start with “1” or end with “01”?

A bit string is a finite sequence of the numbers $0$ and $1$. Suppose we have a bit string of length $8$ that starts with a $1$ or ends with an $01$, how many total possible bit strings do we have? I ...
0
votes
1answer
18 views

the set of extendable p.c. functions is not N

Show that the set $Ext:= \big\{x\in N : \varphi_{x}$ is extendable to a total recursive function $\big\}$ is not equal to the set of non negative integers $N$. Would be grateful for your help.
0
votes
1answer
32 views

Why This alternative way for retrieving the Original number from 2'S complement number works?

I was reading a book to learn about conversion from 2'S complement number to origianl binary number. During my past college study, I learened the following method for retrieving the Original number ...
0
votes
2answers
66 views

Turing Machine halts for at least $1024$ strings as input [closed]

Consider the language $$L = \{\text{"}M\text{"} \mid \text{Turing Machine } M \text{ halts for at least }1024\text{ input-strings}\}.$$ Is L a recursively enumerable language? My answer is no based ...
-1
votes
1answer
47 views

Iterate through integers solutions of linear inqualities [closed]

Say we have a set of integers value $x_1,\ldots x_n$ such that $$ \left\{ \begin{array}{l} a_{1,1} x_1 + \ldots a_{1,n}x_n \leq b_1 \\ \vdots \\ a_{m,1} x_1 + \ldots a_{m,n} x_n \leq b_m \\ x_1, \...
0
votes
1answer
54 views

Turing Machine & Recursively enumerable languages. [closed]

Suppose Turing Machine(TM) M and language L. L = { "M" | M has as input strings which $∈$ $\{0,1\}^{*}$ and terminate at a maximum of $512^{512}$ steps} Is L a recursively enumerable language?
2
votes
1answer
52 views

Hamiltonian circuit in at least one component

I'm having trouble proving that the problem stated in the title is NP-complete, specifically by reduction from Hamiltonian circuit. Intuitively it's clear - Hamiltonian circuit in one graph is NP-...
0
votes
0answers
15 views

Prove that reverse of regular L is also regular [duplicate]

Prove that reverse of regular language is also regular. I know, how i can to this by using DFA of L. Changing directions of edges and so on. But how can it be done with Structural induction? What ...
-1
votes
1answer
42 views

Time complexity (in Θ –notation) in terms of n [closed]

I am struggling quite a bit trying to solve these and any help would be greatly appreciated. a) ...
0
votes
0answers
26 views

Given an array $A$ of length $N<10^6,$ how many subarrays have $\text{max}(A[x:y]) - \text{min}(A[x:y]) {\le} K$?

Given any K and an array of length $N$ what is the most efficient way to find the number of unique subarrays that satisfy this constraint? I believe there is an $O(N)$ solution using monotonic queues ...
0
votes
1answer
41 views

Not sure about Turing machine

Not quite sure, if I understand Turing machine correctly. So I tried building one, which should give back the predecessor of a number in binary code. e.g. 111 -Turing-> 110 picture of turing m. If ...
0
votes
2answers
54 views

Is there an way to calculate the value of O(n) [closed]

Is there an way to calculate the value of O(n) (Big Oh)? I understand it's use in algorithm. But my question is how is the value calculated?
0
votes
0answers
32 views

Modified version of SubsetSum

Let $L=\{(y_1,...,y_n,S,p)\ |\ \exists I\subset[n]\ s.t. \ |I|=p.\ \sum_{i\in I}y_i=S\}$. and $\forall\ 1\leq i\leq n\ :y_i \text{ is a positive integer}$, Assuming $\mathcal{P}\neq\mathcal{NP}$. ...
1
vote
1answer
29 views

What does it mean to say that an automaton construction is “effective”?

Let $L, K \subseteq X^{\ast}$ be languages, then we set $$ K^{-1}L := \{ u \in X^{\ast} \mid vu \in L \mbox{ for some } v \in K \} = \bigcup_{v\in K} v^{-1}L $$ with $u^{-1}L := \{ w \in X^{...
2
votes
0answers
58 views

Counting divisions of an $n \times n$ grid [duplicate]

I'm looking for an efficient way to count the number of ways $D_n$ to divide an $n \times n$ grid into four (possibly empty) regions: top left, top right, bottom left and bottom right, such that no ...
3
votes
1answer
48 views

Identify inherently ambiguous languages

Which of the following languages is/are inherently ambiguous languages? $L_1=\{a^nb^nc^m|m,n\geq0\}\cup\{a^nc^c|n\geq0\}$ $L_2=\{a^nb^nc^m|m,n\geq0\}\cup\{c^mb^na^n|m,n\geq0\}$ My attempt: A ...
-1
votes
1answer
52 views

$L\in P$ prove that $L^*\in P$

I have that question that looks kinda easy at first but it is quit hard. Let $L\in P$ prove that $L^*\in P$ (L is a language and P is the class of all problems which can be decided by a ...
0
votes
0answers
14 views

Finding heavy independent sets

What are some good algorithms for finding maximum weight independent sets in a graph with vertex weights?
0
votes
0answers
18 views

Convert double precision number to rational fraction plus exponent

I have a double precision quantity (either pixels per cm or pixels per inch) that gets converted into pixels per meter. I then need to convert this number into a rational fraction, with numerator and ...
0
votes
1answer
35 views

Is the language regular

We have to check, if the given two languages are regular or not. L={w |each prefix of w has more 0 than 1} L'={w|w has a prefix with more 0 than 1}. I tried something like this: If L regular, ...
1
vote
1answer
32 views

NP problem that has a verifier that uses $\leq 3 \log_2 n$ bits of memory, how does that influence the complexity of the problem itself?

Translated exercise: Algorithms, that solve NP problems. Let's assume a problem $R$ is in the set $\sf NP$. A verifier $M(x,y)$ for this problem works in time $O(n)$ and uses extra information $...
1
vote
0answers
18 views

Is there a minimum spanning tree including $e$ after removing at most $k$ edges?

Let an undirected, connected graph $G=(V,E)$ with the weight funciton $w:E\to \mathbb{R}$, an edge $e$, and $0<k\in\mathbb{N}$. Describe an algorithm determines if there are at most $k$ edges could ...
0
votes
1answer
21 views

How to efficiently sample $y$ in intervals of $\Delta x$ in an “ascending” cubic Bézier curve?

For a cubic Bézier curve defined by control points $\boldsymbol{P_0}$, $\boldsymbol{P_1}$, $\boldsymbol{P_2}$ and $\boldsymbol{P_3}$ with the formula $\boldsymbol{B}(t) = (1 - t)^3\boldsymbol{P_0} + ...
0
votes
0answers
21 views

Red-black tree insert

I'm currently trying to figure out this exercise (sorry for link to image, it's for the red-black trees): http://i.imgur.com/IKMCkVf.png And I do know that the correct one is number three from the ...
1
vote
1answer
21 views

For formal languages $U,V \subseteq X^{\ast}$, what is $\min(U\cdot V)$

Let $L$ be some language, and consider the operator $$ \min(L) := \{ u \in L \mid \mbox{no proper prefix of $u$ is in $L$} \} $$ where a word $u$ is called a prefix of $w$ if it is an initial segment ...