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
52 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 ...
0
votes
1answer
47 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
0answers
14 views

Looking for mathematical/combinatorial and computational explanation regarding adding values in a $5 \times 4$ (matrix?) with a constraint.

Given the following matrix (not sure if I should call it that): Matrix $5 \times 4$ I want to add all possible combinations of values such that each Horse gets but one value from each Bookie. What I ...
1
vote
2answers
66 views

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

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
1answer
26 views

Using pumping lemma

I'm trying to prove that the language $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
13 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 ...
0
votes
0answers
13 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
1answer
507 views

How to construct a context free grammar that generate following language. $\{a^nb^nc^k \in \{a,b,c\}^* | n,k >= 0\} $

$$\{a^nb^nc^k \in \{a,b,c\}^* | n,k >= 0\} $$ $E \to aEbS $ $S \to c$ I do not know where to go next, or even if this is right at all?
-1
votes
2answers
33 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 ...
-1
votes
1answer
16 views

Signed binary number [on hold]

What is the range of number that can be represented by a 16 bit signed binary numbers ? How many are negative and positive numbers ? Thanks.
0
votes
1answer
23 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
1answer
13 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
48 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 ...
1
vote
0answers
31 views

In a floating number system, are there always as many numbers between 0 and 1 as between 1 and $\infty$.

The question is as the following, where $\beta$ is the base, $t$ is precision (length of decimals), $e_{\min}$ is the minimum exponent, and $e_{\max}$ is the maximum exponent. I am not sure, ...
0
votes
1answer
642 views

Y-Axis units on FFT graph

A 50Hz sinusoid wave with a voltage range of +/-20V is sampled at 512Hz for 1 second. No bias or phase shift are present. The signal is run through an FFT. The result is one spike at 50Hz on the ...
13
votes
0answers
88 views

Is there an efficient algorithm for this vertex cycle cover problem? [migrated]

I've been trying to find an algorithm to find a maximum vertex cycle cover of a directed graph $G$ — that is, a set of disjoint cycles which contain all the vertices in $G$, with as many cycles as ...
0
votes
1answer
26 views

Prove that $\mathcal L=\{a^ib^jc^k|i+k=j\}$ is context-free

Prove that $\mathcal L=\{a^ib^jc^k|i+k=j\}$ is context-free I am trying to prove it without to build a pushdown automaton First I tried to look which words are in $\mathcal L$, ...
0
votes
2answers
30 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
49 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
33 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 ...
0
votes
0answers
37 views

Algorithm For Honest vs. Dishonest People

Consider a group of people. When two are taken and asked if the other is honest, they may each either reply that the other is honest, dishonest, or they may report that one is honest and the other is ...
0
votes
0answers
14 views

Cannot open Singular in a running emacs [closed]

I am a newbies in Singular. I just downloaded Singular4-0-2_64.dmg, mounted the image, right-ckick, show the package contents, then moved the contents folder to the Applications directory. ...
1
vote
0answers
60 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
12 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
31 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 ...
1
vote
1answer
1k views

Induction Proof Check: For a binary tree T, Prove that the number of full nodes in T is always one less than the number of leaves in T.

This is a slight variant on a very common beginner's problem. I think I've got it figured out, but I wanted to make sure I actually proved what's being asked. We define a binary tree $T$: (a) A tree ...
0
votes
1answer
24 views

Hardest boolean formula circuit complexity upper bound

I have stumbled upon Shannon's result that states that the maximum number of gates in a circuit needed to compute a boolean function on n bits, $f:\{0,1\}^n \to \{0,1\}$, is $\Theta (2^n/n)$. So far ...
0
votes
1answer
554 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
31 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
1answer
32 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, ...
-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?
0
votes
0answers
16 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
vote
1answer
40 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
28 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 ...
2
votes
3answers
10k views

Question regarding Context Free Grammar exercises

I'm working on the exercises in "An Introduction to Formal Languages and Automata" 4th Ed textbook by Peter Linz. Since there are too few answers given in the back of the book, I wasn't able to check ...
31
votes
8answers
4k views

Is the set of all valid C++ programs countably infinite?

I have heard that the set of valid programs in a certain programming language is countably infinite. For instance, the set of all valid C++ programs is countably infinite. I don't understand why ...
1
vote
2answers
23 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 ...
2
votes
3answers
2k views

An algorithm to convert float number to binary representation

I want to know the algorithm of converting a given float (e.g, 3.14) to binary in the memory. I read this wikipedia page, but it only mentions about the conversion the other way. Let me quickly give ...
0
votes
1answer
78 views

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

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 ...
0
votes
1answer
59 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
22 views

Help solve a computational complexity problem

Find the tight computational time ($\Theta$ notation) complexity of the following function Of course an exact solution is $\sum\limits_{i = 1}^{3{n^3}} {\frac{{2{n^3}}}{i}} $, but I am not able to ...
2
votes
2answers
42 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. ...
6
votes
2answers
8k views

Determining Ambiguity in Context Free Grammars

What are some common ways to determine if a grammar is ambiguous or not? What are some common attributes that ambiguous grammars have? For example, consider the following Grammar G: $S \rightarrow ...
1
vote
0answers
17 views

Finding objects from a list with some properties in $O(n)$

Lets say I have $2$ strings each having $4$ characters. $k$ is a number $\le 4$. If, $2$ strings have exactly $k$ common characters lets say they are a "happy pair" with $k$ points. If I have $n$ ...
0
votes
1answer
16 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 ...
0
votes
1answer
16 views

String recursive definition corner case

I need your assistance with a corner case of this problem: Find a recursive definition for the strings of odd length that start with "a" and end with "b" over the alphabet $\Sigma$={a,b}. I've ...
0
votes
2answers
31 views

RSA Encryption Original Primes $p$ and $q$

I am well aware of the math behind the RSA encryption system, and why it works. The bank, for example, publishes a pair of numbers $(e,n)$ which are used for encryption by the customers. The bank then ...
0
votes
1answer
23 views

Big-O complexity of $2t(\frac{n}{2}) + n^3$

I'm trying to determine the Big-O complexity of the listed equation and want to know if my approach is valid. I tried using the Master method. It appears to be a case $3$ type problem to me, where ...
1
vote
0answers
31 views

How to resolve this computability paradox?

Let's define two Turing machines, $T_1$ and $T_2$, as follows: Given a number $n$ as input, let $T_1$ be a Turing machine that enumerates over all pairs $(p,s)$ where $p$ is the code of some Turing ...