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
64 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?
4
votes
2answers
211 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 ...
17
votes
3answers
13k 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
162 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
284 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
92 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
41 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
170 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
901 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
297 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
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 ...
3
votes
2answers
521 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
104 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
299 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
66 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" ...
0
votes
1answer
57 views

Trouble understanding Grammar Rules

I am totaly new to theoretical computer science, so I am sorry if I get the terminology wrong: I was reading the definition of a grammar, what I didn't get was the formal definition of the production ...
1
vote
1answer
321 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 \...
2
votes
2answers
50 views

Help on the notation of the 2-bit operation: $\frac 12{(I+Z_1Z_0)}$

This was adapted from Quantum Mechanichs for Computer Scientists. On this equation, we have $I$ representing the identity operator, with $Z$ being defined for 1 bit as: $$ Z|0⟩ = |0⟩, \quad Z|1⟩ = -|...
0
votes
1answer
369 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 ...
14
votes
2answers
973 views

What is the origin of λ for empty string?

I usually use the symbol $\varepsilon$ for empty string (empty word or null string). But I know some people use $\lambda$ instead of $\varepsilon$. I think $\varepsilon$ is derived from the word "...
3
votes
2answers
49 views

Notation for a Kleene fixed point with a starting element

Assume a CPO $Q,\leq$ and a Scott-continuous function $f : Q \rightarrow Q$. As it is known, the chain $\bot \leq f(\bot) \leq \ldots \leq f^n(\bot)$ (where $f^n$ denotes the function $n-1$-times ...
2
votes
0answers
246 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-...
2
votes
1answer
127 views

Equivalent expression in English: Set Notation $\{0,1\}^K$

I am overviewing this expression given in set notation. Could someone translate what M "Element of" $\{{0,1}\}^k$ stands for? Im looking for an explanation in English like what I did below. $K_e = \...
2
votes
1answer
728 views

What does > mean in this TAOCP solution?

For our assignment we have to implement a solution given to one of the problems in The Art of Computer Programming by D.E. Knuth (Ex24; Chapter 5: Sorting; TAOCP, Vol3, 2nd). However, I fail to ...
2
votes
1answer
61 views
1
vote
1answer
123 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 ...
2
votes
2answers
35 views

Can I notate time complexity depending on the result of an algorithm?

I have a program that calculates the first year some two events happen on the same day. I have not calculated any upper limit for the year. The time complexity of the program would be equivalent to O(...
4
votes
1answer
658 views

Finding the language of a context-free grammar?

Given following question: Let $G$ be a context-free grammar, $G=(V, \Sigma, R, S)$, that has start variable $S$, set of variables $V = \{S\}$, set of terminals $\Sigma = \{0, 1\}$, and set of rules $...
4
votes
1answer
107 views

Programming Symbols : Instance/Instantiation

Is there a generally accepted symbol for indicating instantiation. That is indicating an object is an instance of a class. My first guess is to use a left arrow with a double or triple line but this ...
6
votes
1answer
659 views

Notation: SPACE(n) vs SPACE(O(n))

I want to denote the class of problems solvable by linear space multi-tape Turing machines. I have seem in many places this class being denoted by $SPACE(n)$. But why is the notation $SPACE(O(n))$ not ...
0
votes
1answer
74 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 ...
2
votes
1answer
60 views

What does $\mathbf{Q}^+$ mean in approximation texts?

Often, in a lot of texts concerning approximation algorithms I see the following notation (for example, here in page 19 of the PDF or the first page of the introduction): ... and a cost function on ...
0
votes
0answers
38 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 ...
18
votes
2answers
3k views

What is this fraction-like “discrete mathematics”–style notation used for formal rules?

In the paper "A Conflict-Free Replicated JSON Datatype", I encountered this notation for formally defining "rules": What is this notation called? How do I read it? For example: the ...
2
votes
0answers
346 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 ...
3
votes
1answer
43 views

Formal notations of equivalencence between floating point expressions

In an informal context, most programmers might call these two expressions "equal" and no one would be mislead: (a + b) + c a + (b + c) For floating point numbers,...
-1
votes
1answer
46 views

Meaning of `<==>` in documentation? [closed]

Title says it all. I just need to confirm that... X.__add__(y) <==> x+y ...doesn't mean anything more than just 'same as' The problem is Google returns zero ...
47
votes
2answers
7k views

Order of growth definition from Reynolds & Tymann

I am reading a book called Principles of Computer Science (2008), by Carl Reynolds and Paul Tymann (published by Schaum's Outlines). The second chapter introduces algorithms with an example of a ...
1
vote
3answers
141 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 ...
1
vote
2answers
89 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$ ...
2
votes
1answer
96 views

What does the $\leq_{\mathrm{P}}$ symbol mean?

What does $\leq_{\mathrm{P}}$ mean? Is it supposed to mean less than or equal polynomial time?
5
votes
1answer
789 views

What does ⊢ mean in operational semantics?

I have been reading a couple of texts on operational semantics. In [1], the evaluation of expressions is done as in this rule: $\frac{<e_1,s>\;\Rightarrow \;n_1\;\;\;<e_2,s>\;\Rightarrow ...
0
votes
1answer
43 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- ...
1
vote
2answers
482 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....
0
votes
1answer
94 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. <...
1
vote
1answer
59 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
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 ...
2
votes
2answers
77 views

Meaning of , and ; in relation to defining context

I have seen use of , and somewhere use of ; when defining context : $$\dfrac{\phi \ , \ \Gamma \ \vdash } {} $$ somewhere else i have seen : $$\dfrac{\phi \ ; \ \Gamma \ \vdash ...
2
votes
1answer
11k views

What's the difference between the concatenation and union of symbols within a language

I feel like I'm confusing myself perhaps but I'm having a bit of trouble figuring out how exactly this language works. I'm given the following regular expression (a + b)* (abba* + (ab)*ba) Can ...