Questions tagged [notation]

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

Filter by
Sorted by
Tagged with
0 votes
1 answer
33 views

An elementary question about grammar

Recently, I am studying grammar in automata. And, I have few information about this subject. I have a grammar with rules $\{S\to ASA, A\to aA, A\to \epsilon\}$. Is it true if I say that $S\to aASA$ ...
user163802's user avatar
-1 votes
1 answer
88 views

Understanding reductions and notation

I am currently working through Sipser's Introduction to the Theory of Computation. In chapter 5, he defines that a Language $A$ is mapping reducible to language $B$, written $A\leq_m B$ if there is a ...
talon23's user avatar
2 votes
2 answers
57 views

Is there a common notation for describing this operation $coNP\; ? \; NP = DP$?

While working with complexity classes, I've come along the definition of $DP$ (or $D^p$): $$DP = \{L_1 \cap L_2 \mid L_1 \in NP \text{ and } L_2 \in coNP\}$$ I am interested in a different (and much ...
Algebruh's user avatar
  • 301
0 votes
0 answers
65 views

Function types in Computer Science Metanotation

See Guy Steele's slides for what I refer to by "Computer Science Metanotation", specifically the bits about BNF. I often make use of the BNF syntax observed there, as a substitute for ...
Sebastian Graf's user avatar
0 votes
1 answer
40 views

When to use subscript and when to make it a function?

Let's say, I have a set of cats $C = \{ a, b, c, ... \}$. Each cat has a tail. I can say, that the lengths of the tails of cats are denoted as $t_a$, $t_b$, etc. Otherwise, I can say that they are ...
yegor256's user avatar
  • 113
11 votes
3 answers
3k views

Is Big-Theta a more accurate description of worst case run time than Big-O?

