# Questions tagged [notation]

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

144 questions
Filter by
Sorted by
Tagged with
3answers
184 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 ...
1answer
74 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?
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 ...
1answer
43 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 ...
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$ ...
1answer
158 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 ...
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 ...
1answer
61 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 ...
1answer
128 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? ...
1answer
38 views

1answer
197 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 ...
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 ...
2answers
109 views

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 ?...
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: ...
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 ...
4answers
173 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, ...
1answer
435 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 (...
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) ...
1answer
65 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 ...
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 ...
1answer
774 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)$...
1answer
195 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 ...
2answers
505 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 ...
1answer
108 views

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 ...
1answer
225 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 ...
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? ...
0answers
131 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 ...
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 ...
2answers
851 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,...
2answers
148 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" ...