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

2
votes
3answers
38 views

How can I implement a Deterministic finite automaton which accepts strings having specific words.

I am trying to make a Deterministic finite automaton which accepts those strings having two specific words(either one) anywhere as a substring. The problem is really simple if the characters of the ...
0
votes
1answer
7 views

Moves in a Turing Machine

In a Turing Machine i understand that δ(q,x) is a transition function that results in a Change in ID. What does δ(q, Xj) =(P, y, L) mean.I understand that L stands for move left.Is P the new state ...
0
votes
1answer
33 views

Writing a Context Free Grammar for a language with multiple strings in the language

I have an interest in computing and want to learn more about the actual theory behind it. Context Free Grammar plays a part and I am quite fascinated by it all. However, I came with a language that ...
0
votes
1answer
12 views

Intersection of Turing Machines Languages

Given a Turing Machine A and a Turing Machine B, how can I know if the intersection of the Languages of both Turing Machines is non empty? L(A) $\cap$ L(B) $\neq$ 0
0
votes
1answer
66 views

Different ways to arrange a set of numbers, so X can be seen from the left and Y can be seen from the right

Given an set of unique integers of length N. What are number of different ways you can rearrange the array so that, you can only see X numbers of integers from the left and Y numbers of integers from ...
0
votes
0answers
16 views

Removing null moves from automata

I need to bulid the equal auomaton non-deterministic automaton but without the "epsilon moves" ($\lambda $ is epsison in this case) (The double circle is 'Accept') My try: I don't ...
0
votes
1answer
29 views

Can a subset ever be considered as a member/element of its superset under certain conditions?