Question I was asked: Does it make a difference if I say "The worst case run time is $O(n^2)$ vs the worst case run time is $\Theta(n^2)$?" To me, the only difference is that when we say $O(...
Carter Falkenberg's user avatar
0 votes
1 answer
38 views

Does $L = \{a^n \ | \ n \geq 1, \ n \ \text{ is even or a square number}\}$ have infinite equivalence classes?

I am unsure if it has infinite equivalence classes or not, respectively how to interpret the textbook solution. My approach was that it has infinite because, lets say we have $x = a^5$ and $y = a^7$. ...
tomato's user avatar
  • 17
0 votes
3 answers
95 views

Is there a notation for types?

Is there a notation for statements like the following: If both operands are of type int, then the result is of type int. If ...
user51462's user avatar
  • 113
1 vote
0 answers
32 views

Dot symbol in set-builder expressions in CRDT literature?

In Conflict-free Replicated Data Types: An Overview and other CRDT-related publications by Preguiça's group, a dot symbol often appears without definition. What does it indicate, how standard is it as ...
aas's user avatar
  • 11
1 vote
1 answer
42 views

What does :: indicate in all-quantifier predicates?

Can somebody explain to me the meaning of $::$ in the following predicate? $$(\forall i : P(i) : Q(i)) \equiv (\forall i :: P(i) \implies Q(i))$$
Rubus's user avatar
  • 121
1 vote
1 answer
147 views

What order B-tree is this?

I am studying B-trees and reading Introduction to Algorithms by Cormen et al. Unfortunately, they have this diagram Figure 18.1 and they do not list the order of the tree. I understand that for a B-...
Stan Shunpike's user avatar
-2 votes
1 answer
59 views

What is the BigO of a C# function when runtime is 3n - logn + 1

I am trying to learn notations for a course and I am stuck on how to even start. I need to figure out the BigO for this function. Question is there's a C# function bool isPalindrome(string S) which ...
Aker55's user avatar
  • 5
1 vote
1 answer
59 views

Simplifying Notations in Recurrence Relation

In the CLRS book, section 4.4 they try to resolve the following recurrence: $$T(n) = 3T\bigg(\bigg\lfloor \frac{n}{4} \bigg\rfloor\bigg) + \Theta(n^2)$$ Later, they write the same recurrence as $$T(n) ...
AlessandroF's user avatar
1 vote
0 answers
43 views

How can I define nested structs as mathematical notation?

My purpose is to write a academic paper related to shared computing more abstractly and I need to refer to these variables in both equation and its corresponding pseudocode. In my pseudocode I have ...
alper's user avatar
  • 135
2 votes
2 answers
131 views

How can I define programming struct variables as mathematical notation?

My purpose is to write a journal paper related to shared computing more abstractly (simply cost model) and I need to refer to these variables in both equation and its corresponding pseudocode. I want ...
alper's user avatar
  • 135
-1 votes
1 answer
55 views

what does $(1 + (λ, λ))$ Genetic Algorithm mean?

I am discovering the topic of Genetic Algorithms, I read a bit about it on wikipedia and towardsdatascience. When I checked papers some papers, I found them using the notation "$(1 + (λ, λ))$&...
user206904's user avatar
1 vote
0 answers
16 views

Contiguous-substring operator

If string concatenation $ab$ is like left- and right-multiplication, is there any infix (latex) operator notation I can use for checking for contiguous substrings, like $bc \subseteq abcd$? $\subseteq$...
andi's user avatar
  • 11
1 vote
1 answer
27 views

Definition a Turing machine (which may or may not halt) as a function... notation?

I would like to define a Turing machine as follows. Let Z be an alphabet, and let L be the set of all sentences of this alphabet. For instance, Z={0,1}, then L is the set of all binary sentences. A ...
Anon21's user avatar
  • 345
1 vote
1 answer
38 views

What does ({a,b}*)² mean?

Pretty much just the title. Is it all possible combinations of a and b that have 2 letters ?
Connor Kolan's user avatar
-1 votes
1 answer
52 views

What does x sign mean in functions

I came across this cross sign when reading a book. Does anyone know what does this mean in the context of a function?
Thanuja Dilhan's user avatar
0 votes
1 answer
467 views

What is the meaning of this symbol that looks like an inverted uppercase A?

I found this symbol in a book I'm reading. Does anyone know what this symbol means? Does it mean for all js?
Thanuja Dilhan's user avatar
1 vote
1 answer
109 views

What is the origin of the Bottom Type notation? Why does it look like... a bottom?

I couldn't help but notice the opening summary in Wikipedia's article on Bottom Types: In type theory, a theory within mathematical logic, the bottom type is the type that has no values. It is also ...
Dai's user avatar
  • 421
3 votes
0 answers
101 views

How to write a job shop problem with these constraints in alpha|beta|gamma notation?

I have a job shop scheduling problem with the following characteristics. How would I write that in alpha|beta|gamma notation (see 1,2)? I know some of the parts, but not all. I add my suggestions in <...
Peter's user avatar
  • 131
1 vote
1 answer
37 views

What does n with an index 0 mean in defenition of Theta/Big Omega/ Big-oh notation?

We define theta notation as follows: $\Theta(g(n))$ = {f(n): there are exist $c_1, c_2$ > 0 and $n_0$ such that 0 $\leq$ $c_1$g(n) $\leq$ f(n) $\leq$ $c_2$g(n) for all n > $n_0$}. I found an ...
Vlad Mikheenko's user avatar
1 vote
1 answer
25 views

Set notation for ACL matrix

This might not be a computer science specific question and apologies if that is the case but it does come from material related to working out access control lists and I cannot understand the notation ...
pac234's user avatar
  • 81
0 votes
1 answer
36 views

On lambda calculus notation: FGa

If we've got this expression: FGa where F and G are functions (as well as a, of course; but let's treat a as a constant). It must be understood that: first apply F taking G as input; then apply the ...
cibercitizen1's user avatar
1 vote
2 answers
545 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?
Matthew Christopher Bartsh's user avatar
2 votes
1 answer
89 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}$
Gabriel's user avatar
  • 21
1 vote
1 answer
287 views

Maximum Subarray Problem - Analyzing best case, worst case, and average case time complexity big o

New to the board, if this is the wrong section I apologize and I will delete it. Will be helpful to be provided correct exchange to guide me through this process of learning. If you have a given an ...
ABC's user avatar
  • 113
8 votes
4 answers
4k views

Arrow notation?

can someone explain what the following notation is? For j <- 1 to n Legal <- True I've seen these in various places, including wikipedia articles. It ...
Daniel's user avatar
  • 190
1 vote
1 answer
30 views

Notations for dealing with generators in algorithms

This question is about generators, which are functions that return an item from a (usually very large or infinite) set on demand, an example from Python is: ...
DjaouadNM's user avatar
  • 133
1 vote
0 answers
49 views

Infix to reverse polish notation (RPN)

