# Questions tagged [notation]

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

147 questions
Filter by
Sorted by
Tagged with
522 views

### What is a conventional format for presenting algorithms?

I'm writing a technical paper and the review committee wants my methodology to be represented in a conventional algorithm format. I've been searching all over the web for the conventional structure ...
99 views

34 views

### Substituting a term for a variable in a context

At this link you can read Nicola Gambino's slides on one way to approach the formal syntax of Martin-Löf dependent type theory. (They are concise and very readable.) On slide 10, he gives a standard ...
228 views

### Why mantissa and exponent are stored differently in a float?

As we know, in IEEE 754 standard, float number's exponent and mantissa are stored differently. While the exponent is stored as an unsigned number, taking advantage of the bias, the mantissa is in sign-...
335 views

### Explaining TM notation in Lewis/Papadimitriou

I was working on some questions in the book "Elements Of The Theory Of Computation", by Lewis and Papadimitriou, and I need help with one question - question 4.1.8 (chapter 4): Give the full ...
278 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 ‘...
247 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 ...
10k views

### Operator precedence in propositional logic

there is some kind of priorities for the elements in propositional logic ? for example : p ∧¬q → r , given this ,we there may be two options (p ∧¬q) → r OR p ∧ (¬q → r) , which one is the correct ?...
82 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 ...
426 views

### How to denote an array in writing paper

How can I represent an array when I am writing to show an algorithm in writing paper. Like Pi is represented by Greek letter. We use that Greek symbol to denote the value of Pi, Kind of like a pointer....
506 views

### Why are Complexity Notations Called Asymptotic?

Why do we use the term "asymptotic" in complexity. Although I know what an asymptote is, but what is an asymptote doing here?
62 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?
106 views

### Is there a standard (common) notation for the following operation on binary strings?

Typically, we use the notation $S = \{0, 1\}^n$ to denote the set of all $n$-bit strings. Suppose that I wanted to extract a subset of the strings where certain bits have some fixed values. For ...
86 views

### What does $\cdot$ mean as a notation with complexity classes?

In the wikipedia page for Toda's Theorem, the notation $A\cdot B$ is used where $A$ and $B$ are two complexity classes, but without explanation as to its meaning. SO given two classes $A$ and $B$ ...
57 views

### If c ∈ Σ denotes terminals, then is Y = Σ∖{c} the set of non-terminals?

If $c\in \Sigma$ denotes terminals, then is $Y=\Sigma \setminus \{c\}$ the set of non-terminals? These notations are used here, p. 379. But I cannot find their definitions. So what I'm asking is, is ...
66 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?
40 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 ...
312 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 \...
52 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 ...
61 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 ...
132 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? ...
57 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 ...
119 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 ...
28 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, ...
54 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 ...
### 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 ...
### $\tilde \Omega$ for division by logarithmic factor
Is $\Omega \left(\frac{n}{\log{n}} \right)\subset \tilde\Omega(n)$?