Questions tagged [notation]
Use this tag whenever you have a question about what some particular symbol/notation means.
198
questions
2
votes
1
answer
711
views
Definition feels contradictory (Computational Complexity Theory)
I studied a definition for time complexity:
Let $M$ be a deterministic Turing Machine. The running time of $M$ is said to be:
for a function $t: \mathbb{N} \to \mathbb{N}$ ($\mathbb{N}$ is natural ...
- 23
3
votes
1
answer
54
views
graph theory single bar vs double bar size notation
A follow-up on https://stackoverflow.com/questions/15037679/what-do-the-absolute-value-bars-mean-in-graph-theory
What is the difference between single bar $|G|$ and double bar $||G||$ notation (both ...
- 807
4
votes
2
answers
147
views
What does $o_n(1)$ mean?
I'm trying to read the following article, and in the abstract they write:
Let $\xi$ be a non-constant real-valued random variable with finite support, and let $M_n(\xi)$ denote a $n\times n$ random ...
- 43
2
votes
0
answers
118
views
SCoP, Iteration Domain in Polyhedral Optimization and use of Presburger arithmetic
Context:
While exploring the fundamentals of polyhedral optimization and attempting to explore a connection from the input Static Control Part (SCoP) to the iteration domain from birds eye view, I am ...
- 123
1
vote
0
answers
13
views
Is there a symbol in FA/FSM for everything else
I remember in a Computability Theory class building a state machine for an assignment that required many 'go-back' transitions on $\Sigma - symbols$ for all symbols not already handled. This was very ...
- 111
0
votes
1
answer
35
views
An elementary question about grammar
Recently, I am studying grammar in automata. And, I have few information about this subject.
I have a grammar with rules $\{S\to ASA, A\to aA, A\to \epsilon\}$.
Is it true if I say that $S\to aASA$ ...
- 13
-1
votes
1
answer
112
views
Understanding reductions and notation
I am currently working through Sipser's Introduction to the Theory of Computation. In chapter 5, he defines that a Language $A$ is mapping reducible to language $B$, written $A\leq_m B$ if there is a ...
- 1
2
votes
2
answers
63
views
Is there a common notation for describing this operation $coNP\; ? \; NP = DP$?
While working with complexity classes, I've come along the definition of $DP$ (or $D^p$):
$$DP = \{L_1 \cap L_2 \mid L_1 \in NP \text{ and } L_2 \in coNP\}$$
I am interested in a different (and much ...
- 321
0
votes
0
answers
85
views
Function types in Computer Science Metanotation
See Guy Steele's slides for what I refer to by "Computer Science Metanotation", specifically the bits about BNF.
I often make use of the BNF syntax observed there, as a substitute for ...
- 141
0
votes
1
answer
66
views
When to use subscript and when to make it a function?
Let's say, I have a set of cats $C = \{ a, b, c, ... \}$. Each cat has a tail. I can say, that the lengths of the tails of cats are denoted as $t_a$, $t_b$, etc. Otherwise, I can say that they are ...
- 113
11
votes
3
answers
3k
views
Is Big-Theta a more accurate description of worst case run time than Big-O?
Question I was asked: Does it make a difference if I say "The worst case run time is $O(n^2)$ vs the worst case run time is $\Theta(n^2)$?"
To me, the only difference is that when we say $O(...
0
votes
1
answer
38
views
Does $L = \{a^n \ | \ n \geq 1, \ n \ \text{ is even or a square number}\}$ have infinite equivalence classes?
I am unsure if it has infinite equivalence classes or not, respectively how to interpret the textbook solution.
My approach was that it has infinite because,
lets say we have $x = a^5$ and $y = a^7$.
...
- 17
0
votes
3
answers
98
views
Is there a notation for types?
Is there a notation for statements like the following:
If both operands are of type int, then the result is of type int. If ...
- 123
1
vote
0
answers
35
views
Dot symbol in set-builder expressions in CRDT literature?
In Conflict-free Replicated Data Types: An Overview and other CRDT-related publications by Preguiça's group, a dot symbol often appears without definition. What does it indicate, how standard is it as ...
- 11
1
vote
1
answer
43
views
What does :: indicate in all-quantifier predicates?
Can somebody explain to me the meaning of $::$ in the following predicate?
$$(\forall i : P(i) : Q(i)) \equiv (\forall i :: P(i) \implies Q(i))$$
- 123