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
3 answers
83 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 ...
user avatar
  • 101
1 vote
0 answers
25 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 ...
user avatar
  • 11
1 vote
1 answer
38 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))$$
user avatar
  • 115
1 vote
1 answer
29 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-...
user avatar
-2 votes
2 answers
46 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 ...
user avatar
  • 5
1 vote
1 answer
46 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) ...
user avatar
1 vote
0 answers
26 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 ...
user avatar
  • 133
2 votes
3 answers
68 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 ...
user avatar
  • 133
-1 votes
1 answer
33 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 + (λ, λ))$&...
user avatar
1 vote
0 answers
10 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$...
user avatar
  • 11
1 vote
1 answer
25 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 ...
user avatar
  • 345
1 vote
1 answer
35 views

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

Pretty much just the title. Is it all possible combinations of a and b that have 2 letters ?
user avatar
-1 votes
1 answer
50 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?
user avatar
0 votes
1 answer
449 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?
user avatar
1 vote
1 answer
71 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 ...
user avatar
  • 421
3 votes
0 answers
61 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 <...
user avatar
  • 131
1 vote
1 answer
31 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 ...
user avatar
1 vote
1 answer
16 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 ...
user avatar
  • 83
0 votes
1 answer
34 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 ...
user avatar
1 vote
2 answers
69 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?
user avatar
2 votes
1 answer
36 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}$
user avatar
  • 21
1 vote
1 answer
91 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 ...
user avatar
  • 113
7 votes
4 answers
2k 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 ...
user avatar
  • 180
1 vote
1 answer
27 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: ...
user avatar
  • 133
1 vote
0 answers
39 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 ...
user avatar
27 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" ...
user avatar
  • 1,016
2 votes
3 answers
93 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, ...
user avatar
0 votes
0 answers
31 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-...
user avatar
  • 119
1 vote
1 answer
34 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}\} \...
user avatar
  • 13
3 votes
1 answer
440 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 ...
user avatar
  • 133
1 vote
1 answer
1k 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 ...
user avatar
  • 123
2 votes
1 answer
173 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 ...
user avatar
0 votes
2 answers
351 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 ...
user avatar
  • 119
1 vote
1 answer
264 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 + \, ...
user avatar
  • 37
3 votes
2 answers
58 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, ...
user avatar
1 vote
1 answer
122 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 ...
user avatar
0 votes
1 answer
38 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} ...
user avatar
  • 1,162
1 vote
1 answer
50 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 ...
user avatar
  • 33
4 votes
1 answer
85 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
168 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
96 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 ...
user avatar
  • 163
3 votes
2 answers
1k 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 ...
user avatar
  • 133
1 vote
1 answer
44 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 ...
user avatar
1 vote
1 answer
2k views

Meaning of L* if L is a language

I can't find anywhere the meaning of $L^*$, given that $L$ is a language. I know $^* $ means repetition, for example $0^*$ = $\{ \epsilon, 0, 00, 000, \dots \}$. Or if $A$ is an alphabet $A^*$ are all ...
user avatar
  • 13
3 votes
3 answers
68 views

Why is subarray $A[p..k-1]$ empty when $k=p$?

I'm working through a proof of correctness for merge sort. I'm given a loop invariant for a for loop, which makes reference to a subarray $A[p..k-1]$. During the initialization step of the ...
user avatar
  • 215
2 votes
1 answer
37 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} ...
user avatar
  • 179
2 votes
0 answers
39 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 ...
user avatar
1 vote
0 answers
385 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 ...
user avatar
  • 11
1 vote
0 answers
65 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 ...
user avatar
1 vote
1 answer
51 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, ...
user avatar
  • 1,582