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
2answers
48 views

How do I use L'Hopital's rule to determine if $\log^kN$ is $o(N)$ for any constant $k$?

How do I apply L'Hopital's rule to see if $\log^kN$ is $o(N)$ (small $o$) for any constant $k$? I understand I should keep finding the derivatives of both functions and stop if I can clearly identify ...
1
vote
1answer
60 views

How to encode a list of integers, how to find an arithmetical formula for a sequence?

I have the following list of integers : $$t={0, 15, 73, 27, 73, 105, 25, 65, 26, 8, 84, 72, 15, 73, 27, 73, 105, 25, 65}$$ And I want to find a function or (an expression) such that $f(k)$ is always ...
1
vote
0answers
21 views

If $T$ is a set, $P(x)$ denotes x is a hard worker and $D(x)$ denotes that $x$ is a worker, how to translate the following to English sentence?

So $T$ is a set of workers and materials in a tower, $P(x)$ denotes that $x$ is a hard worker and $D(x)$ denotes that $x$ is a worker $\forall x \in T: [D(x) \rightarrow [\exists y \in T: P(y)]]$ ...
0
votes
1answer
17 views

String recursive definition corner case

I need your assistance with a corner case of this problem: Find a recursive definition for the strings of odd length that start with "a" and end with "b" over the alphabet $\Sigma$={a,b}. I've ...
1
vote
1answer
33 views

Converting an NFA to a DFA

I am trying to convert this NFA to DFA: So I built the power automata, and this is what I got: This should be the answer: I don't understand where am I wrong since ...
0
votes
0answers
30 views

recursively enumerable sets closed under concatenation

I'm trying to show the set of all recursively enumerable sets is closed under concatenation. I'm trying to use the definition of recursively enumerable sets to construct the argument. I believe that I ...
2
votes
0answers
73 views

How to generalize “Seven trees in one” to labelled/colored trees?

In the famous paper Seven trees in one, Andreas Blass showed that there is "a particularly elementary bijection between the set $T$ of finite binary trees and the set $T^7$ of seven-tuples of such ...
0
votes
1answer
29 views

Big-O complexity of $2t(\frac{n}{2}) + n^3$

I'm trying to determine the Big-O complexity of the listed equation and want to know if my approach is valid. I tried using the Master method. It appears to be a case $3$ type problem to me, where ...
0
votes
0answers
36 views

Statistical Analysis of an AI Solving Raven's Progressive Matrices

I need to build an artificial intelligence capable of solving some simple Raven's Progressive Matrices. The gist of it is that you are given an analogy "A is to B as C is to blank" and numerous ...
0
votes
1answer
13 views

K-Map multiple representations

I have a K-Map for a given function and need to figure out the minimal form. This map involves don't-cares. My question is: Do I need to use the don't-cares in my minimal form. I will show you why I ...
0
votes
1answer
35 views

Induction on String? (automata related)

Honestly, all I know about mathematical induction is as follow: prove $P(0)$ - base step for all $n \ge 1$, prove $(P(n − 1) \rightarrow P(n))$ - inductive step Prove the following claim by ...
0
votes
1answer
41 views

Counterexample for the reverse implication of Rice's theorem

Here is the version of Rice's theorem I use: Rice's first Theorem: For every non-trivial, language invariant property $P$ of a set of Turing machines it holds that the set $$\{M | P(M) \}$$ is ...
0
votes
1answer
42 views

Sum-of-products for a function

I am not quite sure if I am understanding this correctly or not. Here is the problem: "Find the simplest sum-of-products form for the function $f$ using the don't-care condition $d$, where $f = ...
0
votes
1answer
12 views

Substituting functions into other functions in computability, need help with Cutland

I'm working my way through the Cutland text on computability and I'm having a little trouble understanding exactly what he's saying in regards to substituting functions into other functions (if you ...
0
votes
0answers
70 views

A good primer for Concrete Mathematics?

I've been watching MIT's Mathematics for Computer Science, from Fall 2010 whilst reading Concrete Mathematics. Honestly the topic seems like a hodgepodge of ideas. I can follow about 2/3 of the ...
1
vote
1answer
57 views

Question about deterministic finite automaton and accepting states

For $n \in \mathbb N$, an "$n-$DFA" is an automaton with exactly $n$ accepting states. Let $\Sigma=\{0,1\}$. Prove that the set of the languages that can be accepted by "$1-$DFA" is a subset of the ...
1
vote
1answer
73 views

Question about deterministic finite automaton (DFA) [closed]

For $n \in \mathbb N$, an "$n-$DFA" is an automaton with exactly $n$ accepting states. Let $\Sigma=\{0,1\}$. Prove that the language $\mathcal L=\{0,00,0000\}$ cannot be accepted by any $2-$DFA.
3
votes
0answers
59 views

