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

4
votes
1answer
338 views

Decidable? Turing machine runs X steps for certain input?

Question is the following language decidable: {(M)|given input "aaaaa" Turing machine M will perform at least 1295 steps} I would say, yes it is. Just let the Universal Turing Machine count each ...
1
vote
1answer
218 views

Is language L context-free?

Is following language context-free? Alphabet: {a,b,c,d} L = {w | w is not in {aabbc,abc,add}} I think it is: {aabbc},{abc},{add} are all regular. Because of closure properties(Union) R = {w | w ...
3
votes
2answers
306 views

L* regular -> L regular?

If language L* (Kleene Star) is regular, does it imply that L is also regular?
3
votes
1answer
715 views

Turing machine configuration and computation history

These are a series of questions about Turing machines. First, are the number of a given Turing machine configurations (state + tape) countable? Secondly, given that a computation history is a ...
6
votes
1answer
649 views

Are there any known barriers to some approach for solving P vs. NP?

Are there any known barriers to show the following invariant (perhaps by some sort of induction)? Let $\Sigma$ be some finite alphabet with $|\Sigma| \geq 2$, let $M$ be some (deciding) deterministic ...
4
votes
1answer
310 views

Cantor–Bernstein–Schröder theorem and recursion

I am poking on a proof of the subject theorem. Given sets $A_i$ and injections $f_i:A_i\to A_{1-i}$, $i\in \{0,1\}$, theorem defines a bijection $b$ between $A_0$ and $A_1$. $b$ uses an auxilary ...
4
votes
2answers
181 views

Many one and One many reductions

I do not have enough complexity theory background, but I was wondering about the kind of reductions that we normally do to show NP-Completeness. I think all of the reductions that I have seen are ...
1
vote
2answers
274 views

Is this DFA correct

I'm supposed to construct a DFA which accepts { w | w is a word except 'aa' and 'aaa' } Is this the correct solution? The thick line state is supposed to be the end state. EDIT Sry, somehow ...
2
votes
2answers
4k views

Understanding $\epsilon$ transitions in a finite state automaton

I am trying to understand how $\epsilon$ transitions work. From what I've read, when you "go" to a state S that has arrows pointing outwards with $\epsilon$'s in it, you automatically go to those ...
0
votes
1answer
257 views

Question about ambiguity of BNF

The BNF is defined as follows: <S> -> <S>a<S>a<S> | b This is my review question for a quiz, and according to my teacher, this grammar ...
1
vote
1answer
634 views

Independent Set decision problem in P

If P=NP, is there a polynomial-time algorithm $A$ that can decide the $\text{Independent Set}$ decision problem? That is, with an undirected graph $G = (V, E)$ and a positive integer $k$, does $G$ ...
3
votes
3answers
3k views

Proving that $|xy| = |x| + |y|$ being $x$ and $y$ two strings

I am to prove that being $x$ a string and $|x|$ its length, one should have the following property hold true for any two strings $x$ and $y$: $$ |xy| = |x| + |y| $$ with $x, y \in \Sigma^*$. To ...
2
votes
1answer
1k views

Nondeterministic Finite Automata to Deterministic Finite Automata?

I am unfamiliar with the general process of converting NFA to DFA. I have general understanding of the theory, but I don't have the method established. Please help explain the process required to ...
4
votes
1answer
162 views

Help understand $\text{handle}$ in parsing problem

The BNF is defined as followed: S -> aAb | bBA A -> ab | aAB B -> bB | b The sentence is: aaAbBb And this is the ...
4
votes
3answers
1k views

Is this BNF grammar ambiguous?

I have a BNF defined as follow: <S> -> 0 <S> -> 1 <S> -> <S><S> I think this grammar is not ambiguous, but the solution ...
1
vote
1answer
188 views

Need help explain BNF

I have several BNF defined as follow: ...
2
votes
1answer
130 views

Do there exists permutations $\pi_1,\pi_2$ and polynomial size CFG that describe the finite language $\{w \pi_1(w) \pi_2(w)\}$ over alphabet {0,1}?

Do there exists permutations $\pi_1,\pi_2$ and polynomial size CFG that describe the finite language {$w \pi_1(w) \pi_2(w)$} over alphabet {0,1}? Polynomial size in $|w|=n$
3
votes
1answer
101 views

An efficient way to check whether a polynomial (under certain condition) is absolutely equal to zero or not

We have a function $f$ of $N$ variables which is the product of $M$ polynomials: $$f(x_1,x_2,\ldots, x_N) = P_1 \cdot P_2 \cdots P_M.$$ Each $P_i$ is a polynomial of at most three variables ...
2
votes
1answer
81 views

a function of a dependent type, a section, a sheaf

I have defined this simple sheaf. Take $E:set, B:set, p:E\to B$. Let $P(B)$ be a set of subsets of $B$. Let $S$ be the set of sections of $p$. Let $F$ be a contravariant functor from $P(B)$ as a poset ...
0
votes
1answer
59 views

Language complexity from instances of graph

Let $G$ represent an undirected graph, let $a$ and $b$ represent vertices and let $k$ represent a non-negative integer. I have two languages: $L_1 = \left \{ \left \langle G, a, b, k \right ...
6
votes
1answer
636 views

Proof by double induction on strings (SOLVED)

I am truly baffled as to go on to prove this by double induction: http://i.stack.imgur.com/Zvrzt.png (snap shot of question) This question seems rather trivial on first glimpse, however trying ...
6
votes
3answers
779 views

Is learning haskell a bad thing for a beginner mathematician?

Haskell is a programming language which uses some concepts from category theory like functor, monad, etc. My question is: Learning intuitive concepts about category from Haskell will ruin my intuition ...
6
votes
1answer
407 views

Importance of Constructible functions

A function $f$ is called fully time-constructible if there exists a Turing machine $M$ which, given a string $1^n$ consisting of $n$ ones, stops after exactly $f(n)$ steps. Analogously, we can call a ...
1
vote
2answers
149 views

Nondeterminism and computational models

So it is clear than the nondeterministic versions of computational models such as the Turing Machine is equivalent in "power" to the deterministic model. Other than showing this fact, what would be ...
5
votes
2answers
3k views

What is the current status of Vinay Deolalikar's proof that P is not equal to NP

This could be mathematics or computer science, but also statistical physics, so I hope it qualifies for interest :) I am aware that there were reservations about the proof but no fatal flaws. I have ...
3
votes
3answers
268 views

Software/algorithm for the smallest context free grammar describing a set of words?

I am looking for software/algorithm for the smallest context free grammar describing a finite set of words (and no other words). For a single word I found sequitur Related to this seems: given a CFG ...
3
votes
1answer
109 views

Does fixing the number of elements in PARTITION send it in P?

It's possible that this question is trivial and I've overlooked something. Let us impose the following constraint on the well-known PARTITION problem: in all inputs of a new problem the number of ...
1
vote
1answer
282 views

Counting the number of asymmetric graphs on n nodes?

Asymmetric graph is a graph that has only trivial automorphism. Asymptotically, almost all finite graphs are asymmetric. I'm looking for upper bounds and lower bounds on the growth rate of the number ...
1
vote
1answer
283 views

Can a polynomial size CFG describe the finite language \{$w \pi(w)$ : $\pi(w)$ is fixed string permutation, $|w|=n$ is fixed\} over alphabet \{0,1\}?

Can a polynomial size Context free grammar describe the finite language {$w \pi(w)$ : $\pi(w)$ is fixed string permutation, $|w|=n$ is fixed} over alphabet of {0,1}? One case this is possible is when ...
0
votes
1answer
151 views

Problem k-subvector using dynamic programming

Given a vector V of n integers and an integer k, k <= n, you want a subvector (a sequence of consecutive elements of the vector ) of maximum length containing at most k distinct elements. The ...
2
votes
1answer
832 views

Solving a nonlinear system using Groebner basis computations

I have discovered that Groebner basis computations may help in a problem I am working on. However, I am having some very specific problems. First, the literature I have discovered on Groebner basis ...
3
votes
1answer
311 views

Best Practices for Learning Mathematics (especially in the classroom)

What study practices have led you to the best success in learning mathematics (or applied math, or theoretical CS) in the classroom (undergraduate/lower graduate level), especially in courses that ...
14
votes
6answers
2k views

What math should a computer scientist take in college?

I'm a computer science major and like many of us we have to take two additional sciences. These two additional science courses are in addition to three semesters of calculus,two semesters of physics, ...
4
votes
2answers
6k views

What makes a context free grammar ambiguous?

What makes a context free grammar ambiguous?
3
votes
1answer
759 views

Pushdown Automata deriving context free language

I'm trying to understand how you derive a context free grammar (CFG) from a Pushdown Automata (PDA)? I have the following PDA. I believe the following context-free language can be derived.. ...
1
vote
1answer
1k views

Grammar to Chomskys Normal Form eliminating epsilon productions

I've got the following grammar I'm attempting to convert to CNF. S -> T01 | USV | epsilon U -> X V -> S1S | X | 1 X -> 0XS | 0 T -> TV | XT | UTU ...
0
votes
2answers
897 views

How to create a graycode of N bits with a code-agnostic iteration function

I'm posting this as more of a theory/mathematic how-to followup to a stackoverflow question. The non-iterative method for calculating graycode depends on Log2N bytes, to store position information ...
3
votes
1answer
163 views

Help needed on method to use for anomaly detection in Computer Science

I think people here could guide me in solving a problem related to anomaly detection. The term anomaly here refers to some undesired event occurring in the system like a virus infection. I could get ...
0
votes
1answer
1k views

In this Cholesky Algorithm in matlab, what is the abs function doing

We have been told in our homework to implement the following program: function A = Cholesky(A) % Cholesky Decomposition of a Matrix A, so that the resulting matrix L gives A=L*L N = size(A,1); ...
3
votes
2answers
12k views

Implement a program in Matlab for LU decomposition with pivoting

I need to write a program to solve matrix equations Ax=b where A is an nxn matrix, and b is a vector with n entries using LU decomposition. Unfortunately I'm not allowed to use any prewritten codes in ...
0
votes
1answer
81 views

Minimum number of numbers to be inserted in a sequence to transform it into an A.P

Given a sequence of N numbers, how can we find the minimum number of numbers to be inserted to make this sequence to an Arithmetic progression.(we can insert at any position of this sequence) For ...
1
vote
1answer
249 views

Complexity of verifying proofs

My question can be read on many levels and so I welcome answers to any reading. The general question is: What is the computational complexity of verifying a proof? One way of looking at a ...
4
votes
2answers
675 views

Addition on big omega notation

It seems to my uneducated mind that if I have $\frac{n}{k}$ subproblems, each of size $\Omega (k \log k)$, that my overall problem must be at least of size $\Omega (n \log k)$, by the reasoning that ...
9
votes
4answers
8k views

Representing IF … THEN … ELSE … in math notation

How do I correctly represent the following pseudocode in math notation? EDIT1: Formula expanded. EDIT2: Clarification. (a,b) represents a line segment on a 1D line. a <= b for each segment. The ...
2
votes
1answer
71 views
1
vote
3answers
413 views

Can we partition NP-complete problem into finite number of polynomially solvable problems?

I have asked this question on cstheory. Let $\Pi$ be NP-complete problem. Can we partition the set of instances of $\Pi$ into finite number of subsets (subproblems) each of which is polynomially ...
2
votes
2answers
169 views

NP-problem that needs superlinear certificates

In the definition of the complexity class NP, we allow the certificate to be polynomial in the input size. But do we ever need a certificate that is longer than the input? In all the NP problems I ...
3
votes
1answer
221 views

Can a polynomial size CFG over large alphabet describe any of these languages:

Can a polynomial size CFG over large alphabet describe any of these languages: Each terminal appears 0 or 2 times Word repetition {www* | w \in \Sigma *} (word repetition of an arbitrary word w) ...
3
votes
1answer
295 views

Big-oh for function of two variables

Is it true that $O(M^3 + NM^2) \, = \, O(M^3 + N)$, where $M$ and $N$ are variables of the function?
2
votes
1answer
265 views

Restricted read twice BDDs and context free grammars

Several papers give poly-time algorithms for constrained paths on labelled graphs, e.g. [1] Quote: Given an alphabet Σ, a (directed) graph G whose edges are weighted and Σ-labeled, and a formal ...