Skip to main content

Questions tagged [notation]

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

Filter by
Sorted by
Tagged with
47 votes
2 answers
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 ...
JW.'s user avatar
  • 581
0 votes
1 answer
79 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?
stud1's user avatar
  • 317
1 vote
1 answer
77 views

How to express taking the next bit of an infinite string in small-step semantics?

I have to write a rule as part of a small step operational semantics (https://en.wikipedia.org/wiki/Operational_semantics). Whenever this rule is applied, the next bit belonging to an infinite bit ...
Enrico's user avatar
  • 11
1 vote
3 answers
519 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 ...
Celeritas's user avatar
  • 171
2 votes
1 answer
80 views

Meaning of $\stackrel{*}{\rightarrow}$ production rule?

I've seen the production rule $\stackrel{*}{\rightarrow}$ in some papers concerning regular languages. What's the meaning of $\stackrel{*}{\rightarrow}$ production rule?
mavavilj's user avatar
  • 579
1 vote
1 answer
61 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 ...
mavavilj's user avatar
  • 579
0 votes
1 answer
168 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 ...
user21316's user avatar
1 vote
1 answer
23 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$ ...
Revolucion for Monica's user avatar
2 votes
1 answer
214 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 ...
Adam Streck's user avatar
2 votes
1 answer
34 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 ...
FK82's user avatar
  • 273
-1 votes
1 answer
135 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 ...
user's user avatar
  • 129
1 vote
1 answer
231 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? ...
kate's user avatar
  • 327
2 votes
1 answer
53 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 $\...
mavavilj's user avatar
  • 579
-1 votes
1 answer
82 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://...
mavavilj's user avatar
  • 579
2 votes
1 answer
87 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 fact ...
user777's user avatar
  • 749
2 votes
1 answer
647 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 \...
mafu's user avatar
  • 339
3 votes
1 answer
347 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 ...
Nathaniel M. Beaver's user avatar
22 votes
3 answers
24k 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 ...
user avatar
3 votes
2 answers
135 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\...
John F's user avatar
  • 31
3 votes
2 answers
271 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 ...
Erel Segal-Halevi's user avatar
2 votes
3 answers
120 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{...
Arti C's user avatar
  • 21
6 votes
2 answers
17k 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 ?...
Roberto Fernandez Diaz's user avatar
2 votes
1 answer
96 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: ...
Ahmad's user avatar
  • 449
3 votes
1 answer
65 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 ...
babou's user avatar
  • 19.5k
6 votes
4 answers
281 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, ...
Colin's user avatar
  • 63
7 votes
1 answer
792 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 (...
Hath995's user avatar
  • 215
1 vote
2 answers
89 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) ...
Brent.Longborough's user avatar
3 votes
1 answer
77 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 ...
Kelmikra's user avatar
  • 726
3 votes
2 answers
120 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 ...
Adam-Morgan's user avatar
0 votes
1 answer
1k 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)$...
Akatzki's user avatar
  • 33
0 votes
1 answer
281 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 ...
ka8512's user avatar
  • 5
1 vote
0 answers
462 views

Reverse Polish to infix

I have to convert "A = B C + D E + ×" from reverse polish notation to infix. I'm a bit confused because of the equals sign. Is that an operator too? This is my answer: A = (B+C) × (D+E) Is this ...
Tim's user avatar
  • 29
2 votes
2 answers
1k 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 ...
prince's user avatar
  • 129
3 votes
1 answer
151 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 ...
Tingshuo's user avatar
0 votes
1 answer
24 views

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

Consider the generator of the selections: ...
Ali's user avatar
  • 113
4 votes
1 answer
2k 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 ...
tdark's user avatar
  • 155
0 votes
1 answer
540 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. ...
user avatar
6 votes
1 answer
148 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 ...
Mark's user avatar
  • 215
20 votes
1 answer
15k 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 ...
corsiKa's user avatar
  • 423
4 votes
2 answers
109 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:...
Ryan Dougherty's user avatar
1 vote
1 answer
197 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?
qazwsx's user avatar
  • 131
5 votes
1 answer
105 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 ...
Rob N's user avatar
  • 153
3 votes
1 answer
394 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 ...
Rawb's user avatar
  • 245
0 votes
0 answers
39 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? ...
MaheshVarma's user avatar
3 votes
0 answers
154 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 ...
Edd Barrett's user avatar
3 votes
1 answer
289 views

For complexity classes A and B, what does $A^B$ mean?

What does $A^B$ mean where A and B are complexity classes? The "Polynomial Hierarchy" page says: $A^B$ is the set of decision problems solvable by a Turing machine in class A augmented by an oracle ...
dspyz's user avatar
  • 416
5 votes
1 answer
4k 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 ...
Unnamed's user avatar
  • 153
3 votes
2 answers
939 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,...
David Kaczynski's user avatar
5 votes
2 answers
178 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" ...
Vor's user avatar
  • 12.6k

1 2 3
4