Questions tagged [notation]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
331 views

Meaning of double colon $::$

I've came across this expression regarding function composition in some notes by people from computer science, and I don't know what the notation "$::$" means. \begin{equation} g \circ f : A \...
1
vote
1answer
64 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 ...
1
vote
1answer
65 views

Are there color conventions in CS? [closed]

I don't remember seeing any color conventions in Computer Science used to represent some abstract information or to simplify diagrams. For instance, chemists have the CPK coloring which associates ...
1
vote
1answer
178 views

What does $CS - CF$ means?

What does $L_1 \in CS - CF$ means? I think the meaning is $L_1$ can be generated by context-sensitive grammars, but cannot be generated by context-free grammars. Am I understanding this correctly? ...
1
vote
1answer
62 views

What does this mean $[X]_1^T$?

I found this in information theory paper, P.3883* the authors states the following Most existing theoretic studies of network coding focus on DAGs due to its simpler structure and dure to the fact ...
1
vote
1answer
77 views

Determining asymptotic notation of a complex function

$$ 5n^4\log{n} - \frac{100n^2}{\log_4(n^2)} + 40 $$ I am currently studying algorithm analysis and i need to express this function in terms of big O, theta and omega, so I should find C, and N0 for ...
1
vote
1answer
1k views

Meaning of L* if L is a language

I can't find anywhere the meaning of $L^*$, given that $L$ is a language. I know $^* $ means repetition, for example $0^*$ = $\{ \epsilon, 0, 00, 000, \dots \}$. Or if $A$ is an alphabet $A^*$ are all ...
1
vote
1answer
33 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
55 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 ...
1
vote
1answer
205 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 ...
1
vote
1answer
173 views

$\tilde \Omega$ for division by logarithmic factor

Is $\Omega \left(\frac{n}{\log{n}} \right)\subset \tilde\Omega(n)$?
1
vote
1answer
131 views

On asymptotic complexity class notation?

Is the class of problems with complexity $O(n^{n^\epsilon})$ at every $\epsilon>0$ same as class of problems with complexity $O(n^{f(n)})$ at every $f(n)\in\omega(1)$ and hence both classes are ...
1
vote
1answer
476 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 graph ...
1
vote
1answer
198 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 ...
1
vote
1answer
64 views

How to express taking the next bit of an infinite string in small-step semantics?

I have to write a rule as part of a small step operational semantics (https://en.wikipedia.org/wiki/Operational_semantics). Whenever this rule is applied, the next bit belonging to an infinite bit ...
1
vote
1answer
22 views

How to understand the mathematical constraint of potentials?

Good evening! I am studying scheduling problems and I have some difficulties understanding constraints of potentials: Let be $t_j$ the time when a task $j$ starts, and $t_i$ the time when a task $i$ ...
1
vote
1answer
35 views

Maximum Subarray Problem - Analyzing best case, worst case, and average case time complexity big o

New to the board, if this is the wrong section I apologize and I will delete it. Will be helpful to be provided correct exchange to guide me through this process of learning. If you have a given an ...
1
vote
1answer
24 views

Notations for dealing with generators in algorithms

This question is about generators, which are functions that return an item from a (usually very large or infinite) set on demand, an example from Python is: ...
1
vote
1answer
28 views

Notation within gaussian function

On our lecture slides we have two different notations of the gaussian function. First it gets introduced as follows: $$p(x_n|\theta) = \frac{1}{\sqrt{2\pi}\sigma}exp\{-\frac{(x_n-\mu)^2}{2\sigma^2}\} \...
1
vote
1answer
115 views

Is grammar that describes an equation in prefix (Polish) notation always unambiguous?

I recently completed a problem in which I was asked to generate a parse tree for the expression $+ \, 5 \, * \, 4 \, 3$ using the following grammar and rightmost derivation: $$Expr \rightarrow + \, ...
1
vote
1answer
49 views

Why in the code i ≃ n?

i=2; while(i<n) { write('*'); i=i*i; } Why $n ≃ i$? I mean suppose $n=1000$ and so $i= 2,4,16,32,256,65536$ is in every steps. In the book wrote $2^2 ...
1
vote
1answer
151 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 ...
1
vote
1answer
306 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}...
1
vote
1answer
33 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\\...
1
vote
1answer
46 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
2answers
410 views

How do I interpret this divide and conquer algorithm for removing duplicates in a list?

