People who code: we want your input. Take the Survey

Questions tagged [notation]

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

Filter by
Sorted by
Tagged with
3
votes
1answer
283 views

Notation for average case complexity of an algorithm

I'm just wondering what the correct notation is when referring to an average case complexity of an algorithm that was calculated by doing empirical analysis. For example, I have tested my algorithm ...
3
votes
1answer
253 views

Properties of Reverse Polish Notation expressions that are algebraically invariant

The RPN expressions a b + c * and f d e + * are algebraically equivalent, though the names of the variables are different ...
3
votes
2answers
126 views

Combining these two results into one asymptotic notation

Assume you have two parameters, $N \gg 1$ and $\epsilon < 1$. I have an algorithm (and matching lower bounds) that runs in $\Theta(\epsilon^{-1}+\log N)$ for $\epsilon > N^{-1}$, and $\Theta\...
3
votes
0answers
45 views

Where, besides Scheme reports (RnRS) has Stoy's notation for auxiliary semantic functions been used?

The denotational semantics of R4RS, R5RS and R7RS Scheme (included in the language report) uses the same notation that was used by J. E. Stoy in his book, "Denotational Semantics: the Scott-Strachey ...
3
votes
0answers
135 views

Correct mapping “update” notation for computer science papers

A nice easy one. I'm interested to know the most standard and accepted way to denote the update of a mapping in the context of a theoretical computer science paper. By example, suppose we have a ...
2
votes
2answers
821 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 ...
2
votes
3answers
104 views

Notation for asymptotic bounds on both sides

I am writing my first paper, and one of the results can be written as follows: For any $W,\epsilon$ such that $\epsilon = o\left(\frac{\log^4 W}{W\log\log W}\right)$ and $\epsilon=\omega\left(\frac{...
2
votes
2answers
49 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?
2
votes
1answer
112 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?
2
votes
2answers
79 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
3answers
87 views

Meaning of $\log^{O(1)}(a+b)$

What's the meaning of $\log^{O(1)}(a+b)$ ? Is it simply $(\log_2(a+b))^k$ where k is calculated in constant time ? That is the base 2 logarithm usually in computer science when no other base is set, ...
2
votes
1answer
158 views

What does the notation $ [ i \neq k ] $ mean?

I can't figure out what the notation $[x \neq k ]$ means. Here's a bit of context: The formula is: $Pr[A_i^k = 1] = \frac{[i\neq k]}{|k-i| + 1} = \begin{cases} \frac{1}{k-i+1} \text{ if } i \lt k \\ 0 ...
2
votes
2answers
874 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?
2
votes
1answer
751 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
169 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
63 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 ...
2
votes
1answer
75 views

Meaning of $\stackrel{*}{\rightarrow}$ production rule?

I've seen the production rule $\stackrel{*}{\rightarrow}$ in some papers concerning regular languages. What's the meaning of $\stackrel{*}{\rightarrow}$ production rule?
2
votes
1answer
30 views

Raising to the T in machine learning

What does it mean when in a machine learning paper there is $(arg)^{T}$, what does the T does to an arg in this 3b1b video on neural networks he puts the: $(w^{l-1})^{T}$
2
votes
1answer
157 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 ...
2
votes
1answer
181 views

What does $|w|$ mean in the statement “ $|w|$ where $w \in L \subset \Sigma^*$”?

In my assignment I find these symbols: $|w|$ where $w \in L \subset \Sigma^*$ I believe it means the lexikografic value of a word, but I am not 100% certain. Let me phrase my question this way: ...
2
votes
1answer
568 views

Short notation for Turing machine configurations

I'm writing about Turing machines and often need to denote the tape. I'm using exponential tapes, i.e. a repetition count for each symbol. I usually use something similar to $(x_k^{e_k})_{1 \leq k \...
2
votes
1answer
29 views

Notation for field access in Algorithm

While writing array index in an algorithm $a[i]\gets v$ is conventionally used. Is the notation $a_{i}\gets v$ also used ? If the algorithm uses struct or ...
2
votes
1answer
89 views

What is the standard notation for introducing syntactical formalism in a paper

Suppose you want to introduce a format for a language, commands, ... etc. (Specially in the filed of computer science) in a paper for example something like below: ...
2
votes
2answers
126 views

Typesetting LTL in Unicode?

Unicode has an abundance of open circles, diamonds and boxes. Using these, we can typeset linear-time temporal logic formulas such as $$ (\mathop{⬦}ψ)\ \,\land\ \,\mathop{⬦}(θ\ \mathsf{U}\ \mathop{◻}\...
2
votes
1answer
80 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" ...
2
votes
2answers
51 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⟩ = -|...
2
votes
1answer
69 views
2
votes
1answer
180 views

How to denote the space complexity in terms of output

Normally the space complexity of an Algorithm $A$ is denoted $\textrm{SPACE}(A)$, which means how much space is needed by the computation itself. I would however like to also describe how much storage ...
2
votes
1answer
25 views

What does $\alpha_r\supset\beta_r$ mean in the tolerance definition of System Z?

I'm reading up on System Z introduced by Judea Pearl (in System Z: a natural ordering of defaults with tractable applications to nonmonotonic reasoning). A central definition is that of tolerance of a ...
2
votes
1answer
29 views

When and what must be present on the left-hand side of the turnstile in metalogics?

Let me show the problem on an example... An actual task from one of the former exams: Consider a simple functional language: $$e::= x|n|e_1e_2|\lambda x.e$$ With typing rules: $$\tau ::= \mathtt{int} ...
2
votes
1answer
692 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 ...
2
votes
2answers
37 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(...
2
votes
1answer
43 views

Meaning of ⟨_⟩ in the context of verifiers

A verifier for a language A is an algorithm V, where $$A = \{w \mid V \text{ accepts $\langle w,c \rangle$ for some string $c$}\}$$ ($c$ is called a certificate or proof) What's the definition of $\...
2
votes
0answers
36 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 ...
2
votes
2answers
790 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
0answers
268 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
0answers
358 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 ...
1
vote
5answers
318 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
2answers
435 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 ...
1
vote
2answers
12k 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 ?...
1
vote
1answer
90 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 ...
1
vote
2answers
611 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....
1
vote
1answer
70 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?
1
vote
3answers
270 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
95 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$ ...
1
vote
1answer
58 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 ...
1
vote
2answers
33 views

Why are binary numbers sometimes written with one or more leading zeros that don't change the number (quantity) represented?

Binary numbers like '0110', or '00100101' are seen very often in all contexts. What are the leading (left hand side) zeroes for? Why did the writer not write '110' and '100101', respectively?
1
vote
1answer
313 views

Convention of a += operator in pseudocode

I have to write some algorithm in pseudocode for a paper. For this I have the "$\leftarrow$" to assign a value. $x \leftarrow y^2$ now I want to write a method which adds to the variable. In ...
1
vote
2answers
101 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?
1
vote
1answer
43 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 ...