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
57 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 ...
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 ...
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$ ...
2
votes
1answer
156 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
24 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 ...
-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
vote
1answer
121 views

What does $CS - CF$ means?

What does $L_1 \in CS - CF$ means? I think the meaning is $L_1$ can be generated by context-sensitive grammars, but cannot be generated by context-free grammars. Am I understanding this correctly? ...
2
votes
1answer
38 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 $\...
-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
vote
1answer
57 views

What does this mean $[X]_1^T$?

I found this in information theory paper, P.3883* the authors states the following Most existing theoretic studies of network coding focus on DAGs due to its simpler structure and dure to the ...
2
votes
1answer
391 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 \...
3
votes
1answer
192 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 ...
16
votes
3answers
10k views

What is the purpose of using NIL for representing null nodes?

In my Algorithms and Data Structures course, professors, slides and the book (Introduction to Algorithms, 3rd edition) have been using the word NIL to denote for ...
3
votes
2answers
109 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
2answers
268 views

Expressing that a function converges to 1 with linear rate using Landau notation

I am working on an algorithm which approximates a certain optimal quantity. The approximation becomes better when the size of the problem ($n$) becomes larger: the difference from the optimum is ...
2
votes
3answers
98 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{...
1
vote
2answers
9k 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 ?...
2
votes
1answer
88 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: ...
3
votes
1answer
51 views

How to state that a complexity bound does not depend on a given parameter size?

I am often ill at ease with Landau (Big O) notation, because it seems often to be abusing mathematical notation. The best example is the use of the equal sign to express a set membership. And this can ...
6
votes
4answers
171 views

Can I use ellipses in first order logic

I ask, because I have to come up with a first-order logic sentence that shows that there are exactly N objects in the universe. What I've been able to come up with is: $$ \forall x \; \exists y_1, ...
6
votes
1answer
420 views

type theory notation troubles

I'm working through "Types and Programming Languages" by Benjamin Pierce and I don't quite understand the notation. Particularly on Page 106, (chapter 9 Simply Typed Lambda-Calculus) there is a lemma (...
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) ...
3
votes
1answer
61 views

What does does $O$ mean in this context?

I understand big O notation in computational complexity theory, but I don't see how it applies in the equation below. From Pattern Recognition and Machine Learning: If we weren't familiar with the ...
3
votes
2answers
102 views

Differences in Postfix Syntax

A question about postfix/RPN came up in my class due to the current ACSL competition. Is it a rule or convention that 4 + (5 * 6) in infix is written 4 5 6 * + in postfix, as opposed to 5 6 * 4 + in ...
0
votes
1answer
744 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 ...
2
votes
2answers
494 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 ...
3
votes
1answer
106 views

Hierarchy of complexity classes $\bigcup_{c > 0} \mathrm{Time}(2^{c \log^k n})$, w.r.t. $k$

This is a true/false question: For each integer $k > 1$, define the complexity class $\sf QP_k := \bigcup_{c > 0} Time(2^{c \log^k n})$. Then for all integers $k > 1$, $\sf QP_k \subsetneq ...
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: ...
4
votes
1answer
756 views

Determining Number of States in a Turing Machine

I am looking at an example Turing machine in my textbook, Automata and Computability by Dexter C. Kozen, and I'm confused as to how they determine the number of states this particular machine has. The ...
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. ...
6
votes
1answer
128 views

Use of Big O Notation in a recent paper by Khot et al

I'm reading a paper about Constraint Satisfaction Problems, specifically "A Characterization of Strong Approximation Resistance", Subhash Khot, Madhur Tulsiani, Pratik Worah (ECCC TR13-075). The ...
10
votes
1answer
5k views

Can a Big-Oh time complexity contain more than one variable?

Let us say for instance I am doing string processing that requires some analysis of two strings. I have no given information about what their lengths might end up being, so they come from two distinct ...
3
votes
2answers
83 views

Origins of misconception about using equality signs with Landau notation

From "Misconception 1" from Søren S. Pedersen's blog, and as many have seen before, a major misconception in Big-O (and others) notation is to say a function is "equal" to Big-O of some other function:...
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?
5
votes
1answer
77 views

In type systems, is there a name for SQL's way of cutting and combining record types into new types?

I'd like to have this feature in my application programming language (which these days, is Scala), but when I went to learn more about it on the internets, I realized I don't know the name of it. I'm ...
3
votes
1answer
222 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 ...
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? ...
3
votes
0answers
130 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
1answer
2k views

What does the R superscript notation mean in regular/formal languages?

What does the capital R superscript notation mean in regular languages? I am working on a homework assignment and don't recall my professor mentioning what the what the R superscript means. For ...
3
votes
2answers
849 views

What type of formal notation is being used here to represent functional algorithms?

Interested in learning more about algorithm design in functional programming, I picked up Andrew Bird's Pearls of Functional Algorithm Design. I have experience with a number of programming languages,...
5
votes
2answers
146 views

Numeral systems other than unary used in nature or in animal and human behaviours

Representing numeric values using positional notation is one of the milestones in the history of arithmetic. Babylons used a base 60 system, Maya a base 20 system; base 10 system became "the standard" ...