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
232 views

The way that a regular expression describes a regular language

A formal language is a set of words in some alphabet. It may be defined as being generated by a formal grammar or as being recognized by an automaton. For a regular language, it can also be described ...
2
votes
2answers
417 views

Can a formal language always be generated by a formal grammar?

A formal language is often defined by means of a formal grammar. I wonder for a formal language if there is always a formal grammar that generates the language? Does this answer have something to do ...
0
votes
3answers
197 views

Is a regular expression a string or a set of strings?

Quoted from Introduction to the Theory of Computation by Sipser, a regular expression is defined as: Say that R is a regular expression if R is a for some a in the alphabet $\Sigma$, ...
0
votes
1answer
369 views

Complexity of $T(n)=\sqrt{n}T(\sqrt{n})+n$

I tried to find the complexity of this recursion equation: $T(n)=\sqrt{n}T(\sqrt{n})+n$, by doing couple of iterations and getting a general idea, but I completely got lost. I'd really love your ...
2
votes
3answers
237 views

Analysis of Algorithms: Solving Recursion equations: $\quad T(n)= T(cn)+T(dn)+n$

How can I prove that the solution for the following recursion equation is $\Theta(n)$: $$T(n)= T(cn)+T(dn)+n \text{ for } d,c>0 \text{ and } c+d<1$$ Edit: $cn$ on one side only. What I need to ...
1
vote
2answers
1k views

NP verifier-based definition

I'm a computer science student and I'm having some problem understanding the verifier based definition of NP problems. The definition says that a problem is in NP if can be verified in polynomial ...
3
votes
4answers
413 views

Mathematics necessary for a Master's degree in CS

I'm contemplating doing a Master's degree in Computer Science at night school. What sort of mathematics am I likely to encounter?
8
votes
2answers
169 views

Given $N$, count $\{(m,n) \mid 0\leq m<N, 0\leq n<N, m\text{ and } n \text{ relatively prime}\}$

I'm confused at exercise 4.49 on page 149 from the book "Concrete Mathematics: A Foundation for Computer Science": Let $R(N)$ be the number of pairs of integers $(m,n)$ such that $0\leq m < N$, ...
4
votes
3answers
4k views

How to prove two regular expressions are identical in mathematical way?

I'm currently working on "regular expression" exercises in the textbook ("An Introduction to Formal Languages and Automata"), and the problem that I'm facing is, most of the time, my solution is ...
1
vote
1answer
117 views

Mathematical names of the sets and elements of standard computer numbers

In standard computer arithmetic, there are two sets of numbers. N-bit unsigned numbers. The elements are natural numbers in $(0, 2^N]$. Arithmetic operations is defined as for the natural numbers ...
1
vote
1answer
508 views

why does multiplicatively weighted voronoi diagram (mwvd) with 2 sites create a circle?

I want to understand the structure of a multiplicatively weighted voronoi diagram. I found that the bisector between 2 sites is circle shaped, but couldn't formally ...
3
votes
1answer
130 views

Prove or refute that $\frac{t^a-1}{t^b-1}$ is not a integer if $a \mod b \neq 0$

Hi guys in my last question I got the wrong idea maybe because a poor problem's description or maybe because of my poor English skills. So, anyway I found out the problem requires to be a integer. ...
0
votes
2answers
1k views

Find the DFA for the language $L = \{a^nb: n \geq 0\} \cup \{b^na : n \geq 1\}$

Problem Find the DFA for the language $$L = \{a^nb: n \geq 0\} \cup \{b^na : n \geq 1\}$$ This is a problem from the book "An Introduction to Formal Languages amd Automata 4th edition", ...
3
votes
2answers
204 views

Prove or refute that $\frac{t^a-1}{t^b-1}$ has more than 100 digits if $a \mod b \neq 0$

I'm a computer science student from Mexico and I have been training for the ICPC-ACM. So one of this problems called division sounds simple at first. The problem is straight for you have and 3 ...
4
votes
3answers
2k views

How to compute the transition function in non-determinism finite accepter NFA?

I'm currently teaching myself Automaton using Peter Linz book - An Introduction to Formal Languages and Automata 4th edition. While reading chapter 2 about NFA, I was stuck this example (page 51): ...
4
votes
2answers
321 views

