Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

# Questions tagged [notation]

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

145 questions
Filter by
Sorted by
Tagged with
46 views

### Difference between ⫾ (U+2AFE) and ⫿ (U+2AFF) in the context of Dijkstra's Guarded Command Language?

Continuing https://tex.stackexchange.com/questions/435986/how-to-draw-the-box-of-dijkstras-guarded-command-language, what is the difference in the intended usage of ⫾ (Dijkstra choice, U+2AFE) and ⫿ (...
50 views

31 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 ...
17 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 ...
49 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 ...
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, ...
41 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 ...
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 ...
159 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 ...
32 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),...
244 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 ...
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 ...
48 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 ...
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)$ ...
52 views

99 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? ...
983 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:...
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})^*$?
243 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 ...
109 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 ...
43 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?
93 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 <...
32 views

176 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 ...
10k 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 ...
161 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.
268 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 ...
### 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 } } \...