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
1answer
17 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
55 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 ...
7
votes
1answer
122 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
27 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 ...
1
vote
0answers
54 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
69 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 ...
3
votes
2answers
155 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
38 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
41 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
30 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
45 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 ...
5
votes
2answers
183 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
108 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
96 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$. ...
2
votes
1answer
98 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
0answers
32 views

mathematical structure or algorithm for mapping a sinuous pattern ( a river)

I have a java application where I need to show a wooden log floating down a sinuous river. the problem is the river is in the shape of an S and for every frame i need to draw the wooden log. So I was ...
0
votes
1answer
301 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 ...
5
votes
1answer
125 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
81 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 ...
3
votes
1answer
57 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 ...
1
vote
1answer
89 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.
4
votes
1answer
157 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 ...
4
votes
0answers
124 views

Math or CS PhD areas to look at. [closed]

I am looking into getting back to school to get a PhD in Mathematics or Computer Science (I hold MA in Math). I am wondering what new areas of research in Math and CS are promising in a sense that ...
3
votes
1answer
74 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
16 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
54 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
49 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
0answers
32 views

Inward-pointing normal and co-ordinate systems

I'm doing a course in computer graphics, and as such, we're being taught measures on how to deal with the Hidden Surface Removal problem. One of the topics covered was "back-face detection", that is, ...
0
votes
2answers
265 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
34 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
51 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
620 views

Colored ball probablity

A triangular box contains five differently colored balls: red (R), green (G), blue (B), white (W), and yellow (Y). Define an appropriate sample space to study the outcome of an experiment where a ...
0
votes
0answers
28 views

What is the simplest form of the Boolean expression below? [duplicate]

I'm completely new to Boolean algebra, and I'm trying to simplify the expression below, using the distributive law, cancellation, negative absorption and De Morgan's theorem. I would start with the ...
1
vote
1answer
67 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
52 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
75 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
37 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
36 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
55 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
41 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, ...
6
votes
0answers
103 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
51 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
62 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
39 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
59 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 ...
1
vote
1answer
47 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
0answers
52 views

Lower bound of maximum seating plans

10 people will sit in a row of 10 chairs. How do I calculate how many seating plans can be made, where two seating plan are considered the same if two plans share adjacent quadruples? or How can I ...
0
votes
1answer
56 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) ...
1
vote
0answers
54 views

Showing particular language is NP-complete

How is FLO NP-complete? Let G be a social network where vertices correspond to people and edges are relationships between people (undirected). Some pairs of people (who are friends) get married. We ...
1
vote
0answers
49 views

Homomorphic Compression

Can there be an algorithm such that: given a plaintextdata P, Q and compression function e: $$e(P + Q) = e(P) + e(Q)$$ $$e(P*Q) = e(P)*e(Q)$$ The idea is closely related to homomorphic encryption ...