Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [notation]

Use this tag whenever you have a question about what some particular symbol/notation means.

0
votes
0answers
32 views

Is my interpretation of the expression on the expectation is a correct one? [migrated]

Consider the following expression $$E_{x\sim p_{data}(x)}[ f(x) ] $$ I am understanding it as 1) if X is a collection of a discrete random variable $(X_1, X_2,......, X_n)$, and x is generated from ...
1
vote
0answers
45 views

What is this weird gate?

This came from a picture of something that I'm supposed to make, and I can't find it in the program I'm supposed to use (LogicWorks). It looks like it 'not's only one of its inputs, but that doesn't ...
1
vote
1answer
27 views

What is the equivalent of the integers symbol Z for n bit only integers?

We refer to the set of all integers as $\mathbb{Z}$. Now suppose we have a set of integers that can be held within a computer variable of $n$ bits width. Clearly they can only be of $2^{n}$ range, ...
1
vote
1answer
40 views

Can the notation for polynomial reduction, A ≤p B be reversed in computability theory?

I don't know this is a proper question on this forum but I was reading about computability theory and I saw the reduction concept and its notation like this: $A \le_pB$. I just wanted to know is this ...
5
votes
2answers
2k views

Why do ¬, ∀ and ∃ have the same precedence?

I thought the order of precedence of operators and quantifiers was arbitrary, but I don't really understand why those three have the same "strength" in relation to other operators (e.g., ¬ will have ...
1
vote
1answer
143 views

What is the Haskell-style type signature called (i.e., who is it named after)?

A type signature in Haskell is written in the following format: functionName :: arg1Type -> arg2Type -> returnType There's a (hyphenated, after a person or ...
0
votes
0answers
27 views

Did Menezes et al. switch the letters $\mu$ and $\lambda$ in Floyd's cycle detection note 3.8?

The letters $\mu$ and $\lambda$ are usually used to represent, respectively, the length of the tail of the graph and length of the cycle in the graph. But Menezes on note 3.8, page 91 (or PDF-page 6),...
2
votes
1answer
135 views

How I can find all equivalence classes by Myhill-Nerode?

first of all I'm sorry for my bad English and second I'm sorry for my mistakes of understanding the following topic, I still going to school and learning this for interest. The topic is Myhill-Nerode ...
1
vote
1answer
53 views

Constructing a new graph. G'. What does it mean v ∈ S_{i+1}?

John lives in a city whose streets has the same length. His apartment is located at a specified node H. John need to do his errands where he visits each of k different shop in order. However, each ...
0
votes
2answers
41 views

Terminology for worst-case N-complexity on $O(1)$ insert after amortisation