I have an example: m = n = p = (-1) ^ (m + n + p) * (m + n + p); I don't know what to do with multiple "=". Should I treat them as a sign with the lowest priority or just put them in end of ...
GoldenRC's user avatar
26 votes
3 answers
6k views

Is there any reason why the modulo operator is denoted as %?

I would like to know if there is any reason why many programming languages use the notation % for the modulo operator? It is used in the most "famous" ...
zdm's user avatar
  • 1,046
2 votes
3 answers
95 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, ...
Niklas Rosencrantz's user avatar
0 votes
0 answers
51 views

Function notation/mapping for this type of functions?

In short, what is the proper function notation/mapping for this type of functions? From Wikipedia regarding maps: In the communities surrounding programming languages that treat functions as first-...
JDoeDoe's user avatar
  • 119
1 vote
1 answer
41 views

Notation within gaussian function

On our lecture slides we have two different notations of the gaussian function. First it gets introduced as follows: $$p(x_n|\theta) = \frac{1}{\sqrt{2\pi}\sigma}exp\{-\frac{(x_n-\mu)^2}{2\sigma^2}\} \...
csphil's user avatar
  • 13
3 votes
1 answer
749 views

Does there exist standardized language-agnostic data structure notation?

I wonder if there exists language-agnostic data structure notation. Preferably a standard, allowing to describe data structures and basic data types. e.g. something like a subset of ...
Filip's user avatar
  • 133
1 vote
1 answer
2k 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 ...
cagcoach's user avatar
  • 123
2 votes
1 answer
199 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 ...
Gerardo Zinno's user avatar
0 votes
2 answers
644 views

Same notation/terminology for union of sets and concatenation (Kleene star)?

For the union of sets we use the union operator $\cup$ (or $\bigcup$). And for a concatenation (Kleene star) we also use the union operator. The operations are different, but why the same terminology ...
JDoeDoe's user avatar
  • 119
1 vote
1 answer
365 views

Is grammar that describes an equation in prefix (Polish) notation always unambiguous?

I recently completed a problem in which I was asked to generate a parse tree for the expression $+ \, 5 \, * \, 4 \, 3$ using the following grammar and rightmost derivation: $$Expr \rightarrow + \, ...
Goya's user avatar
  • 37
3 votes
2 answers
63 views

Parentheses after Typing Environment

I've been reading about System F Omega lately, and I keep stumbling across a construct in typing rules that I cannot find an explanation of: Γ(x) = k. For example, ...
Andrew Thaddeus Martin's user avatar
1 vote
1 answer
181 views

Determining asymptotic notation of a complex function

$$ 5n^4\log{n} - \frac{100n^2}{\log_4(n^2)} + 40 $$ I am currently studying algorithm analysis and i need to express this function in terms of big O, theta and omega, so I should find C, and N0 for ...
Sara Owen's user avatar
0 votes
2 answers
68 views

Transformation Function: Gonzalez and Woods

I have been reading Image Processing from Gonzalez and Woods and in the chapter Image Transformation I have come across this equation $$ T \left(u, v\right) = \sum_{x=0}^{M-1} { \sum_{y=0}^{N-1} ...
Turing101's user avatar
  • 1,190
1 vote
1 answer
51 views

Why in the code i ≃ n?

i=2; while(i<n) { write('*'); i=i*i; } Why $n ≃ i$? I mean suppose $n=1000$ and so $i= 2,4,16,32,256,65536$ is in every steps. In the book wrote $2^2 ...
Michael's user avatar
  • 33
4 votes
1 answer
90 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 ⫿ (...
user avatar
2 votes
2 answers
222 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{◻}\...
user avatar
5 votes
1 answer
115 views

Exact meaning of $2^{\mathcal{O}(f(n))}$

In Sipser's Introduction to the Theory of Computation he uses the notation $2^{\mathcal{O}(f(n))}$ to denote some asymptotic running time. For example he says that the running time of a single-tape ...
Daniel's user avatar
  • 163
3 votes
2 answers
2k views

Weight functions in graph algorithms

In text books, for instance in the 3rd edition of Introduction to Algorithms, Cormen, on page 625, the weights of the edge set $E$ is defined with a weight function $w:E\rightarrow \mathbb{R}$. Why ...
RichArt's user avatar
  • 133
1 vote
1 answer
52 views

Asymptotic notation and random variables

I have two random variables $X$ and $Y$ and I want to bound the value of one in terms of the other (for now, I don't care about the actual distribution of their values). Suppose that the two ...
user1246462's user avatar