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

3
votes
1answer
63 views

Mapping reduction to show NeverHalt is undecidable

I need help with showing that $NeverHalt_{TM} = \{\langle M\rangle|M\text{ is a TM which runs forever on every input $w$}\}$ is undecidable by giving an explicit mapping reduction. To show that a ...
0
votes
1answer
57 views

How to prove such program is uncomputable

We say that two programs are equivalent if they give the same output on every input. Prove that it is impossible to write a computer program that takes as input two pieces of code, code1 and code2, ...
1
vote
1answer
83 views

Does proving that a function is not in big O mean that the function is in big Omega?

If I determine that a function is not in Big O of another function, can you assume that the function is in big Omega of the same function?
1
vote
2answers
159 views

Choosing Codes or sequences with excellent Auto-Correlation properties

The Auto-Correlation function of Walsh-Hadamard codewords does not have a good characteristics. It can have more than one peak and thus, the Walsh-Hadamard codes do not have the best spreading ...
1
vote
1answer
38 views

Tight bound on the worst running time

I have to find a tight bound for an algorithm. I ended up with $3n^2 + 5$ as the worst running time of the piece of code. Is it ok if I consider $n^2$ as the tight bound? $$3n^2 + 5 \in ...
1
vote
2answers
146 views

Probability that $\frac{n}{2}$ bins are empty [close]

A Bloom filter of length $n$ was built. I have only the first $\frac{n}{2}$ bits of this filter. How will the false positive probability change? For the whole Bloom filter, the false positive ...
0
votes
1answer
388 views

Calculating normals for a polygon mesh (3D computer graphics)

I want to write a program to generate arches, a common architectural form, and export them to a wavefront object format for sharing with various three dimensional graphics editors. To do this, I need ...
0
votes
1answer
21 views

proving regular language

let $L$ be a language over the alphabet $\{a,b\}$ that maintains that for each $w \in L$ ,the difference in absolute between the number of apearences of the letter $a$ and the number of apearences ...
0
votes
1answer
60 views

Regular expression-language

I want to draw the DFA of the language that is given of the following expression, but I got stuck... Let the expression be {$(xy)^{*},(zx)^{+}$}$xz$ . Could you help me understanding which language it ...
10
votes
1answer
192 views

Is it possible that P != NP cannot be proved?

I am probably asking a stupid question but what I gather from a layman explanation of Godel's incompleteness theorem is that it is completely possible that a true statement cannot be derived from ...
0
votes
1answer
33 views

first order definability with $<$ vs $Succ, 0$.

