# Tagged Questions

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 ...

24 views

### Floating point numbers

In a certain computer represents numbers in base2, if the distance between 7 and the next largest floating-point number is $2^{-12}$. What is the distance between 70 and the next largest floating ...
19 views

54 views

### Turing Machine & Recursively enumerable languages. [closed]

Suppose Turing Machine(TM) M and language L. L = { "M" | M has as input strings which $∈$ $\{0,1\}^{*}$ and terminate at a maximum of $512^{512}$ steps} Is L a recursively enumerable language?
54 views

### Hamiltonian circuit in at least one component

I'm having trouble proving that the problem stated in the title is NP-complete, specifically by reduction from Hamiltonian circuit. Intuitively it's clear - Hamiltonian circuit in one graph is NP-...
34 views

58 views

### Counting divisions of an $n \times n$ grid [duplicate]

I'm looking for an efficient way to count the number of ways $D_n$ to divide an $n \times n$ grid into four (possibly empty) regions: top left, top right, bottom left and bottom right, such that no ...
53 views

### Identify inherently ambiguous languages

Which of the following languages is/are inherently ambiguous languages? $L_1=\{a^nb^nc^m|m,n\geq0\}\cup\{a^nc^c|n\geq0\}$ $L_2=\{a^nb^nc^m|m,n\geq0\}\cup\{c^mb^na^n|m,n\geq0\}$ My attempt: A ...
55 views

### $L\in P$ prove that $L^*\in P$

I have that question that looks kinda easy at first but it is quit hard. Let $L\in P$ prove that $L^*\in P$ (L is a language and P is the class of all problems which can be decided by a ...
14 views

### Finding heavy independent sets

What are some good algorithms for finding maximum weight independent sets in a graph with vertex weights?
21 views

### Convert double precision number to rational fraction plus exponent

I have a double precision quantity (either pixels per cm or pixels per inch) that gets converted into pixels per meter. I then need to convert this number into a rational fraction, with numerator and ...
35 views

### Is the language regular

We have to check, if the given two languages are regular or not. L={w |each prefix of w has more 0 than 1} L'={w|w has a prefix with more 0 than 1}. I tried something like this: If L regular, ...
32 views

21 views

### Red-black tree insert

I'm currently trying to figure out this exercise (sorry for link to image, it's for the red-black trees): http://i.imgur.com/IKMCkVf.png And I do know that the correct one is number three from the ...
22 views

### For formal languages $U,V \subseteq X^{\ast}$, what is $\min(U\cdot V)$

Let $L$ be some language, and consider the operator $$\min(L) := \{ u \in L \mid \mbox{no proper prefix of u is in L} \}$$ where a word $u$ is called a prefix of $w$ if it is an initial segment ...
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 ...
14 views

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 ...
28 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. ...
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 ...
36 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 ...
98 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 ...
34 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 ...
61 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(...
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 ...
24 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 ...
28 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 ...
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: ...
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?
45 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 ...
### 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 \$...