Normally, when discussing amortisation and worst-case complexity, amortisation negates the worst-case scenarios, and the BigO describes the average for the operation (the way it's used in interviews ...
46
votes
10answers
11k views

O(·) is not a function, so how can a function be equal to it?

I totally understand what big $O$ notation means. My issue is when we say $T(n)=O(f(n))$ , where $T(n)$ is running time of an algorithm on input of size $n$. I understand semantics of it. But $T(n)$ ...
1
vote
1answer
32 views

What is the meaning of max() in intro. to algorithms?

I'm reading chapter 3(growth functions) of CLRS and in giving an example of proving theta for a standard quadratic function the book gives the following value for $n_0 = 2 \cdot max(|b|/a, \sqrt{|c|/a}...
0
votes
2answers
268 views

Clarify the steps: what happened in this mathematical modelling of TSP?

Source: http://examples.gurobi.com/traveling-salesman-problem I don't get this part: (look at the source) $$\sum_{i,j\in\{1,2,3\},i\neq j} x_{ij}=3>2=|\{1,2,3\}|-1$$ I get that $x_{ij}$ is ...
1
vote
1answer
108 views

How the language $\{a^nb^mc^nd^m | n \geq1, \ m\geq1\}$ is used to check whether formal and actual parameters are equal?

How does the language $L=\{a^nb^mc^nd^m \mid n \geq1, m\geq1\}$ abstract the problem of checking that the number of formal parameters in the declaration of a procedure agrees with the number of actual ...
0
votes
0answers
12 views

How to denote a graph class which allows only $k$ instances of a certain induced subgraph?

Suppose that a graph class $\mathcal{C}$ is defined as follows: A graph $G$ belongs to $\mathcal{C}$ if, and only if $G$ is chordal, but has at most $k$ $5$-cycles. I am aware that the ...
4
votes
1answer
21 views

In ISGCI, unit interval graphs are denoted as ($C_{n+4}$,$S_3$,claw,net)-free. Is this an accurate notation?

When I search unit interval graphs in ISGCI, it says that the unit interval graphs (UIG) are equivalent to ($C_{n+4}$,$S_3$,claw,net)-free graphs. I am confused about the definition of an $S_3$ graph....
1
vote
1answer
78 views

Does big-Oh notation in optimization follow the same convention as in CS?

I first learned big-Oh (little-Oh, big-Theta.....) complexity for growth of functions using CLRS in a computer science class. Now I am doing a project on optimization. In our optimization class, we ...
3
votes
1answer
181 views

Properties of Reverse Polish Notation expressions that are algebraically invariant

The RPN expressions a b + c * and f d e + * are algebraically equivalent, though the names of the variables are different ...
1
vote
2answers
58 views

Is $n^3$ an asymtotically tight bound of $(n^{2.99}).(\log_2n)$? How? [duplicate]

Is $n^3$ an asymtotically tight bound of $(n^{2.99}).(\log_2n)$? If so then how?
1
vote
1answer
48 views

$\tilde \Omega$ for division by logarithmic factor

Is $\Omega \left(\frac{n}{\log{n}} \right)\subset \tilde\Omega(n)$?
8
votes
2answers
1k views

Double exponentials vs single exponentials

Here are four tenets I cannot reconcile: Double exponential time algorithms run in $O(2^{2^{n^k}})$ time with $k \in \mathbb{N}$ constant Exponential time algorithms run in $O(2^{n^k})$ with $k \in \...
0
votes
1answer
83 views

Convert for loop into math sigma notation

Have some code (written in C), need the equivalent notation for mathematics. Is it possible using if-statements and sigma notation for this, and if so, how? ...
4
votes
2answers
973 views

Understanding the Reasoning Behind These Typing Rules

So the expression $\Gamma \ \vdash \ e:\sigma$ states that under assumptions $\Gamma$, the expression $e$ has type $\sigma$. Then we have the following rules: \begin{array}{cl}\displaystyle {\frac {x:...
0
votes
1answer
53 views

What does $\overline{L}^*$ signify?

Suppose that $L$ is a language. What does $\overline{L}^*$ signify? Is $\overline{L^*}$ the same as $(\overline{L})^*$?
4
votes
3answers
146 views

Meaning of the notation Typ := TVar | (Typ → Typ)

In the paper "introduction to type theory" by Herman Geuvers, it states the following definition for the type theory of propositional logic (I've added "convention 2" just for reference): Given ...
5
votes
1answer
103 views

Is there a formal difference between $f:X \to X$ and $f\in X \to X$?

We can denote by $X\to X$ the set of all functions from $X$ to $X$. Therefore, we can use the following statement to say that $f$ is a function from $X$ to $X$: $$f\in X\to X$$ But we usually state ...
2
votes
2answers
42 views

shortest notation for “set of all maps from $A$ to $B$”?

I usually write the following: $$\{m| m:A\to B\}$$ Is there a more succint notation?
6
votes
0answers
91 views

Where did our present regex notation originate?

First question, and my apologies if it is off-topic! This question suggests to me I may not be totally off-base. Where did our present regex notation originate? I am particularly wondering how <...
1
vote
1answer
32 views

Syntax of recurrence formula not clear

I have this task for Analysis of Algorithms module in university $$ \begin{align*} W, V &= \{v_1, v_2, v_n\}, S = \{s_1, s_2, s_n\}\\ G(W) &= \max~_{i:w_i\leq w} ~\{G(W-s_i) + v_i\}, G(0)=0\\...
0
votes
0answers
39 views

Banker's algorithm

I have a question regarding the banker's algorithm step 2. When it says the Need[i] <= work. Need is an n * m matrix and work is a vector of length m. I want to know what Need[i] <= Work means. ...
2
votes
1answer
126 views

What does $|w|$ mean in the statement “ $|w|$ where $w \in L \subset \Sigma^*$”?

In my assignment I find these symbols: $|w|$ where $w \in L \subset \Sigma^*$ I believe it means the lexikografic value of a word, but I am not 100% certain. Let me phrase my question this way: ...
0
votes
1answer
42 views

How to represent a map data structure mathematically

Wondering how to represent a map object such as the following mathematically: var foo = { a: 10, b: 'bar', c: true } You could say that it was a function ...
2
votes
1answer
26 views

Notation for field access in Algorithm

While writing array index in an algorithm $a[i]\gets v$ is conventionally used. Is the notation $a_{i}\gets v$ also used ? If the algorithm uses struct or ...
1
vote
1answer
41 views

Notation for expressing function call count during a program run

Which notation can be used for expressing how many times that function or subroutine called during a run of a program? Example program pseudocode: $ a \gets 0 \\ \textbf{While } a \neq 5 \textbf{ do}...
1
vote
1answer
57 views

what is the 'x :=' part mean in a hoare triple?

In Hoare logic, there's a thing called a Hoare triple, e.g.$$ \begin{array}{ccccc} \{x = 2\} & & x := x+1 & & \{x = 3\} \end{array}. $$ What does '$x :=$' mean?
3
votes
2answers
151 views

What does the $O^*$ notation mean?

I'm recently reading some papers on the maximum independent set problem, all the algorithms' time complexity is donated by $O^*()$ notation, like $O^*(1.0836^n)$. One paper says "the $O^*$notation ...
16
votes
3answers
9k views

What is the purpose of using NIL for representing null nodes?

In my Algorithms and Data Structures course, professors, slides and the book (Introduction to Algorithms, 3rd edition) have been using the word NIL to denote for ...
5
votes
1answer
159 views

When it is said an algorithm runs in exponential time, is it meant it has complexity $O(2^n)$, or $2^{O(n)}$?

Also, are they equivalent or are they different? Examples of algorithms/Turing Machines that run in complexity of one but not the other would be much appreciated.
5
votes
3answers
256 views

Help understand the notation

I'm reading a computer science paper, this one: https://arxiv.org/abs/1608.03960. It uses certain notation in one of the illustrations (Figure 9, page 8 in the PDF version) that I don't understand how ...
2
votes
1answer
74 views

Is this a standard representation of a 'space' character?

I recently came across a handwritten note with directions to push a string of text into a database. There was a strange character in the string I've never seen before, a lower case 'b' with a forward ...
-1
votes
1answer
37 views

Why $\left\lceil lgn \right\rceil <lgn+1\le 2lgn\quad for\quad all\quad n\ge 2$

I have some confusion about 3.2-4 in CLRS. Here is the question : Is the function $\left\lceil \log { n } \right\rceil !$ polynomially bounded? Is the function $\left\lceil \log { \log { n } } \...
0
votes
1answer
27 views

A commonly-used symbol for the set of all heads of directed edges?

Let $G = (V, E)$ be a digraph, and consider the set $\left\{ v \in V \; \middle| \; \left(\{v\} \times V \right) \cap E \neq \varnothing \right\}$, the set of vertices which form edges with other ...
5
votes
1answer
164 views

What does $n^{O(1)}$ mean?

I read an example that said explain what "$f(n)$ is $n^{O(1)}$" means. I can't interpret the $n^{O(1)}$ syntax. I know what Big $O$ notation is, its just that this example looks odd to me.
4
votes
1answer
749 views

Determining Number of States in a Turing Machine

I am looking at an example Turing machine in my textbook, Automata and Computability by Dexter C. Kozen, and I'm confused as to how they determine the number of states this particular machine has. The ...
1
vote
5answers
266 views

“Smallest set” term in the trees set definition

I often meet such kind of the definition of the set of trees, as: The set of unranked $\Sigma$-trees, denoted by $T$, is the smallest set of strings over $\Sigma$ and the parenthesis symbols ‘)’ and ‘...
1
vote
1answer
39 views

What does it mean the norm symbol applied to a concept?

I'm reading this paper: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.150.14 or http://www.jmlr.org/papers/volume10/kontorovich09a/kontorovich09a.pdf On page 1101 are introduced 2 functions ...
2
votes
2answers
292 views

Addition modulo 2 notation (Quantum Computing)

I am studying Quantum Computing using the book Quantum Computation and Quantum Information of Michael Nielsen and Isaac Chuang. I am confused by the meaning of the $\oplus$ (addition modulo 2) symbol ...
-2
votes
1answer
78 views

How to negate this one?

How can I negate the following sentence: For all words x from L with |x|>= n , exists decomposition x = uvw with |uv| <= n and |v| >= 1, so for all i >= 0 , is valid that u(v)^iw in L is.
1
vote
2answers
184 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 ...
2
votes
1answer
59 views

What do the commas separating atomic events in a Relational Calculus formula means?

For instance, take the example of this book here on page 30. About the formula $$ Q(x,x') = R(x), S(x,y), S(x',y), R(x') $$ described there, what do the commas mean? Is it the same as an "and" ...