In first order logic formulae with just the predicate $<$ could describe more structures than first order formulaes with $Succ$ (successor predicate) and a constant $0$ such that $\forall x (\neg ...
2
votes
0answers
92 views

Cut-off Subtraction in Coq

I am new to the world of computer assistant proof programs in general, and Coq in particular. As a result, I have sought to prove some elementary results about integers as a way to … At the moment, I ...
1
vote
1answer
89 views

Is there a DFA with $k+2$ states which its reverse has $2^k$ states

I am trying to figure out if there exists a DFA $M$ with $k+2$ states (for every $k\in \mathbb{N}$ ) so that every automaton which accepts $L(M)^R$ has at least $2^k$ states. I am trying to find an ...
4
votes
2answers
232 views

How to understand the definition of sets in homotopy type theory and the role of univalence?

Bear with me, I'm a physicist. In homotopy type theory, as I understand it, a type $X$ is a set if all the morphisms over its terms $x:X$ are identies. When I say "morphisms", then I view the term as ...
2
votes
1answer
114 views

Finding aggregate score from incomplete data

$$ \begin{align} n & = \text{number of reviews}\\ x & = \text{review score}\\ \bar{x} & = \text{aggregate score} \end{align} $$ I have a specified number of reviews for a product, I have ...
1
vote
1answer
43 views

Prove the existence of $C\in L_{regular}$ so that: $A \prec C \prec B $

Given $A,B$ regular languages. Prove the existence of $C\in L_{regular}$ so that: $A \prec C \prec B $ Whereas $A\prec B$ stands for: $A\subset B $ and $B\setminus A $ is infinite regular language. I ...
0
votes
1answer
45 views

Communication complexity example problem

Let $G = (V,E)$ and $H = (W,F)$ be two undirected graphs with $|V| = |W| = n$. G and H are isomorphic if there is a bijection f : V -> W such that: $\{u,v\} \in E$ <=> $\{f(u),f(v)\} \in F$ ...
2
votes
1answer
49 views

Proving that $L=\{w\in \Sigma^*: |w|_a= 2^n +273$, $n\in \mathbb{N} \}$ is irregular. [duplicate]

I am trying to prove that $L=\{w\in \Sigma^*: |w|_a= 2^n +273$, $n\in \mathbb{N} \}$ is irregular, whereas: $\Sigma=\{a,b\}$. I tried to use the pumping lemma with no success. I have also tried to ...
4
votes
2answers
266 views

NP-complete: One proof to rule them all

To prove a decision problem $C$ is in NP-complete, 2 things need to be shown: There is a polynomial verification for $C$ solution. Every problem in NP is reducible to $C$ - You can solve all the ...
1
vote
3answers
354 views

Context free grammar question

i have two context free grammar questions and I don't know how to do them. $$\{(a^n)b(c^n) \mid n >0 \}$$ I'm having trouble with this one because I don't know how to account for $a$ or $b$ not ...
1
vote
1answer
416 views

Time complexity of binary sum

What is the time complexity of binary sum, the sum of two binary numbers done like in elementary school? Say one number is F and his length is $s$ bits, and another number is H and his length is $t$. ...
3
votes
1answer
429 views

lambda calculus and category theory

I am not particularly knowledgeable in either lambda calculus or category theory, but I am starting to learn Haskell so I would like to ask: are there connections between category theory and lambda ...
0
votes
1answer
996 views

Proving a tight bound on the worst case running time of an algorithm?

This exercise I don't understand what 'give a tight bound' implies here. The correct way to prove this is to consider that the runtime is in O and then use the definition of BIG O to prove that it ...
6
votes
1answer
150 views

Reference Request on Order Theory topics

I am looking for some references (especially a good recent book) that covers important topics involving partial orders such as: order polytopes, sorting/selection in partially ordered sets, upper and ...
2
votes
1answer
251 views

Turing Machine for comparing, copying, and operating

If one wants to design a Turing Machine for a function such as this: Where $x>0,y>0$ and are both integers represented in unary, so an example movement in this TM on the read-write head would ...
4
votes
1answer
109 views

Could every ultimately periodic word $\eta$ factored $\eta = pq^{\omega}$ such that $pq$ is primitive?

An infinite word $\eta$ is called ultimately periodic iff $\eta = pq^{\omega}$ for some $p, q \in X^*$. A word $w \in X^*$ is called primitive iff it is not a power of another word, i.e. it could not ...
2
votes
1answer
1k views

What is meaning of strict weak ordering in layman's term?

I gone through many pages using Google, but not understand exact meaning of Stick-weak Ordering term. I have this requirement while sorting strings. Thanks.
8
votes
1answer
747 views

Applications of Differential Geometry in Artificial Intelligence

I am new to this wonderful site. I searched around a bit but I couldn't find any well-discussed posts on applications of differential geometry to artificial intelligence, or more generally to computer ...
3
votes
1answer
106 views

Prove that Y is not context free.

2.42 Let $$Y = \{w\mid \text{$w=t_1\#t_2\#\cdots\#t_k$ for $k \ge 0$, each $t_i \in 1^*$, and $t_i \ne t_j$ whenever $i \ne j$}\}.$$ Here $\Sigma = \{1,\#\}$. Prove that $Y$ is not context free. ...
0
votes
1answer
63 views

How do I know that this is the density of the Chebyshev Points?

By knowing that a discrete distribution of points go asymptotically to the density: $\displaystyle p(x)= \frac{1}{\pi \sqrt{1-x²}}$ in $[-1, 1]$ I am able to conclude that interpolating at those ...
1
vote
1answer
64 views

Suppose $f_1 \in \Theta(g_1) \land f_2 \in \Theta(g_2)$. Prove $(f_1 + f_2) \in \Theta(\max\{g_1, g_2\})$.

I need to prove that $f_1 \in \Theta(g_1) \land f_2 \in \Theta(g_2) \implies (f_1 + f_2) \in \Theta(\max\{g_1, g_2\})$ This question is relevant, but I have a slightly different case, so I don't ...
1
vote
0answers
55 views

What exactly is 'computer mathematics'?

I'm looking at some potential things to study next semester and I see a full B.sc. degree called 'Computer mathematics'. It says it's a hybrid between computer-science and mathematics. Does anyone ...
0
votes
2answers
1k views

problem simplifying boolean algebra expression using consensus theorem

Please simplify this logic expression for me with helping boolean algebra : A'C'D + A'BD + BCD + ABC + ACD' I know that must use consensus theorem . my solve : STEP 1 : Terms 1 & 3 ...
1
vote
0answers
35 views

simplifying boolean algebra expression [duplicate]

A very urgent question : Please simplify this logic expression for me with helping boolean algebra : A'C'D + A'BD + BCD + ABC + ACD' I know that must use consensus theorem . my solve : STEP 1 : ...
3
votes
3answers
59 views

algorithm question how prove that $(n+a)^b = \Theta(n^b)$ [closed]

this question doctor in college give us as home work but I don't know how approve it
1
vote
1answer
182 views

Proving a set is language generated by given grammar

I have grammar $G$ with productions $S\rightarrow aS|aSbS|\epsilon$, and task is to prove that $L(G)=\{w|$every prefix of $w$ has at least $a$'s as $b$'s$\}$ (I'm not sure if translation is correct, I ...
2
votes
1answer
123 views

transition function DFA, PDA

I am new to PDA, teacher is using different format, I see different notation for transition function I am not able understand teacher's format in this question for transition function of PDA! ...
2
votes
2answers
127 views

Decimal to fraction conversion

We write software for managing recipes and are working on moving from an approximation based decimal to fraction conversion, for example, anything between 0.03125 and 0.09375 becomes 1/16 to a math ...
0
votes
1answer
83 views

Find Regular Grammar from NFA

I'm currently doing some self study to improve my half-forgotten college theory of comp skills. I'm going over some problems from an old book and it asks you to find a regular grammar for the ...
2
votes
0answers
51 views

LLL and factoring polynomials in $\Bbb Z[x]$

Given a degree $2k$ reducible polynomial $f(x)=\sum_{i=0}^{2k}a_ix^i\in\Bbb Z[x]$ with $gcd(a_{2k},\dots,a_0)=1$ that is known to be of the form $f_1(x)f_2(x)$ with $deg(f_i(x))=\frac{deg(f(x)}{2}=k$ ...
1
vote
1answer
62 views

Working with the word w⋅y, while given the word y⋅w

$L$ is a regular language. I am given $F(L)$ such that $$F(L)= \{wy \mid yw\in L\}$$ I need to prove that if $L$ belongs to $L_\text{dfa}$, $F(L)$ also belongs to $L_\text{dfa}$. I am having a hard ...
0
votes
2answers
46 views

Building an automaton that defines a language

I have $2$ languages, $L_1$ and $L_2$, both are part of $L$-dfa. I have the following language: $$L_0= \{a_1\cdot b_1\cdot a_2\cdot b_2\cdot\ldots a_n\cdot b_n \mid a_i,b_i\in\Sigma, ...
10
votes
1answer
244 views

Algorithm for obtaining the surface of a mirror

My colleague and I have been trying to implement an algorithm described in the paper "Recovering local shape of a mirror surface from reflection of a regular grid", primary author of which being ...
1
vote
1answer
114 views

How does Knuth's second algorithm to calculate permutations work?

I have started reading the Art of Computer Programming Volume 1 by Knuth. The first half of the book is basic concepts in maths. On page 45 there is an algorithm to obtain the next (amount of) ...
2
votes
1answer
97 views

Combinatorics/Task Dependency

Here is a competitive programming question: You have a number of chores to do. You can only do one chore at a time and some of them depend on others. Suppose you have four tasks to complete. For ...
3
votes
2answers
60 views

Injective map, that maps context-free languages to regular languages

Let $\Sigma \neq \emptyset$ be an alphabet. Is there an injective map $f: \Sigma^* \rightarrow \Sigma^*$ such that for every context-free language $L \subseteq \Sigma^*$ the set $f(L)$ is a regular ...
1
vote
0answers
104 views

Is there a proof that Encrypting and then Decrypting any data using AES 256 will result in the same data?

I use AES quite often at work (I'm a software programmer) and I trust that it "works" without understanding the maths behind it. It's a black box to me. Does a mathematical proof exist that AES 256 ...
0
votes
1answer
175 views

Public and private RSA keys, using the primes $p = 5$ and $q = 11$

Assume that $p = 5$ and $q = 11$, and all other variables are defined as per the RSA theorem (a) Suppose we consider $e = 3$. Would $(e, n)$ be a suitable public key? (b) Prove that if $d = 27$, ...
1
vote
1answer
142 views

How can I encode this?

Let say I have 7 integers: 1, 2, 3, 4, 5, 6, 7. Among the 7 integers, I choose 3 integers. For example, my choice is (1,2,3). Note1: The order of the integers in the choice doesn't matter. This means ...
0
votes
1answer
63 views

beta reduction bascis

Hi I get the basics of beta reduction e.g. $$(\lambda var.body)arg $$ you just replace the occurrences of var with arg in body. However what happens here? $$(\lambda x.xx)(\lambda x.xx) ...