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

0
votes
1answer
23 views

Max Flow Min Cut - Prove that $e$ crosses some minimal cut

I already asked about the opposite direction but I'm really confused about it, so I'd like to get some help please: Let's assume we have a flow network $G$ and some edge $e$. Now, Let's assume ...
1
vote
2answers
13 views

Max Flow Minimum Cut - after removing an edge

Suppose that the max flow of a network is $|f|$ and there's a minimum-cut $(S,T)$ such that $e$ is an edge which crosses the cut. Why is it must be that the max flow after removing $e$ is exactly $|...
1
vote
1answer
36 views

Although proven by pumping lemma language is not regular [closed]

We have to show, that although the language $L=\left\{qw^jq^k \mid j,k \in \mathbb N, j>k \mbox{ or }j \mbox{ is not even }\right\}$ satisfies pumping lemma, it is not regular. Okay, my try: For $...
0
votes
1answer
37 views

Undestanding SVM

I am the moment trying to understand how SVM works.. I understand the concept of finding a seperating hyperplane with the highest margin, but i do not understand how it works in mathmatically. Mor ...
0
votes
1answer
25 views

What are “definable integer sequences”

According to Wikipedia, An integer sequence is a definable sequence, if there exists some statement P(x) which is true for that integer sequence x and false for all other integer sequences. ...
0
votes
1answer
28 views

proving not regular with pumping lemma

Not quite sure if I understand pumping lemma correctly. so if i have this language and i like to show it is not regular: L={ $q^a w^be^c| a,b,c \in N, a+b=c$}. If L would be regular, than there ...
1
vote
1answer
35 views

A Question about Computable Functions

Barry Copper states following in his Computability theory book which I have a question about them. Exe.4.5.1: Show that if $\varphi_e(x) \downarrow $ is a computable relation, then so is ...
2
votes
1answer
83 views

Are sets and symbols the building blocks of mathematics?

A formal language is defined as a set of strings of symbols. I want to know that if "symbol" is a primitive notion in mathematics i.e we don't define what a symbol is. If it is the case that in ...
0
votes
1answer
26 views

Determine whether a language belong to R,RE\R,coRE\R or other

For the following language, determine to which class it belongs $$L_3=\left\{\langle M\rangle\Big\vert|\langle M\rangle|\le 2016\text{ and M is a TM that accepts }\varepsilon \right\}$$ I've ...
0
votes
0answers
60 views

Having rand2() function build rand5()