Is there a better representation than p-adics for exact computer arithmetic?

I stumbled across Quote notation and went hog wild. But when I stumbled on a technical detail I received a very discouraging comment: I think those authors may have been a bit short-sighted, ...
2
votes
4answers
38 views

O(n) of given code

sum = 0 for (i = 0; i < n; i++) for (j = 0; j < i * i; j++) for(k = 0; k < n; k++) ++sum Here is my work The outer most loop: ...
0
votes
1answer
28 views

Describe this language (Context Free Grammar).

Below we have a BNF grammar defined by grammar G(N, T, P, S), N={S, C}, T = {a, b, c} and set of productions rules are: S -> S a S b S | S b S a S | C S | S C | Epsilon C -> c C | Epsilon Epsilon - ...
0
votes
1answer
31 views

Context Free Grammar for unsigned real numbers

Construct Context-free Grammar for unsigned real numbers with coma. Each number has the same number of digits before the decimal and after decimal. Example: 0,0; 0090,1117; 1,9; are correct, but ...
1
vote
2answers
41 views

Context Free Grammar for integers

Construct Context-free Grammar for integers. Integer can begin with + or - and after that we have non-empty string of digits. Integer must not contain unnecessary leading zeros and zero should not be ...
0
votes
0answers
24 views

C /matlab/ Algorithm for monotonicity of Ploygon

is there any easy and understand able algorithm to check the monotonicity of random polygon and also help me to code in which language(c or matlab) is beneficial to code the algorithm
0
votes
1answer
30 views

What is the monotonicity of a polygon? [closed]

What is the monotonicity of a polygon and why is it necessary to check the monotonicity?
2
votes
1answer
71 views

Relationship between $L^1$ norm and sparsity

I'm doing some research in the field of sparse representation and sparse modeling. I have two variables and their $L^1$ norm is calculated to make comparisons. As I take it the smaller the value of ...
1
vote
1answer
33 views

Load balance N customers over K servers with different capacities

Let's say we have N customers that supply a stream of requests, but each customer i supplies different number of requests per minute - $R_i$. All requests are identical in terms of the amount of ...
3
votes
1answer
75 views

How do computer programs find roots of high-degree polynomials?

My question is motivated by curiosity about the optimization of high-degree polynomial functions. Let's say your experiment data are modeled by a non-trivial 15th degree polynomial. Taking the ...
0
votes
2answers
72 views

Prove correctness of the following algorithm for computing Fibonacci numbers [closed]

I am a student studying for my BS in Computer Science. We recently got asked this question in on of my class and with no book to reference I am going to ask it here for a little help. I know I will ...
0
votes
1answer
34 views

Pumping lemma for two words that “completely different”

Let $"x"$ and $"y"$ be a words, we will say that two words are "completely different" if for all $1\leq i\leq |x|$ the $i$ letter in $x$ diffrent from the $i$ letter in $y$. Prove that the ...
1
vote
1answer
56 views

Perturbation of roots in Wilkinson's polynomial

I am studying numerical analysis. When I read the online definition I found on this paragraph: Suppose that we perturb a polynomial $p(x) = Π (x−α_j)$ with roots $α_j$ by adding a small multiple ...
1
vote
0answers
21 views

Converting CFG to PDA for $S\to aSd|aBd\\B\to bBc|\varepsilon$

I need to build a pushdowm automata for the context-free-grammar $$S\to aSd|aBd\\B\to bBc|\varepsilon$$ My attempt: I'm not sure if my attempt is correct or not.
2
votes
1answer
57 views

Using Rice's theorem to prove undecidability of $A_{TM}$

Can you use Rice's theorem to prove that the acceptance problem is undecidable? Wikipedia says that it can be used to solve the Halting problem too but I can't see how that works either. Here is the ...
1
vote
1answer
50 views

From a set of rules, derive the implications?

I've only just become interested in this domain, so sorry if I'm not using the correct terminologies. What I want is the following: Say I have a set of rules (or constraints), I want to derive some ...
3
votes
1answer
225 views

How to show that a function is computable?

Is the following function $$g(x) = \begin{cases} 1 & \mbox{if } \phi_x(x) \downarrow \mbox{or } x \geq 1 \\ 0 & \mbox{otherwise } \end{cases}$$ computable? Please note that $\phi_i(x) ...
0
votes
1answer
106 views

How to find an index of a computable function?

Is there an index $i$ such that $\phi_{p(i)}(0) = i + 2$, for a total computable function $p$? I know about the s-m-n theorem and fixed point theorem, and how to apply them to some basic ...
1
vote
1answer
112 views