Consider the following divide and conquer algorithm to remove duplicates in a list. The text is in French. What is the meaning of the variables $c1, c2, d1, d2$? Why are only the variables $c1, d1$ ...
1
vote
2answers
82 views

Is there a generally agreed short notation for “a points to b”

Is there a conventional symbol for "points to" or "is a pointer to". I've been using a short right arrow; for example "a is a pointer to b" would be (approximately) ...
1
vote
1answer
128 views

What does superscript + mean in relational algebra?

What does superscript + mean in relational algebra? Suppose $A$ is a subset of attributes of all attributes in a relation $R$. What does $A^+$ mean?
1
vote
1answer
12 views

Set notation for ACL matrix

This might not be a computer science specific question and apologies if that is the case but it does come from material related to working out access control lists and I cannot understand the notation ...
1
vote
0answers
30 views

Infix to reverse polish notation (RPN)

I have an example: m = n = p = (-1) ^ (m + n + p) * (m + n + p); I don't know what to do with multiple "=". Should I treat them as a sign with the lowest priority or just put them in end of ...
1
vote
0answers
73 views

Cheat sheet for notation

I'm reading a paper which has quite a few formulas. I'm getting quite confused with some of the notation. For example I am able to pick-up on the BNF Notation (::= -> "is defined as") ...
1
vote
1answer
36 views

Asymptotic notation and random variables

I have two random variables $X$ and $Y$ and I want to bound the value of one in terms of the other (for now, I don't care about the actual distribution of their values). Suppose that the two ...
1
vote
0answers
240 views

What's the difference between Acfg and ALLcfg

In computational theory, and talking about CFGs, Turing Machines, and so forth I haven't a satisfactory explanation or definition for what ATM means versus ALLTM or the same or similar uses with ...
1
vote
0answers
59 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
0answers
39 views

Representing Graham Scan Mathematically

I am aware the convex hull algorithm known as Graham Scan can be computed by sorting the derived vectors from points given in a 2D plane. One then iterates through a series of Cross Product ...
1
vote
0answers
217 views

Reverse Polish to infix

I have to convert "A = B C + D E + ×" from reverse polish notation to infix. I'm a bit confused because of the equals sign. Is that an operator too? This is my answer: A = (B+C) × (D+E) Is this ...
0
votes
3answers
313 views

Difference in having * inside vs outside of brackets for NFA

If you have a question saying "draw the NFA for the following language" what difference does it makes if the language is $(0^* \cup1^*)$ vs $(0 \cup1)^*$ in otherwords what difference does it make for ...
0
votes
2answers
274 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 ...
0
votes
1answer
76 views

Can I say ≤ O(f(x)) rather than = O(f(x)) if the bound is not tight?

Suppose I just invented merge sort, but due to my limited ability was only able to prove that the running time is $O(n^2)$. However, I suspect that the running time is actually better (in reality it's ...
0
votes
1answer
56 views

Converting sets into regular expressions

In my book: The set {abb, a, b, bba} is said to be converted into regular expression abb + a + b + bba. The set ...
0
votes
1answer
45 views

Express semantic duplicates of records formally

I'm working on a paper about record linkage and duplicate detection and want to visualize my definitions of "hard" and "semantic" duplicates. Hard ones are a 100% match; where's only true or false- ...
0
votes
1answer
1k views

Turing Machine notation

I'm a bit confused on some of the notation being used for turing machines in one of our exercises in class. The question gives us a string $\alpha \in \{0,1\}$* and the function $\mathsf{int}(\alpha)$...
0
votes
1answer
206 views

What is meant by the notation $L(…)$?

I am currently studying about formal languages and automata. I am trying to solve a problem but there is a notation whose meaning I'm not sure of. I have a question to find out the relationship ...
0
votes
2answers
67 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 ...
0
votes
1answer
234 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? ...
0
votes
1answer
71 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})^*$?
0
votes
1answer
120 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 ...
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 ...
0
votes
1answer
421 views

How do I normalize a push down automaton?

Looking at the above PDA, I am unsure whether or not it is normalized. Specifically, the loop transition from $q_1$ to $q_1$, because I know a transition must either push OR pop from the stack. Does ...
0
votes
1answer
112 views

representing set of non-overlaping string in formal notation

I want to represent a set of any substrings which come from an original string with constraint that all substrings should not be overlapped. To be more clear please consider the example below: e.g. <...