I was asked this question long time ago. Having a function $rand2()$ (in any computer language, "rand" means random) which returns $0$ or $1$ (two values only) with a uniform distribution, i.e. $$P(...
0
votes
0answers
30 views

What is computational complexity of a coding technique

In my previous Question Help in understanding a coding technique based on inverse mapping of a dynamical system I learnt how to apply chaotic map in coding theory in communications. Steps: (1) The ...
1
vote
0answers
22 views

Modal extensions (operators) for monoidal (categorical) logics

There is nice generalization of first order logic to monoidal (categorical) logics http://www.springer.com/us/book/9783642128202 which has recently been applied extensively as replacement for deontic ...
0
votes
0answers
27 views

Are these functions computable - Understanding computable functions

There is a theorem in computability theory which states: B.Cooper: If $A\subseteq N$ is computable, then $A$ is also computably enumerable. In the proof of this theorem -which is an ...
0
votes
0answers
20 views

How do I calculate such possible number of total and serial schedule?

Consider the following two transactions $T_1$ and $T_2:$ How many non serial schedules are possible, if we execute both transactions concurrently? $3000$ $3001$ $3002$ $3003$ My try: ...
-3
votes
1answer
26 views

Deterministic Turing Machines

Let's say that M is a deterministic Turing Machine, can I say that for a certain input I will have the same output? How can I demonstarte this?
0
votes
0answers
42 views

Construction of Permutation Group (bounded order) from a Set of Permutation

Given a set of permutation $S$. It has $|S|$ (The cardinality of $S$) elements. Consider a subset $A\subset S$. We can construct a group using $A$. One possible algorithm could be- We start ...
1
vote
1answer
48 views

Prove that if $xy=yz$ then $ \exists u,v \in A^*$ and $\exists p \in\mathbb N$ such that $x=uv$, $z=vu$ and $y=(uv)^pu$

Prove that if $xy=yz$ then $ \exists u,v \in A^*$ and $\exists p \in \mathbb{N} $ such that $x=uv$, $z=vu$ and $y=(uv)^pu$. $A^*$ is the set of all words that can be formed over the alphabet $A$. By $...
0
votes
1answer
16 views

Grammar generator for the Knight (Chess)

I'm trying to build a regular grammar to generate the valid movements for the knight. I'm using (U)p, (D)own, (L)eft, (R)ight to represent each of the components of the movement. I already have a NFA ...
1
vote
2answers
29 views

equivalent regular expr

Given a regular expression $r_1$, is $(r_1^*)^* = (r_1^*)$. I know that this is true but I do not know how to prove it. Would it be adequate to set $r_1$ to a regular expression such as $(a+b)$ for ...
2
votes
1answer
83 views

Is [a, a[ empty?

Is the segment $[a, a[$ equivalent to the point $\{a\}$ or the empty set $\varnothing$? Can one or other be formally proved? I was wondering because in computer science it is the empty set, as the ...
0
votes
1answer
48 views

b tree least upper bound

Hi I have an university assignment question that I can't fully understand. My tutor doesn't understand some of the terminology and my lecturer in the subject is not particularly forthcoming. The ...
0
votes
1answer
15 views

Is there a Relationship Between Multi-Valued Logic and n-Satisfiability?

Is binary (Boolean) logic related at all to the two-satisfiability problem? And is ternary logic related in some way to the three-satisfiability problem? Would it follow then that if one were to ...
2
votes
0answers
44 views

In a directed graph with $n \geq 2$ nodes, if two different nodes reaches $n$ nodes, then this graph has a directed cycle.

I think this statement is true because if first node can reaches every other node (including second node) and second node can reaches every other nodes (including first node), then first node and ...
1
vote
0answers
20 views

Rightmost derivation word aaaccb

I have got these context free grammar: $S \implies aSA | a \\A \implies Ab|c$ The goal is find rightmost derivation of word $aaaccb$ a draw derivate tree, which corresponding with this derivation. ...
0
votes
1answer
21 views

Context-free grammar and regular expression

I have got these Context-free grammar/regular expression: (1) $abba^{*}$ (2) $abb(a+b)^{*}$ (3) $a^{*}ba^{*}ba^{*}$ (4) $S \implies abA \\ A \implies Aa|b$ (5) $S \implies aS|bA \\ A \implies aA|...
0
votes
1answer
27 views

Is every decidable language accepted by a turing machine? [closed]

I am taking a cs class and the lecture slides are not very complete on this topic. can somebody clarify? thank you
2
votes
3answers
37 views

Naming binary strings

Given a string of 1's and 0's, containing the same number of 1's as 0's, is there a way to uniquely "name" each string with a number such that it is computationally easy to go between this "name" and ...
1
vote
0answers
55 views

How Do You Write Mathematical Proofs | Linear Algebra (I have no idea what I am doing…) [closed]

I am a Computer Science student, and right now I am taking a 15 week Summer class on Linear Algebra. This course will cover proof writing (basic) and I have never written a proof like these in my life!...
1
vote
0answers
25 views

Discrete Mathematics: Prove Expression Is Even

I'm brushing up for my Discrete Math final exam, and would like to know if the following proof is valid... Prove by direct proof that $a^2-5a+8$ is even for any integer $a$. Proof: By ...
2
votes
1answer
35 views

Turing Machine Diagram, one Solved Problem ?!

The following Diagram Gets binary number $x$ and produce $x+1$. complete it: the book solution is says first line is the answer. any hint or idea for completing this TM?
0
votes
1answer
19 views

Number system question

Is it true that if we are given a number system with base 3, mantissa 2, $-1 \le p \le 1$, determined by $$\pm 0.d_1 d_2 \times 3^p$$ where each number is normalized, unless it is zero, then the ...
2
votes
1answer
50 views

Longest Common Prefix among $n$ strings with length $k$

Suppose I have a set of alphabet $\Sigma = \{ A,B,\ldots,Z \}$ with $|\Sigma|=26$. I am generating a set of $n$ random strings $S$, with each string of length $k$ from the alphabet (for the random ...
1
vote
0answers
40 views

Discretizations of Differential, Geometric and Topological Notions

I have noticed a recurring theme in Graph Theory / Theoretical Computer Science (abbreviated GT and TCS throughout this post) in that notions typically belonging to differential calculus / geometry / ...
1
vote
0answers
73 views

What is the relationship between Realizability and the Curry-Howard isomorphism?

I have recently been studying the Curry-Howard isomorphism/correspondence. My sources have primarly been Sørensen [1] and Girard [2]. Realizability is introduced here in the form of Kleene's ...
1
vote
1answer
26 views

Showing equivalence of 2 Big O notations

I have the task to show that the following two big O definitions are equivalent. My first thought was that it has to be equivalent because the set of natural numbers excludes all broken rational ...
0
votes
1answer
20 views

Demonstrate that a language is semi-decidable

I need some help to demonstrate that this set below is decidable, semi-decidable, or undecidable. Here's the set: H = {p| |Images(fp)| >= 10} explanation: an ...
0
votes
0answers
14 views

Show how to construct new AKE protocol

I'd appreciate if someone could help me with this exercise (image is for text and notation): http://i.imgur.com/S6xmkEX.png Could someone give me a hint, what am I supposed to do to show it?
1
vote
0answers
33 views

Find $A^n$ for n=0,1, and 3: Languages and Finite State Machines

The question is: Let $A$={11,00}. Find $A^n$ for n=0,1, and 3. Would i be right in thinking that $A^0$ = {λ} $A^1$ = {11,00} $A^3$ = {111111,111100,110011,110000,000011,000000,001100,001111}. if ...
0
votes
3answers
34 views

What does the algorithm s = s + k * k do?

I just finished an exam in my math class and I did well except for one question that I just can't get out of my head, it seems simple but I just can't figure it out: PROBLEM: ...
2
votes
0answers
19 views

levenshtein distance: iterative vs single calculation

I had a list of 1100 words and sought to cluster them based on a levenshtein distance of 2. This reduced the list to 900 words. Running the calculation again reduced the number to roughly 800, and ...
0
votes
1answer
28 views

Algorithm to find password from hash value

I'm currently trying to solve this exercise (sorry for link to image, but there's a bit text): http://i.imgur.com/ETaCK0H.png But there's a few things in the exercise I don't understand. For example,...
8
votes
1answer
411 views

What is the current state of formalized mathematics?

Russell and Whitehead famously tried to actually create and use a formal system to explicitly develop formal mathematics in their work, "Principia Mathematica." Much more recently, with the aid of ...
0
votes
2answers
41 views

Bit increase when averaging?

I have a given number $N$ of binary numbers, that are stored using a given number $B$ of bits. $B$ is the same for all the numbers. For example, thease values where $N = 4, B = 4$. ...
12
votes
1answer
278 views

How to formulate the P v.s. NP problem as a formal statement inside the language of set theory?

I've read a lot that some computer scientists believe that P v.s. NP could turn out to be independent of ZFC. The thing that puzzled me is how to formulate this inside the language of set theory? I ...
2
votes
0answers
17 views

Find Theta Class of T(n) = T(3n/4) + T(n/6) +5n [duplicate]

I'm not quite sure I can apply the Master Theorem to T(n) = T(3n/4) + T(n/6) + 5n. It is not in the normal form of T(n) = aT(n/b) + f(n). Is it possible to apply the MT to it? If not, can the ...
1
vote
0answers
43 views

Arc length using bisection error - root finding methods.

Apologies if this is poorly formatted - it is my first time posting a question. I'm trying to find evenly spaced arc lengths along a function (in this case a sinusoid) using the bisection method. ...
1
vote
1answer
21 views

Hilberts tenth problem over $\mathbb R$ with coefficients in $\mathbb Q$

Consider the following decision problem: Given: An equation $f(x_1, \dots, x_n) = 0$ where $f(x_1, \dots, x_n)$ is a polynomial with variables $x_1, \dots, x_n$ and coefficients in $\mathbb Z$. To ...