How to get 'rectangular size' of arbitrary circular sector?

Given a circular sector defined by sweeping from a 'start' to a 'stop' angle (see diagram below) and a radius, how do you compute the bounds of the rectangle that fits to the edges of the sector? ...
1
vote
1answer
245 views

Lower bound for the complexity of linear programming

Since it is known that you can sort $n$ numbers by solving a certain kind of linear program - doesn't this imply a lower bound on the complexity of solving linear programs in general via the lower ...
4
votes
2answers
564 views

An “uncountable” Turing Machine?

A proof of the insolubility of the halting problem is a diagonalization, which I'm sure most of you have seen. I am not very familiar with set theory, but it strikes me as similar to Cantor's proof of ...
2
votes
1answer
91 views

Paths with DFA?

My teacher made an example to explain DFA, it was about paths (URL paths), the rules were as follows: ...
1
vote
5answers
354 views

“Plotting” an equation

I have an equation like $$ (x - a)^2 + (y - b)^2 = r^2 $$ that represents a circle. I need to "plot" it very basically with a programming language. Computer graphics coordinate generally use the ...
2
votes
4answers
1k views

First order logic and higher order logics?

I hear that Prolog is based in first-order logic. This makes me wonder, C/C++ are based on which higher order logics? If this question is incorrect, please point out that. and how are these logics ...
19
votes
2answers
18k views

What books do you recommend before 'Concrete Mathematics'?

What book(s) do you recommend before Concrete Mathematics? Is something like "Introduction to discrete Mathematics" enough?
3
votes
3answers
113 views

Why isn't it enough to enforce $w \in A \Rightarrow f(w) \in B$ before allowing a reduction from A to B?

From my textbook, I can see that A language A is mapping reducible to language B if there is a computable function such that for every $w$, $w \in A \Leftrightarrow f(w) \in B$. Now, what I fail to ...
8
votes
1answer
222 views

Homotopy and watershed

homotopy is a new word to me. Upon trying to understand this property, I immediately think of another well-known segmentation algorithm: watersheds. I see that watershed should exhibit some ...
1
vote
1answer
193 views

Does there exists a absolute measure for growth-rate of a function?

In computer science there are many notions of growth-rate of a function. These notions are, however, always relative in the sense that growth-rate of some function $f$ is always relative to some other ...
2
votes
1answer
336 views

Theory of supercategories

Category Theory has enormous utility as language for expressing mathematics, both continuous and discrete. It allows beautiful and succinct expression of that else be clumsy and clutterized. One ...
1
vote
2answers
171 views

Why are regular languages called “regular”?

Why regular languages are called "regular"? Are there any mathematical (formal or not) characterization of that word per se? The word is overused in mathematics in unsystematisable manner so we ...
1
vote
2answers
114 views

Survey Article on Decision Tree Proofs

I'm looking for a survey article on proofs using decision trees. Presumably it would include at least a passing reference to the proof that the lower bound on comparison-based sorting is ...
3
votes
2answers
473 views

Is Halting Problem is decidable for any real world algorithms?

Halting Problem is (theoretically) decidable for such algorithms which termination may be proved in First Order Logic (FOL) because all true statements in FOL are recursively enumerable. It is ...
2
votes
2answers
123 views

Class of linearly parsable languages?

Is there name for class of languages exactly such that their words can be parsed in $O(n)$ by program in conventional Turing-complete language (SML)? (i.e. without backtracking) Any references?
0
votes
1answer
92 views

What is “language of words” means?

Some papers (especially about Nested Words languages) ofter contain term "language of words". What is the difference between "language" and "language of words"?
2
votes
2answers
533 views

Step function for greaterthan

I need to avoid using an if statement that does a $\geq$ comparison, (I'm writing HLSL code for the xbox). I need a function such that $f(x, y) = 0$ when $x < y$ and $f(x,y)=1$ when $x \geq y$. ...
1
vote
1answer
1k views

Proving regular expressions to be equivalent

I'm trying to prove that two regular expressions are equivalent. I mean prove in the rigorous sense of the word (i.e. this is a legit proof). The process is to show that R1 is a subset of R2, and ...
0
votes
1answer
325 views

Complementary language of a context free grammar

First post on Mathematics ;) I'm stucked with a problem related to automata theory / formal grammars. The problem ask the student to design a Pushdown automaton that accepts the complementary ...
6
votes
1answer
2k views