How to argue that a set is recursive or recursively enumerable?

I have the two sets listed below, and I want to argue whether each of them is recursive, recursively enumerable or neither recursive nor recursively enumerable. the set $A = \{ i | ...
1
vote
1answer
120 views

Structural induction on binary trees

I have some problems understanding structural induction, maybe because it is such a rigorous way of thinking, so I don't really know where to start here.. This is taken from our Algorithms course and ...
0
votes
1answer
47 views

Binary subtraction with borrowing vs. 2's complement

Consider the following two binary numbers which are using sign-magnitude representation. Therefore, both are positive numbers. ...
0
votes
0answers
34 views

how to generate parity check matrix for a non-systematic generator matrix?

Introduction: Suppose $C$ is an $\left [ n,k \right ]$ code. Let $I_{k}$ be the $k\times k$ identity matrix. Let $P$ be a $k\times \left (n-k \right )$ matrix. Then, $\left ( I_{k} | P\right )$ is ...
0
votes
0answers
29 views

If $f(n) = \Theta(n^{\log_b{a}}\lg^k{n})$ where $k \ge 0$ , then the master recurrence has solution $T(n) = \Theta(n^{\log_b{a}}\lg^{k+1}n) $.

I'm working through problems to the book "introduction to algorithms". I'm going through the section on the master recurrence and have been running into some roadblocks. I found a solution to the ...
2
votes
1answer
14 views

Closed form expression for $n_j$ defined by $n_j=\lceil n_{j−1}/b\rceil$ clarification

I came across this answer to this question: Closed form expression for $n_j$ defined by $n_j=\lceil n_{j-1}/b \rceil$ I was hoping someone could clarify the following step: $q−1 \leqslant ...
1
vote
3answers
195 views

Isomorphism of Non-Symmetric Matrices

$A, B$ are non-symmetric matrices of dimension $m \times n$ where $m=n$ or $m \neq n$. Example: An example of $6 \times 3$ non-symmetric matrix is $$ \begin{pmatrix} 1 & 0 & 0 \\ 0 & ...
0
votes
1answer
28 views

Free context grammar for $\mathscr{L_2}=\{0^i1^j2^k|i,j,k\geq0,i+j=2k\}$

I need to bulid a free context grammar for $\mathscr{L_2}=\{0^i1^j2^k|i,j,k\geq0,i+j=2k\}$ My try: Let denote $T_{x}$ for $k=x$ $$S\to T_{0,1}|T_2\\T_{0,1}\to\epsilon|002|112|012\\T_2\to ...
3
votes
1answer
47 views

Free context grammar for $\mathscr{L_1}=\{a^{3n}b^{5n}|n\geq0\}$

I need to bulid a free context grammar for $\mathscr{L_1}=\{a^{3n}b^{5n}|n\geq0\}$ My try: $$S\to N_0|N_1|N_2\\N_0\to \varepsilon\\N_1\to aaabbbbb|N_2\\N_2\to aaaN_1bbbbb$$ I'm not sure if ...
1
vote
1answer
23 views

Analysing a context-free grammar

Let: $$S \to AC \mid BC\\ A \to aAb \mid aA \mid a\\ B \to aBb \mid Bb \mid b\\ C \to Cc \mid c$$ I need to find if: the word $aabbbcc $ is in the grammar, and if so to write a very left series, ...
0
votes
0answers
52 views

Two's complement involving binary numbers [Single-precision floating point number]

Given the following bit pattern: 0010 0100 1001 0010 0100 1001 0010 0100 What decimal number does it represent, assuming it is a single-precision floating point number?
1
vote
1answer
466 views

Coloring problem on directed graph

Let $D=(V,E)$ a directed graph. How to color nodes of $D$ in white and black such that: No two white colors are adjacent, and For each black node there exists at least one white node which is ...
1
vote
1answer
95 views

A function given a string ( a program) accepts it if the next program which halts does so in an odd number of steps… is it turing computable

A function which given a string returns 1 if the next program halts with an odd number of steps and 0 otherwise. Is this function computable f(s)=1 if w halts in odd number of steps where w>s and ...
0
votes
1answer
65 views

Prove that this function is primitive recursive?

Let $g : \mathbb{N} \rightarrow \mathbb{N}$, $n\mapsto$ the $(n+1)^{th}$ natural number which is not prime. I have to prove that $g$ is a primitive recursive function. My attempt is by minimization ...
0
votes
2answers
72 views

Is this integral less than infinity?

Assume the following integral: $$ \int\limits_{-\infty}^{\infty}\frac{f\left(x\right)} {BB\left(\lceil abs\left(x\right)\rceil\right)}\mathrm{d}x $$ Where $f\left(x\right)$ is any computable ...