Skip to main content

Questions tagged [notation]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
-1 votes
1 answer

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 ...
Palerme's user avatar
0 votes
1 answer

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?
andi's user avatar
  • 71
2 votes
0 answers

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 ...
honestSalami's user avatar
1 vote
1 answer

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 ...
Robbo's user avatar
  • 126
21 votes
3 answers

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 ...
Gaslight Deceive Subvert's user avatar
1 vote
0 answers

How to represent boolean tree + algorithm as a mathematical formula

In programming say you have a boolean tree like this: ...
Lance's user avatar
  • 141
2 votes
1 answer

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,...
Elliot Gorokhovsky's user avatar
2 votes
1 answer

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 ...
Yann Ponty's user avatar
5 votes
2 answers

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 ...
Paul Medvedev's user avatar
4 votes
1 answer

"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 ...
Daisy Sophia Hollman's user avatar
3 votes
0 answers

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 ...
isekaijin's user avatar
  • 501
2 votes
2 answers

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 ...
Christopher Aden's user avatar
3 votes
3 answers

Why do theoreticians in CS use multiple-letter variables?

This is a "dual" question of a popular post on Some mathematical objects in computational complexity theory have multiple-letter names. Complexity classes such as $\mathbf{BPP}$ have an ...
Pteromys's user avatar
  • 895
5 votes
0 answers

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))$? ...
BastienMob's user avatar
8 votes
0 answers

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 ...
machine yearning's user avatar
4 votes
1 answer

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: ...
Johannes Weiss's user avatar
1 vote
1 answer

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 ...
A T's user avatar
  • 566
11 votes
2 answers

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 $...
user14717's user avatar
  • 213
1 vote
3 answers

Is there a common mathematical symbology for collections?

Preface: So, it was suggested in 'Programmers' that I ask this over here. I am being asked to define several of my algorithms in mathematical terms to describe my work to a customer. I trying to ...
JMike's user avatar
  • 21