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.

learn more… | top users | synonyms

0
votes
0answers
18 views

Hierarchy of hardness for the pumping lemma for regular languages.

Whenever I bring up the Pumping lemma for regular languages people often say `better to use the Myhill-Nerode theorem'. I want to make this thought rigorous. Def: A language $L$ is pumpable if there ...
2
votes
0answers
65 views

Todd-Coxeter algorithm: coincidences

I'm trying to understand the Todd-Coxeter algorithm with the help of a multiplication and relator table, but there is one thing about coincidences that is not really clear. For some small groups (for ...
2
votes
4answers
727 views

Convert from base 10 to base 5

I am having a problem converting 727(base 10) to base 5. What is the algorithm to do it? I am getting the same number when doing so: $7*10^2 + 2*10^1+7*10^0 = 727$, nothing changes. Help me figure it ...
1
vote
3answers
70 views

Base 16 to base 10 number conversion

I know that if we want to convert from base 16 to base 10 we do as follows (for example): Given : $15C$ in base $16$ Conversion to base 10: $12 \times 16^0 + 5 \times 16^1 + 1 \times 16^2 = 348$ in ...
0
votes
1answer
110 views

Find all subsets whose sum modulo a value is 0.

How can we find the count of number of subsets of a given set (e.g. {1,7,4,90,23} ) whose sum is a multiple of a given value A. One method which I know of is to store all subset sums modulo A and ...
0
votes
0answers
36 views

Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
0
votes
1answer
29 views

using pumping lemma to prove that a set is not regular

A={s11s|s $\epsilon$ {0}^*} so the strings 00011000 and 000001100000 are accepted of A but not 00100 or 001100000. Demon chooses k. ...
0
votes
2answers
41 views

What can be observed by evaluating a polynomial at roots of order greater than the polynomial itself?

I have been reading through an algorithms book on the use of FFT for large number multiplication. An example it used to emphasize a point was: Evaluate the following polynomial at all roots of unity ...
0
votes
0answers
40 views

It would be possible to use the covariance matrix $C'=XX^T$ instead of the standard $C=X^TX$ to get the same result on PCA?

It would be possible to use the covariance matrix $C'=XX^T$ instead of the standard $C=X^TX$ to get the same result on PCA? If so, what are the next steps to retrieve the data with reduced ...
1
vote
1answer
37 views

Are there differences between total functions, epimorphic functions and surjective functions?

I've read three definitions which seems to point to the same idea. I've read about epimorphic functions in Mazzola's Comprehensive Mathematics for Computer Scientists - in this book, he treats it as ...
1
vote
4answers
70 views

Examples of partial functions in which the domain is not known?

I was reading this, it mentions about a kind of function in which the exact domain is not known. The only example given is this one - and I'm not really sure I understood it. I got curious about it: ...
0
votes
0answers
21 views

(L1* ∩ L2*) = (L1 ∩ L2)* for all languages L1 and L2 over the alpabet Σ={A,B} Is it true or false and why?

plz answer me Determine whether each of the following statements is true or false. If a statement is false, give a counterexample..... 1- $(L_{1}^{*} \cap L_{2}^{*}) = (L_{1} \cap L_{2})^{*}$ for ...
0
votes
1answer
34 views

How to prove not a CFL with pumping lemma?

need to prove using the pumping lemma that $L=\{a^{2N} b^{N} c^M d^N| M,N>=0\}$ is not Context-Free. This is what I have so far: Suppose that L is a CFL. Let p be the pumping length. Choose ...
1
vote
4answers
150 views

Prove this language is not regular [closed]

How do I prove that this language = {1^k | k is a perfect square} is not regular by showing that no DFA can accept the language?
0
votes
1answer
71 views

efficient algorithm to place people in a specific order

You are preparing a banquet where the guests are government officials from many different countries. In order to avoid unnecessary troubles, you are asked to check the list of international conflicts in ...
0
votes
1answer
55 views

How to convert this NFA to DFA?

http://www.cs.odu.edu/~toida/nerzic/390teched/regular/fa/figures/nfa-dfa1.jpg What are the steps for convert this NFA to DFA??
0
votes
1answer
17 views

how to come up with a solution of finite or infinite language using context free grammer?

I am trying to come up with a solution of finite or infinite language using context free grammer. I have these grammers to find if it's a solution of finite or infinite language ...
0
votes
0answers
61 views

Boolean algebra - cube - minimal disjunctive normal form

I have a test coming up and I would like to know how to solve these kinds of problems. This is the description: ...
0
votes
0answers
15 views

algorithm for traversing a fractal in a “maximally ordered” way

consider a multidimensional fractal that can be "traversed" in an arbitrary order. is there an algorithm for traversing a fractal in a "maximally ordered" way? in other words the algorithm has ...
3
votes
2answers
359 views

Linear Homogeneous Recurrence Relations and Inhomogenous Recurrence Relations

I'm having some difficulty understanding 'Linear Homogeneous Recurrence Relations' and 'Inhomogeneous Recurrence Relations', the notes that we've been given in our discrete mathematics class seem to ...
2
votes
0answers
17 views

A confusion about RP class of problems

I have some notes which introduces the quantifier $\exists^+x$ and interprets it as "the overwhelming majority of $x$". Then, it defines RP (Randomized Polynomial) as: $$ L\in RP\Leftrightarrow ...
0
votes
1answer
13 views

Detecting ray cross after hit on a convex object

I have a hw question im struggling to solve - Any guidance will be appreciated.
1
vote
1answer
103 views

Finite state machine

I am doing discrete math, and we are studying Finite State Machines. But i am a little confuse on how to do this. Here is a question, Write a regular expression for the language, and define a finite ...
1
vote
3answers
62 views

Why do the children of a node $n$ in a complete binary tree have indices $2n $ and $2n+1$?

The complete binary tree is breadth-first ordered 1 to $n$ where $n$ is the number of nodes. The thing I cant seem to understand is that why are the children of node $N$ always $2N$ and $2N+1$? For ...
11
votes
3answers
157 views

is there an efficient algorithm for comparing collections of points?

Let's say you have two sets of M points $p_1...p_M$, and $q_1...q_M$, which reside in $\mathbb{R}^N$. Is there an efficient (e.g. polynomial in M and N) algorithm to determine if the point-sets are ...
1
vote
3answers
54 views

Prove that this language is not regular (Pumping Lemma)

Prove that the following language is not regular. I have no clue where to start. $$L = \{ a^n b^n c^n \mid n \geq 0 \}.$$
0
votes
2answers
25 views

Help with finding the generating function (with a constant )

How do you get the generating function from this formula: $8(1+x)^{7}$ I have the following formula for $(1+x)^{n}$ : $n\choose 0$ + $n \choose 1$$x^1$ + $n \choose 2$$x^2$+... +$n \choose ...
0
votes
1answer
166 views

Discrete Math: Functions and Set Questions

1) Consider the function: $f: \mathbb{R} \to \mathbb{R}$ (Real to Real Number), where $f(x)=2+x^2$, what would be all of the preimages of $3$? 1) $11$ 2) $11$, $-11$ 3) $1$, $-1$ 4) $1$ 2) Let $D ...
1
vote
2answers
48 views

How can I tell if these are undecidable?

For each of the following set, show that they are undecidable. Do not use Rice theorem. a. $L_{1} = \{M |M$ accepts w if w contains the substring 10 $\}$ b. $L_{2} = \{M| M$ accepts an odd number ...
0
votes
1answer
30 views

find an algorithm to find MST in linear time while each edge has the same weight

I have been disscussing this problem with a lot of my friends . However no solution has been found. let G= w is a weight function for each e in E w(e)=1 find MST of G in O(|V|+|E|) thanks
1
vote
1answer
68 views

texture mapping from a camera image to a 3D surface acquired by a kinect

I have the following problem: A kinect camera capture a 3D surface and save it as a .obj files containing all the positions of the vertices (in the kinect coordinate system). If I take a picture ...
0
votes
0answers
28 views

Binary counter with increment by powers of 2 worst case and amortized

Question: We define a binary counter with the function $Increment (i) $ that whenever called , it increments the counter by $2^i$. It does that by: starting from the i'th place in the counter: going ...
0
votes
0answers
84 views

Bitwise operations: using bitwise operations on bitstrings to find combinations

I'm not sure how one would go about solving this problem from my discrete math book. Here is the problem : Show how bitwise operations on bit strings can be used to find these combinations of ...
0
votes
0answers
26 views

how to convert Finite Automata into Push Down Automata

I am trying to convert Finite Automata into Push Down Automata and I am not sure if I am doing this right. There are not many good tutorials on this topic that I can find, but this is what I have. I ...
0
votes
3answers
104 views

What is the difference between regex operations in math and regex in UNIX / Linux?

What is the difference between regular expression operations (union, concatenation, kleene star) and regular expression (implemented in UNIX and can be used together with the grep command)? Are there ...
0
votes
1answer
26 views

Provide a Proof of Inequalities for the Given Problem

Let A be known as a graph. By definition an independent set S is a group of vertices (could be 0 vertices, or could be all vertices) of A where there are no two vertices from S that are adjacent in ...
0
votes
1answer
95 views

Planar and Euler's Formula Question

If a connected planar graph has four regions and six vertices, how many edges will the graph have? (I believe the answer is 8 but I'm not positive) 1) 9 2) 8 3) 6 4) 7 Graph A = ({a,b,c,d,e,f,g}, ...
0
votes
1answer
20 views

Homogeneous Arrays

I have this problem for homework and was wondering if anyone could help me out with it:
22
votes
5answers
3k views

Is a brute force method considered a proof?

Say we have some finite set, and some theory about a set, say "All elements of the finite set $X$ satisfy condition $Y$". If we let a computer check every single member of $X$ and conclude that the ...
0
votes
0answers
14 views

What are the current lower bounds for $NTIME$ vs $DTIME$?

Trivially, we have $DTIME(f(n)) \subset NTIME(f(n))$. Is it known whether or not this inclusion is strict? Do we know if $DTIME(f^c(n)) \subset NTIME(f(n))$ for any $c$? Is there any $c$ for which ...
0
votes
1answer
102 views

Bipartite Graphs and Trees Questions

Which of the claims below is not equivalent to the rest? 1) Every cycle in a graph "B" has an even length 2) Graph "B" is bipartite 3) Graph "B" has two components that are connected. 4) Graph "B" ...
0
votes
0answers
27 views

Given a N*M matrix determine the number of pairs that exist in a GLCM

This is an interesting problem for which I can't find a direct solution. Given a n*m matrix (in this case 5*5): 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 There exist a certain number of ...
0
votes
1answer
61 views

Checking Boolean Algebra work - Simplification

I am currently working on an assignment for a CE class I am taking, and I wanted to know if I have been simplifying these equations correctly. I'm supposed to reduce them to a sum of products. 1) ...
2
votes
3answers
45 views

Help making the distinction between polynomial and exponential time

I'm trying to understand how problems are categorized in these two classes. I have a specific problem I'm looking at, the directed path problem: PATH = $\{\langle G,s,t \rangle | G$ is a directed ...
3
votes
2answers
156 views

Are even numbers the sum of two odd sub-primes? / How to use computers to check?

Suppose $$p_{a} + p_{b} = 2{p_{1}}^{m_{1}}{p_{2}}^{m_{2}}...{p_{n}}^{m_{n}} \qquad \text{where }p_{x} \in \mathbb{P} -\left\{2\right\} $$ Then $$\frac{p_{a} + ...
0
votes
1answer
89 views

If the union of two languages is NP-complete, is one of them NP-complete?

Question 1) If $A\cup B$ is NP-complete, and $A$ is NP, and $B$ is P, then is $A$ NP-complete? I don't think so but I am unsure. When I try to reduce $A\cup B$ to $A$, I fail because strings in $B$ ...
1
vote
1answer
35 views

Showing a Problem Is Undecidable

How can I show that T is undecidable using only this information? $$T = \{\langle M, w, r\rangle \mid M \text{ accepts } w^r \text{ when it accepts } w.\}$$ So, what it's saying is that the machine ...
0
votes
0answers
34 views

An independent set of vertices $\times$ the chromatic number $\ge$ the number of vertices

$A$ is a graph. By definition an independent set $S$ is a group of vertices (could be 0 vertices, or could be all vertices) of $A$ where there are no two vertices from $S$ that are adjacent in graph ...
0
votes
1answer
55 views

Using the Pumping Lemma to prove a language is not regular.

I want to know if my proof is wrong and whether what I am doing works. $$\sigma = \{0, 1\}$$ $$A = \{0^n1^m \mid n < m\}$$ Claim: A is not regular. Proof: Assume A is regular. Let p be the ...
0
votes
1answer
66 views

Reduction from HALT on any string to HALT on empty string

The title says it all (if I have phrased it properly). How can we show that HALT on any string is undecidable using a decider for HALT on empty string? I think this is written: $$ HALT \leq ...