The 2024 Developer Survey results are live! See the results

# Questions tagged [notation]

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

198 questions
Filter by
Sorted by
Tagged with
711 views

### Definition feels contradictory (Computational Complexity Theory)

I studied a definition for time complexity: Let $M$ be a deterministic Turing Machine. The running time of $M$ is said to be: for a function $t: \mathbb{N} \to \mathbb{N}$ ($\mathbb{N}$ is natural ...
54 views

### graph theory single bar vs double bar size notation

A follow-up on https://stackoverflow.com/questions/15037679/what-do-the-absolute-value-bars-mean-in-graph-theory What is the difference between single bar $|G|$ and double bar $||G||$ notation (both ...
• 807
148 views

### What does $o_n(1)$ mean?

I'm trying to read the following article, and in the abstract they write: Let $\xi$ be a non-constant real-valued random variable with finite support, and let $M_n(\xi)$ denote a $n\times n$ random ...
118 views

### SCoP, Iteration Domain in Polyhedral Optimization and use of Presburger arithmetic

Context: While exploring the fundamentals of polyhedral optimization and attempting to explore a connection from the input Static Control Part (SCoP) to the iteration domain from birds eye view, I am ...
• 123
1 vote
13 views

### Is there a symbol in FA/FSM for everything else

I remember in a Computability Theory class building a state machine for an assignment that required many 'go-back' transitions on $\Sigma - symbols$ for all symbols not already handled. This was very ...
• 111
35 views

### An elementary question about grammar

Recently, I am studying grammar in automata. And, I have few information about this subject. I have a grammar with rules $\{S\to ASA, A\to aA, A\to \epsilon\}$. Is it true if I say that $S\to aASA$ ...
113 views

### Understanding reductions and notation

I am currently working through Sipser's Introduction to the Theory of Computation. In chapter 5, he defines that a Language $A$ is mapping reducible to language $B$, written $A\leq_m B$ if there is a ...
63 views

### Is there a common notation for describing this operation $coNP\; ? \; NP = DP$?

While working with complexity classes, I've come along the definition of $DP$ (or $D^p$): $$DP = \{L_1 \cap L_2 \mid L_1 \in NP \text{ and } L_2 \in coNP\}$$ I am interested in a different (and much ...
• 321
89 views

### Function types in Computer Science Metanotation

See Guy Steele's slides for what I refer to by "Computer Science Metanotation", specifically the bits about BNF. I often make use of the BNF syntax observed there, as a substitute for ...
69 views

### When to use subscript and when to make it a function?

Let's say, I have a set of cats $C = \{ a, b, c, ... \}$. Each cat has a tail. I can say, that the lengths of the tails of cats are denoted as $t_a$, $t_b$, etc. Otherwise, I can say that they are ...
• 113
3k views

704 views

### Same notation/terminology for union of sets and concatenation (Kleene star)?

For the union of sets we use the union operator $\cup$ (or $\bigcup$). And for a concatenation (Kleene star) we also use the union operator. The operations are different, but why the same terminology ...
• 119
1 vote
430 views

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 + \, ... • 37 3 votes 2 answers 64 views ### Parentheses after Typing Environment I've been reading about System F Omega lately, and I keep stumbling across a construct in typing rules that I cannot find an explanation of: Γ(x) = k. For example, ... 1 vote 1 answer 212 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 ... 0 votes 2 answers 68 views ### Transformation Function: Gonzalez and Woods I have been reading Image Processing from Gonzalez and Woods and in the chapter Image Transformation I have come across this equation$$ T \left(u, v\right) = \sum_{x=0}^{M-1} { \sum_{y=0}^{N-1} ...
• 1,210
1 vote
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 ...