The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [notation]

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

Filter by
Sorted by
Tagged with
6
votes
0answers
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 <...
3
votes
2answers
365 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
92 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.
2
votes
1answer
62 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
53 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
309 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
47 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
327 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 ...
2
votes
0answers
222 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
116 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
57 views
3
votes
2answers
47 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 ...
1
vote
1answer
118 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
34 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
467 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
80 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
657 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
71 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 ...
14
votes
2answers
730 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 "...
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
36 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 ...
1
vote
2answers
229 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 ...
17
votes
2answers
2k 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
327 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 ...
1
vote
3answers
102 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
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$ ...
2
votes
1answer
83 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?
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
416 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
51 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 ...
0
votes
1answer
85 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
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
1answer
9k 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 ...
2
votes
2answers
76 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 ...
1
vote
1answer
334 views

How to read 'max min' and 'min max'?

Here is an exercise I came across while studying MaxFlow / MinCut and I'm rather stumped: Designate $G = (V, E)$ as an undirected graph that has at least two vertices. Every edge $(e)$ on this ...
1
vote
2answers
283 views

How do I interpret this divide and conquer algorithm for removing duplicates in a list?

Consider the following divide and conquer algorithm to remove duplicates in a list. The text is in French. What is the meaning of the variables $c1, c2, d1, d2$? Why are only the variables $c1, d1$ ...
5
votes
1answer
740 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 ...
1
vote
2answers
485 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
0answers
38 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 ...
0
votes
1answer
45 views

Question on interpreting logical notation, relating to alphabets, theoretical comp sci

$\exists x \in \Sigma^* (t=sx)$ Have I interpreted the above into words correctly?: "There exists a symbol 'x', which is a member of the set which contains all possible strings of alphabet sigma, ...
5
votes
1answer
145 views

What is the origin of using Q to denote a set of states in an automaton?

When talking about DFAs and NFAs as 5-tuples, it's common to use the letter $Q$ to denote the set of states in the automaton and to denote individual states with names like $q_0$, $q_1$, etc. Is ...
2
votes
1answer
648 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 ...
0
votes
0answers
88 views

What does an = sign with an x beneath it mean?

I am studying for a test in Logic right now, and saw the symbol $\underset{x}{=}$, which is used like this: $I \underset{x}{=} I'$. I've seen it in the solutions of questions like this one: Prove ...
3
votes
5answers
10k views

What is the difference between $\log^2(n)$, $\log(n)^2$, $(\log n)^2$, $\log (n^2)$ and $\log \log n$?

In research articles (e.g. this one's abstract), I often see the complexity of an algorithm expressed using a somewhat ambiguous notation: $\log^2(n) = ?$ $\log(n)^2 = ?$ $(\log n)^2 = (\log(n)) \...
1
vote
1answer
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 ...
9
votes
1answer
932 views

What does up arrow ($\uparrow$) mean in pseudocode?

I'm learning vantage point trees, and I met this while reading the paper Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces by Peter Yianilos (Proceedings of SODA 1993,...
46
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 ...
0
votes
1answer
38 views

There is any notation for a language that is empty infinite?

Assume that $L$ is a language, is there any established notation that means that $L$ is infinite or empty?