For example: Let $\mathrm{S}$ be a 2x2 square matrix. Each element in $\mathrm{S}$, denoted by the term $\mathrm{sector_{\alpha \beta}}$, is itself a set of non-numerical objects (a custom software ...
0
votes
1answer
32 views

Graph theory Euler graph

let $G=(V,E)$ be an undirected graph wheres $deg (v) =p >1$ for all $v \in V$ and also $|V|=2p+1 ,$ I need to show that G and his Complement graph are Euler graphs.... $$$$ I think that i ...
2
votes
0answers
30 views

Equivalence relation on set $X$

Me and my friends were complaining about one of the exercises in discrete math. If there are two equivalence relations $R_1$ and $R_2$ on set $X$. Is $R_{1}\setminus R_{2}$ still an equivalence ...
0
votes
1answer
24 views

Prove : Independent set plus covering number is equivalent to number of vertices in a graph

What is the size of the smallest MIS(Maximal Independent Set) of a chain of nine nodes? AFAIK : In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which ...
1
vote
0answers
14 views

Which research groups use stochastic processes and/or stochastic differential equations in computer graphics/vision?

Some research groups use stochastic differential equations for mathematical image processing. Which research groups do use stochastic processes in general and/or stochastic differential equations in ...
1
vote
0answers
36 views

Covering unit square

Now, I am reading this topic http://mathoverflow.net/questions/34145/can-we-cover-the-unit-square-by-these-rectangles. And do some research on it. Guys, who had written in topics, have said, that they ...
0
votes
1answer
67 views

Graph theory undirected graph problem

Let $G=(V,E)$ be an undirected graph , $|V|=n \ge 3$, n is Even. and $deg(v)\ge (n-1)/2$ $$$$ i need to show that G is an Hamilton graph... im here with about 5 other students... and no one has any ...
0
votes
0answers
27 views

Regular Expression for a Set of Strings of Even Length

Can the language for the set of even strings be represented by L={ε,aa,ab,ba,bb.....} Isnt Epsilon Odd?
0
votes
1answer
15 views

If $L_1$ and $L_2$ are non regular then $L_1 \cup\;L_2\; = L$ can be regular?

I need to prove or disprove with contrast example: If $L_1$ and $L_2$ are non regular then $L_1 \cup\;L_2\; = L$ can be regular I have no idea how to begin, hints and spoilers are welcomed
2
votes
1answer
24 views

Why for the input: 'a' I'm getting 'Accept' in the automata

This is a finite non-deterministic automaton ($\lambda$ same like $\epsilon$) I don't understand why for the input: 'a' (first line) I'm getting 'Accept'
0
votes
0answers
19 views

how solve the recurrence T (n) = T (n-1) + c using substitution method [duplicate]

how we solve this recurrence T (n) = T (n-1) + c using substitution method
1
vote
0answers
23 views

Where does this formula come from?

This is the derivation of formula of Gamma Correction for CRT monitors. I am not finding this in any book or web-site. Books seem to derive this formula in different ways. Can anyone please tell me ...
0
votes
2answers
43 views

Mathematical representation of flood fill algorithm

For school I'm writing a report on the flood fill algorithm used in computing. I was wondering if the flood fill algorithm can be represented mathematically, I've searched all over but cannot find ...
1
vote
2answers
42 views

What is a mathematical term for a non-rectangular matrix/array?

In computer science, we can have a list of lists, and the sublists can have different lengths. In math, is there a concept for such non-rectangular "matrix"? If I am correct, array and matrix are ...
0
votes
1answer
16 views

Show that the problem of deciding whether a Turing machine prints something is undecidable

I am unable to get the logic for showing that the problem of whether a Turing machine prints something is undecidable by showing that the halting problem reduces to it. Please guide me with this.
0
votes
0answers
20 views

State space complexity of $2d$ and $3d$ tic tac toe

So for a 2d tic tac toe game, we know that the space complexity can be represented as follows. A naive upper bound will be $3^9$ as there is $3$ possibilities (X, Y or blank) in each of the $9$ ...
0
votes
0answers
18 views

Sketch the reachability graph for the Petri net model

Petri net for traffic light Sketch the reachability graph for the Petri net model of the two traffic light system shown above. I know the starting is (1, 0, 0) but I'm not sure how to draw it and ...
1
vote
2answers
71 views

Different heuristics to solve the Caesar cipher

I know two heuristics that can be used to solve Caesar cipher, but I am asked a question in my artificial intelligence class to Give three heuristics that might be used for solving Caesar ...
0
votes
1answer
16 views

If I rewrite a grammar to remove ambiguity, will it remain equivalent to the original one ?

For example, I have this grammar E → E + E | E * E | a | b | c It is ambiguity for the case: a * b + c, which have 2 parse tree: E => E + E => E * E + c => a * b + c and E => E * E => a * E + E ...
0
votes
1answer
18 views

Regular Expression definitions, as a rule, what is always true?

If I have two regular expressions $\sf S$ and $\sf T$, what is always true of these? options: Both $\sf(SS \mid T)^\ast$ and $\sf(TSS)^\ast$ are subsets of $\sf(TSS\mid STS\mid SST)^\ast$ ...
0
votes
1answer
16 views

Why is the spanning tree algorithm used for bridge-routing?

In a network of LANs connected by bridges, packets are sent from one LAN to another through intermediate bridges. Since more than one path may exist between two LANs, packets may have to be routed ...
6
votes
2answers
89 views

Polynomials closed under composition

I'm planning on being a TA for a computer science class and I'm reviewing a few things that have slipped my memory. Currently I'm working on this: Show that the polynomials are closed under ...
3
votes
2answers
50 views

Why is triangle $\in P$ (P/NP)

I'm learning about $P/NP$ and my friend used an example in which he said that if you have a triangle in an undirected graph which is basically a set of three nodes in which all pairs of nodes are ...
0
votes
0answers
16 views

$NP^A \neq coNP^A$(Baker, Gill and Solovay theorem)

From Baker, Gill and Solovay theorem we know that there is an oracle $A$ such that $NP^A \neq coNP^A$ Now what can we conclude from this if $A \in P$ or $A \in NP$ ? And correct me if I'm wrong, if ...
0
votes
1answer
48 views

What does $\forall X: A^X \subseteq B^X$ mean?

In Greg Kuperberg's complexity zoology inclusion diagram, there is a color coding based on whether or not $$ \forall X : A^X \subseteq B^X $$ is proven, disproven, or unknown. What does this ...
0
votes
1answer
46 views

Artificial intelligence methods in mathematics

Are there aritficial intelligence methods in mathematics, automatic theorem discovery and proving? Google gives results in the opposite direction - mathematical methods of AI. Are there applications ...
0
votes
1answer
30 views

Complete trail - walk traversing each vertex at least once, each edge at most once

I would like to know the status of the following problem: Given a simple graph, is there a walk traversing each vertex at least once and each edge at most once? (I am asking for a complete trail, a ...
0
votes
0answers
19 views

Tangent Plane of two polyhedron from below in 3D

The convex hull or convex envelope of a set X of points in the Euclidean plane or Euclidean space is the smallest convex set that contains X. A polyhedron (plural polyhedra or polyhedrons) is a solid ...
0
votes
1answer
36 views

Book that covers Counting & Probability basics

My aim is to become sharp in the necessary knowledge of basic probability and counting to follow my studies of Statistics for Computer Science. Right now I found the following book: ...
1
vote
0answers
17 views

How rounding real numbers affect mean

First of all, I am not used to construct mathematical demonstration, so I will discuss my point in a argument based fashion. This is why I am asking to mathematician a more formal and correct way to ...
5
votes
0answers
81 views

partial derivative of a facet normal wrt to one of its vertex

I am struggling to understand the derivation of an equation in a paper (A Bayesian Method for Probable Surface Reconstruction and Decimation, specifically Eqn. 16). Basically they define three ...
2
votes
0answers
8 views

Naive Euclidean algorithm - average complexity?

Suppose I compute the GCD in a rather simple-minded recursive way: $$ \gcd(a, b) = \begin{cases} \gcd(a, b-a) & \text{ if }{a < b}, \\ \gcd(a-b, b) & \text{ if }{a > b}, \\ a & ...
0
votes
0answers
36 views

How to plan a ride by several buses?

Given a source location and a destination location, and an acceptable range of departure times, or an acceptable range of arrival times, and a schedule of available bus routes (e.g. ...
1
vote
2answers
27 views

Converting NFA to DFA (exponential).

I understand how to convert from an NFA to a DFA, and the if there are $n$ states in a NFA there will be $2^n$ states in the DFA (without minimizing). Would someone mind explaining the intuition ...
1
vote
1answer
31 views

Prove the infinite union is not regular

Prove $\bigcup _{i=1}^\infty A_i$ is not regular. We know $A_i$ is regular, but how can prove the infinite union is not regular. I think a counter example would work, but I can't think of any. ...
0
votes
1answer
31 views

Given the postorder sequence 1, 2, 3, 0, 7, 9, 8, 6, 5, 4 of the keys of nodes in a binary search tree, find that tree.

Given the postorder sequence 1, 2, 3, 0, 7, 9, 8, 6, 5, 4 of the keys of nodes in a binary search tree, find that tree. I think i've done this right but i'm not sure.
0
votes
1answer
23 views

How can I write a partial recursive function “maximum(x,y,z)”?

It is quite easy to write a partial recursive function "max(x,y)": 1.substraction1: substraction(x) = if x=0 then 0 else x - 1 @R(z1,i21) 2.substraction2: substraction(x,y) = if x < y then 0 ...
0
votes
1answer
65 views

Language decidability and Post's theorem

I have the following exercise on decidability: Show that the language $L$ is decidable if and only if there exist decidable languages $A$ and $B$ such that $L=\{x\;|\;(\exists y)[\langle x, ...
0
votes
0answers
25 views

Proving correctness for code computing function.

I was solving an exercise from the book "Complexity, computability and languages" which asks: Write a program that computes $f(x)=1 \iff x$ is even, $f(x)=0\iff x$ is odd. I wrote the following ...
0
votes
1answer
57 views

Show the binary search tree that results from inserting elements 10, 14, 11, 9, 4, 2, 12, 16, 7, 5, 8

Question: Show the binary search tree that results from inserting elements 10, 14, 11, 9, 4, 2, 12, 16, 7, 5, 8 (in that order) into an (initially) empty binary search tree. Show also ...
0
votes
1answer
46 views

Master theorem. Particular example I can't understand

I thought that I understood how to use the Master Theorem but apparently I don't. So here it is: ...
2
votes
1answer
50 views

Show a language is regular with Myhill-Nerode Theorem

I understand how to show a language is not regular using Myhill-Nerode Theorem (proof by contradiction), but how do you show the language is regular? Take language $0^*1^*$ for example. I know this ...
1
vote
1answer
73 views

Random walk in a graph

This is a question about random walk from vertex $s$ in a graph (can be directed), which is defined in the following manner: The random variable $X_0$ (whose possible values is the set of vertices) ...
1
vote
0answers
31 views

Numerically robust computation of the mutual information

Given the numerical distributions $p(x,y), p(x|y), p(y|x)$, what is the most numerically robust way of computing $I(X;Y)$? Should one use the formula for $I(X;Y)$ directly? Or should we use either of ...