Easy proofs of the undecidability of Wang's tiling problem?

Wang tiles are (by Wikipedia): "equal-sized squares with a color on each edge which can be arranged side by side (on a regular square grid) so that abutting edges of adjacent tiles have the same ...
6
votes
2answers
1k views

Subset sum problem is NP-complete?

If I know correctly, subset sum problem is NP-complete. Here you have an array of n integers and you are given a target sum t, you have to return the numbers from the array which can sum up to the ...
5
votes
2answers
238 views

How do we know if a problem is hardest in NP

I read that the definition of NP-complete is : These are the hardest problems in NP. Such a problem is NP-hard and in NP How do we know if a problem is hardest in NP, and no harder problem ...
0
votes
1answer
149 views

Computational complexity of this algorithm

Consider a function $f(n,k)$ for $n,k\in\mathbb{N}$ and an algorithm that implements that function. The structure of the algorithm is as follows: do some calculations that take $O(n)$ time define ...
4
votes
3answers
974 views

NP hard/complete

I have never been very clear on this concept. Please help: At the end of the day, we should want to identify useful problems for which we don't have polynomial solution so far and only have ...
0
votes
2answers
423 views

How can I determine the cardinality of a set of polymorphic functions?

It seems obvious to me that the set of functions with the signature $\forall A. A \rightarrow A$ is "once-inhabited", i.e. there is only one such polymorphic function which "works" for any set $A$, ...
31
votes
6answers
3k views

Simple “real life” NP-hard problems?

There are many proofs lying around that games like Lemmings or Sudoku or Tetris are NP-hard (generalized version of those games, of course). The proofs, as I recall, are not difficult but not simple ...
3
votes
1answer
1k views

Determine if function is little-o, little-omega or big-theta

Let $f(n) = n^3(5+2\cos(2n))$ and $g(n) = 3n^2+4n^3+5n$. Given these two functions, I must determine the appropriate symbol where the underscore is: $f(n) \in \_(g(n))$ So, first thing to do is take ...
4
votes
2answers
197 views

Showing a property for a set of rewriting rules

Let $\to$ be a relation over the set of binary strings of 0 and 1. $\to$ is defined by the following rules: R1. $x10y \to x0001y $ R2. $x01y \to x1y $ R3. $x11y \to x0000y $ R4. $x00y \to x0y$ ...
4
votes
3answers
2k views

Proof Hampath is NP-Complete

I'm really confused by the proof that Hampath is NP-Complete. In order to prove something is NP-Complete, we can reduce another NP-Complete problem to it. So we want to take 3-SAT and reduce it to ...
6
votes
4answers
4k views

Example of a not recursively enumerable set $A \subseteq \mathbb{N}$

Can someone give me an example if a not recursively enumerable set $A \subseteq \mathbb{N}$ ? I came up with this question, when trying to show, that there exist partial functions $f: \mathbb{N} ...
9
votes
5answers
555 views

Is there any mathematical operation on Integers that yields the same result as doing bitwise “AND”?

I'll provide a little bit of a background so you guys can better understand my question: Let's say I have two positive, non-zero Binary Numbers.(Which can, obviously, be mapped to integers) I will ...
3
votes
1answer
525 views

pickup and delivery driver problem

Let's assume food delivery for multiple restaurants (say 20). There are (say 10) drivers available. Further, let's say we get 100 orders over a 4 hour period to deliver food from these restaurants to ...
1
vote
3answers
236 views

Algorithm to tell if a partial recursive function is 0 everywhere

Is there a (partial) recursive function that tells me, if a partial recursive function encoded by the number $c$ is the constant zero function ?
0
votes
1answer
174 views

Question about the “source code” of a recursive function

How can I show, that for every recursive function $f: \mathbb{N} \rightarrow \mathbb{N}$ we have a number (source code) $c$ such that $\forall x \in \mathbb{N}: f_U (c,x)=f_U (f(c),x)$, where $f_U: ...
3
votes
1answer
396 views

Partition a square into sub-rectangles with restrictions

Is there a method to generate all partitions of given square by using $n$ vertical and $n$ horizontal lines into sub-rectangles under the following restrictions? 1- No vertical line crosses any ...