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
21 views

How to understand the mathematical constraint of potentials?

Good evening! I am studying scheduling problems and I have some difficulties understanding constraints of potentials: Let be $t_j$ the time when a task $j$ starts, and $t_i$ the time when a task $i$ ...
1
vote
1answer
41 views

Can the notation for polynomial reduction, A ≤p B be reversed in computability theory?

I don't know this is a proper question on this forum but I was reading about computability theory and I saw the reduction concept and its notation like this: $A \le_pB$. I just wanted to know is this ...
1
vote
1answer
38 views

What is the meaning of max() in intro. to algorithms?

I'm reading chapter 3(growth functions) of CLRS and in giving an example of proving theta for a standard quadratic function the book gives the following value for $n_0 = 2 \cdot max(|b|/a, \sqrt{|c|/a}...
1
vote
1answer
32 views

Syntax of recurrence formula not clear

I have this task for Analysis of Algorithms module in university $$ \begin{align*} W, V &= \{v_1, v_2, v_n\}, S = \{s_1, s_2, s_n\}\\ G(W) &= \max~_{i:w_i\leq w} ~\{G(W-s_i) + v_i\}, G(0)=0\\...
1
vote
1answer
41 views

Notation for expressing function call count during a program run

Which notation can be used for expressing how many times that function or subroutine called during a run of a program? Example program pseudocode: $ a \gets 0 \\ \textbf{While } a \neq 5 \textbf{ do}...
1
vote
2answers
259 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$ ...
1
vote
2answers
76 views

Is there a generally agreed short notation for “a points to b”

Is there a conventional symbol for "points to" or "is a pointer to". I've been using a short right arrow; for example "a is a pointer to b" would be (approximately) ...
1
vote
1answer
102 views

What does superscript + mean in relational algebra?

What does superscript + mean in relational algebra? Suppose $A$ is a subset of attributes of all attributes in a relation $R$. What does $A^+$ mean?
1
vote
1answer
28 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 ...
1
vote
0answers
31 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 ...
1
vote
0answers
17 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 ...
1
vote
0answers
49 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 ...
0
votes
3answers
172 views

Difference in having * inside vs outside of brackets for NFA

If you have a question saying "draw the NFA for the following language" what difference does it makes if the language is $(0^* \cup1^*)$ vs $(0 \cup1)^*$ in otherwords what difference does it make for ...
0
votes
2answers
268 views

Clarify the steps: what happened in this mathematical modelling of TSP?

Source: http://examples.gurobi.com/traveling-salesman-problem I don't get this part: (look at the source) $$\sum_{i,j\in\{1,2,3\},i\neq j} x_{ij}=3>2=|\{1,2,3\}|-1$$ I get that $x_{ij}$ is ...
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 ...
0
votes
1answer
42 views

Converting sets into regular expressions

In my book: The set {abb, a, b, bba} is said to be converted into regular expression abb + a + b + bba. The set ...
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- ...
0
votes
1answer
745 views

Turing Machine notation

I'm a bit confused on some of the notation being used for turing machines in one of our exercises in class. The question gives us a string $\alpha \in \{0,1\}$* and the function $\mathsf{int}(\alpha)$...
0
votes
1answer
191 views

What is meant by the notation $L(…)$?

I am currently studying about formal languages and automata. I am trying to solve a problem but there is a notation whose meaning I'm not sure of. I have a question to find out the relationship ...
0
votes
2answers
43 views

Terminology for worst-case N-complexity on $O(1)$ insert after amortisation

Normally, when discussing amortisation and worst-case complexity, amortisation negates the worst-case scenarios, and the BigO describes the average for the operation (the way it's used in interviews ...
0
votes
1answer
88 views

Convert for loop into math sigma notation

Have some code (written in C), need the equivalent notation for mathematics. Is it possible using if-statements and sigma notation for this, and if so, how? ...
0
votes
1answer
53 views

What does $\overline{L}^*$ signify?

Suppose that $L$ is a language. What does $\overline{L}^*$ signify? Is $\overline{L^*}$ the same as $(\overline{L})^*$?
0
votes
1answer
45 views

How to represent a map data structure mathematically

Wondering how to represent a map object such as the following mathematically: var foo = { a: 10, b: 'bar', c: true } You could say that it was a function ...
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 ...
0
votes
1answer
314 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 ...
0
votes
1answer
84 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. <...
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, ...
0
votes
1answer
52 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 ...
0
votes
1answer
37 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?
0
votes
1answer
465 views

Principles of Programming Languages: Understanding Judgements

I am taking a principles of programming languages class right now and am trying to understand the following judgement form. ...
0
votes
0answers
30 views

Did Menezes et al. switch the letters $\mu$ and $\lambda$ in Floyd's cycle detection note 3.8?

The letters $\mu$ and $\lambda$ are usually used to represent, respectively, the length of the tail of the graph and length of the cycle in the graph. But Menezes on note 3.8, page 91 (or PDF-page 6),...
0
votes
0answers
12 views

How to denote a graph class which allows only $k$ instances of a certain induced subgraph?

Suppose that a graph class $\mathcal{C}$ is defined as follows: A graph $G$ belongs to $\mathcal{C}$ if, and only if $G$ is chordal, but has at most $k$ $5$-cycles. I am aware that the ...
0
votes
0answers
40 views

Banker's algorithm

I have a question regarding the banker's algorithm step 2. When it says the Need[i] <= work. Need is an n * m matrix and work is a vector of length m. I want to know what Need[i] <= Work means. ...
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 ...
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 ...
0
votes
1answer
21 views

Selection type generated by nested loops where initial value is current value of parent loop

Consider the generator of the selections: ...
0
votes
0answers
37 views

What are these notations O(1)/O(n)/O(log n)? [duplicate]

I am a newbie here I recently read tutorials on java about collection framework. The time complexity of various objects in reading/writing data What does it mean? ...
-1
votes
1answer
77 views

Notation: $L_R = \{w\#y\space|\space R(w,y)\}$?

What is the set $$L_R = \{w\#y\space|\space R(w,y)\}$$ Specifically what kind of conditional is $R(w,y)$? Also what's the purpose of $\#$? This comes from page 2 of the Clay paper on P vs NP: http://...
-1
votes
1answer
59 views

Clarification notation in CLRS runtime analysis

I am learning algorithms from the clrs book. I am having trouble understanding the notation the book has placed. The book wrote the following: $t_j$ denote the number of times the ...
-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
votes
1answer
38 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 } } \...
-2
votes
1answer
82 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.