# Questions tagged [mathematical-foundations]

Questions about the relation of (subfields of) computer science to the relevant mathematical foundations and their application.

87 questions
Filter by
Sorted by
Tagged with
342 views

### Can you operate on and draw conclusions on functions described asymptotically?

This question is homework based (not using actual problem though)! Say you have a function described as: $$f(n) \in O(2n^2) \, .$$ Can you then go on the treat this as: $$f(n) = 2n^2$$ and ...
942 views

### Minor Mistake in Computability, Complexity, and Languages?

In the book Computability, Complexity, and Languages (2nd edition), Martin Davis writes in chapter 1 (Preliminaries), section 2 (Functions): A partial function on a set $S$ is simply a function ...
245 views

### Set notation of the set of all strings

How do I present the complement using set notation? I guess it has to be shows with universal set - {aa,bb} but I do not know how to represent the universal set in ...
35 views

### physical significance of membership function greater than one

In fuzzy logic, when we associate an element with a set, we usually do it in terms of membership grade which suggests the "belonging" of this element to the set. Membership grade value 0 means that ...
275 views

### Are numbers types and what is “Number”?

I was pondering about what are the numbers. It seems like a number is data type. I mean, like Maybe in Haskell. Because, for instance, one on its own means nothing for me. However, one apple tells me ...
237 views

### How Types avoids Russel's Paradox?

I gone through the Russel's paradox. From Wikipedia : According to naive set theory, any definable collection is a set. Let R be the set of all sets that are not members of themselves. If R is ...
181 views

### Solving inhomogeneous recursion using quadratic particular solution

I am interested in solving recursions and while I was trying to solve this one: $a_n=a_{n-1}+4n-3$ I ran onto a problem, I don't see how to find an explicit solution using standard inhomogeneous ...
661 views

### Why is the zero-th power of the empty set {ε}?

It has been asked before why $\emptyset^\star=\{\epsilon\}$. The answer boils down to $\emptyset^\star$ being defined as $$L^\star = \bigcup_{i=0}^\infty L^i,$$ where a word in $L^i$ is the ...
2k views

### Predicate Logic Notation: What does a “dot” mean?

What does a dot (.) mean in predicates? $\forall a \in A. \exists d \in D. H(a,d)$ Especially, how is the above different to $\exists d \in D. \forall a \in A. H(a,d)$ I've never seen this used ...
88 views

### What kinds of problems are modeled by a recursive definition of a set of strings?

Given this definition: The set $\Sigma^*$ of strings over the alphabet $\Sigma$ is defined recursively by: BASIS STEP: $\lambda \in \Sigma^*$ (where $\lambda$ is the empty string) RECURSIVE ...
148 views

### Help in understanding how to apply nonlinear function in hashing

Can somebody help in brainstorming how to apply the map as a hashing function? I am aware that chaos is used in cryptography but I fail to understand how to apply it. Most popular hashing techniques ...
887 views

### What mathematical background is enough to go through the entire Knuth's TAOCP?

I am an undergrad. I can do mathematics fine and am a lot more interested to explore. I turned towards TAOCP as it is highly mathematically oriented so as to excel at maths and programming at the same ...
51 views

### What Does The Notation of Union Over K represent?

I am currently studying about polynomial time in Comp Theory. The definition for polynomial time given in my textbook as follows: $$P= \bigcup_{k}TIME(n^k)$$ I have not seen the Union over k notation ...
367 views

### How to read 'max min' and 'min max'?

Here is an exercise I came across while studying MaxFlow / MinCut and I'm rather stumped: Designate $G = (V, E)$ as an undirected graph that has at least two vertices. Every edge $(e)$ on this ...
45 views

### Reference Request: Overlaps between complexity theory and dynamical systems?

Per Wikipedia: In mathematics, a dynamical system is a system in which a function describes the time dependence of a point in a geometrical space. Examples include the mathematical models that ...
2k views

### What is the role of mathematics in programming?

I am almost totally uneducated in programming and computer science in general, though I am really fascinated by these topics. I read that mathematics is important in programming and that nowadays many ...
84 views

### Describe data structure using equations

Good afternoon. At work I'm currently developing a system which takes user input (well structured) and then stores it in memory to do some processing. The input is basically a dataset formed by ...
90 views

### What are functions called that yield the same result when applied to one of their result values

Suppose one of the following holds for all x, or all y, or all z: ...
11k views

61 views

### How to read this inductive language definition?

A language $L$ is defined recursively according to the following rules: $λ ∈ L$ If $w ∈ L$, then $bw ∈ L$ and $waa ∈ L$ I am not sure if strings from this language should mix from this definition. ...
170 views

### How to expand 2D graphic and functions to 3D?

So I have a program that enables the user to draw 2D-objects. To rotate them, to move them, and so on, all in 2D. I want to expand the 2D objects and functions to 3D which I don't expect to be too ...
33 views

### How much calculus do you actually use (not counting use of a graphing calculator)? [closed]

I'm wondering if it's worth it to pursue some deep study into calculus. Already, I have some familiarity with derivatives, limits, and integrals. Though, I also have a graphing calculator that's ...
66 views

### MAP estimation (for stationary iid gaussian environment)

This is my first post, and have been self studying Haykin's Neural Networks and Learning Machines book. I'm not sure if this is a typo or if I'm doing something wrong, but I've been stuck on a ...
134 views

### Right equivalent elements arising in the proof of the Schützenberger Theorem

As a part of my Bachelor thesis in computer science I should review the proof of the Schützenberger Theorem (which was given by M.P. Schützenberger himself $^{}$). My question arises on page 193 in ...
3k views

### What are Markov chains?

I'm currently reading some papers about Markov chain lumping and I'm failing to see the difference between a Markov chain and a plain directed weighted graph. For example in the article Optimal state-...
5k views

### What parts of linear algebra are used in computer science?

I've been reading Linear Algebra and its Applications to help understand computer science material (mainly machine learning), but I'm concerned that a lot of the information isn't useful to CS. For ...
98 views

### What do we call a function that outputs 0 on half and 1 on the other half of all inputs?

I have a Boolean function that outputs a one on half of its inputs and outputs a zero on half of its inputs, the inputs are assumed to be coming from the uniform distribution. Another way of saying ...
136 views

### What is the significance of the following equation in computer vision?

Say I have a set of sample measurements of a one dimensional curve in the image plane $f(x)$. What is the purpose of minimizing the following functional E(S) = \int \left[\lambda(S''(x))^2 + (f(x) - ...
359 views

### Terminologies of “Process calculus” and “Process algebra” [duplicate]

In the literature, the terms of "process calculus" and "process algebra" are often interchangeable. Meanwhile, it confused me. My questions are: Are there formal, standard, and widely-accepted ...
797 views

### Applications in Computer Sciences of Partition Functions

A partition function computes the number of ways an integer $n$ can be represented as the sum of $m$ other integers. For some value $n$, we have a partition function $p(n)$. These were studied ...
104 views

### Matrix usage in CS [closed]

I'm studying a major in CS. I'm interested in taking a few extra courses, specifically math to improve my knowledge as future computer scientist. Right now I'm thinking to take Matrix Fundamentals ...
47 views

### Syntax checking expressed mathematically

1) Set B is the finite set of all rules for a particular programming language. 2) Set A is the infinite set of all valid strings of that language and is defined by Set B. I'm having a problem ...