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

Lattice Reduction of two matrix

I have two matrices A, B with same number of rows. I want lattice reduction on B. During this reduction, I change rows of A accordingly. That is if i-th row and j-th row in B interchanges, swap i-th ...
1
vote
1answer
104 views

Understanding recursion in λ calculus

In recursion for λ calculus, I was wondering why the following two are equal (λx.g (x x)) (λx.g (x x)) g ((λx.g (x x)) (λx.g (x x))) How shall I understand g ((λx.g (x x)) (λx.g (x x)))? ...
1
vote
1answer
272 views

How do I go about calculating the entropy level of this algorithm?

I have a set of items. These items are (pseudo)randomly placed into buckets. The buckets are ordered and items placed in them are ordered. After all of the items are placed in buckets, the items ...
3
votes
1answer
380 views

Can somebody explain to me how we define an isomorphism between structures?

I was reading this definition from journal article 'fixed-point logics with nondeterministic choice' by Anuj Dawar and David Richerby. On page 505 it says 'Classes of structures are assumed to be ...
12
votes
2answers
2k views

Can someone explain the Y Combinator?

The Y combinator is a concept in functional programming, borrowed from the lambda calculus. It is a fixed-point combinator. A fixed point combinator $G$ is a higher-order function (a functional, in ...
4
votes
1answer
188 views

Gradualness of Polynomial-time Recognizers

Is there a counterexample or theorem for the question below? Examples: Let's look at some examples first to get the feel of it. We'll let $n$ be the length of the input in characters. All the ...
0
votes
1answer
222 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
391 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
196 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
353 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
233 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
887 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
390 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
167 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
3k 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
114 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
441 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
129 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
940 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
1k 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): ...
3
votes
2answers
309 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
239 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
496 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
304 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 ...
17
votes
2answers
15k 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
218 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
177 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
312 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
161 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
106 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
445 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 ...
1
vote
2answers
118 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
449 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
297 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
1k 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 ...
5
votes
2answers
959 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 ...
4
votes
2answers
213 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
144 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
782 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
411 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
967 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
192 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 ...