Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [notation]

The tag has no usage guidance.

19 questions
Filter by
Sorted by
Tagged with
86 views

### notation in graph theory [closed]

I was reading a paper, and I found a notation that I don't understand: $\mathbb{E}[| \textbf{S} |]$, where $\textbf{S}$ is a set. Are there any differences with the notation $\mathbb{E}[formula]$ (I ...
153 views

### What does x.y notation mean?

In Harper's PFPL (Ed. 2, top of page 8), this notation is used but I don't see a definition. What does $x.y$ mean?
• 71
78 views

### Is there a list of notations developed for regular expressions? [closed]

There is, of course, PCRE. I know also of Olin Shiver's Structural Regular Expressions, and Rob Pike's Structural Regular Expressions. I also understand that Raku's regexps are different from perl's ...
• 121
1 vote
73 views

### What are the widely used notations for quickly referring to a single component of a multi-component object?

I have the need to define a multi-component object type for which I provide numerous definitions throughout the text. However, in most of these definitions, I only need to refer to one or two of the ...
• 126
3k views

### Why colon to denote that a value belongs to a type?

Pierce (2002) introduces the typing relation on page 92 by writing: The typing relation for arithmetic expressions, written "t : T", is defined by a set of inference rules assigning types to ...
1 vote
178 views

### How to represent boolean tree + algorithm as a mathematical formula

In programming say you have a boolean tree like this: ...
• 141
147 views

### Preferable way to express $O(n2^n)$

Is it preferable to write $O(n2^n)$ or $O((2 + \epsilon)^n)$? If neither, what is the best way? Since I see a lot of papers with $O(1.42^n)$ instead of $O(2^{\frac{n}{2}})$ and similar transformations,...
136 views

### What is the standard name for the function which inflates a string by duplicating each of its characters?

Given a string $s$ over some alphabet, I'd like to use the proper nomenclature/notation for the operation/function $f$ which inflates $s$ by independently duplicating each of its characters. For ...
821 views

### Is there notation for converting a multi-set to a set?

Suppose we have a multi-set $S$. For example, $S = \{ 1,2,2,3 \}$. Suppose we also have a set $T$, e.g., $T=\{1,2,3\}$. I would like to say, compactly, that $S$, when its duplicates are removed, is ...
251 views

### "a" or "an" with big O notation?

A simple (though somewhat pedantic) question: when using big O notation in a sentence, should it be preceded with "a" or "an"? Example: The extra loop results in a/an $\mathcal{O}(N)$ increase in ...
100 views

### How to develop an effective notation for a partially ordered logic?

I am developing a logic for reasoning about programs in a resource-constrained environment. My starting point is intuitionistic linear logic, but I made the following changes: In intuitionistic ...
• 501
366 views

### What is this notation style called?

I was reading a paper about implementing the statistical programming language R on the JVM, and encountered this notation I haven't seen before (I'm not formally CS-trained). What is the name of ...
557 views

### Why do theoreticians in CS use multiple-letter variables?

This is a "dual" question of a popular post on math.se. Some mathematical objects in computational complexity theory have multiple-letter names. Complexity classes such as $\mathbf{BPP}$ have an ...
• 895
278 views

### Big O notation for "modulo a polynomial"

Is there a notation that would be like the Big O notation (let's say Big P), but with the following definition: $f=P(g)$ if there exists a polynomial p such that for n large enough, $f\leq p(g(n))$? ...
1k views

### Names for the left- and right-hand sides of a grammar production?

Problem I'm writing a document where I have to describe some of the properties of a type system as they relate to a particular formal grammar. I was trying to refer to the right-hand-sides of the ...
407 views

### Formal Representation of Haskell Data-Types

I come from Haskell programming and currently writing my (Diploma/Master) thesis. I'm having trouble finding a formal/mathematical notation for a Haskell data-type. The Haskell data type is: ...
1 vote
2k views

### Worst-case asymptotic-complexity of the Set-cover problem?

What's the worst-case asymptotic-complexity of the Set-cover problem in Big O notation? I've been developing some novel techniques to try and solve this problem but am having trouble finding the ...
• 566
622 views

### Notation for a Conditional Hamiltonian Evolution Operator

I am reading Harrow, Hassidim, and Lloyd's paper Quantum algorithms for linear systems of equations. On the third page of that paper, they write Next we apply the conditional Hamiltonian evolution \$...
• 213
1 vote