# 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
167 views

### What does $n^{O(1)}$ mean?

I read an example that said explain what "$f(n)$ is $n^{O(1)}$" means. I can't interpret the $n^{O(1)}$ syntax. I know what Big $O$ notation is, its just that this example looks odd to me.
773 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 ...
277 views

### “Smallest set” term in the trees set definition

I often meet such kind of the definition of the set of trees, as: The set of unranked $\Sigma$-trees, denoted by $T$, is the smallest set of strings over $\Sigma$ and the parenthesis symbols ‘)’ and ‘...
40 views

### What does it mean the norm symbol applied to a concept?

I'm reading this paper: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.150.14 or http://www.jmlr.org/papers/volume10/kontorovich09a/kontorovich09a.pdf On page 1101 are introduced 2 functions ...
360 views

### Addition modulo 2 notation (Quantum Computing)

I am studying Quantum Computing using the book Quantum Computation and Quantum Information of Michael Nielsen and Isaac Chuang. I am confused by the meaning of the $\oplus$ (addition modulo 2) symbol ...
91 views

### How to negate this one?

How can I negate the following sentence: For all words x from L with |x|>= n , exists decomposition x = uvw with |uv| <= n and |v| >= 1, so for all i >= 0 , is valid that u(v)^iw in L is.
225 views

### Set notation of the set of all strings

How do I present the complement using set notation? I guess it has to be shows with universal set - {aa,bb} but I do not know how to represent the universal set in ...
62 views

### What do the commas separating atomic events in a Relational Calculus formula means?

For instance, take the example of this book here on page 30. About the formula $$Q(x,x') = R(x), S(x,y), S(x',y), R(x')$$ described there, what do the commas mean? Is it the same as an "and" ...
53 views

### Trouble understanding Grammar Rules

I am totaly new to theoretical computer science, so I am sorry if I get the terminology wrong: I was reading the definition of a grammar, what I didn't get was the formal definition of the production ...
308 views

### Meaning of double colon $::$

I've came across this expression regarding function composition in some notes by people from computer science, and I don't know what the notation "$::$" means. g \circ f : A \...
47 views

9k views

### What's the difference between the concatenation and union of symbols within a language

I feel like I'm confusing myself perhaps but I'm having a bit of trouble figuring out how exactly this language works. I'm given the following regular expression (a + b)* (abba* + (ab)*ba) Can ...
333 views

### How to read 'max min' and 'min max'?

Here is an exercise I came across while studying MaxFlow / MinCut and I'm rather stumped: Designate $G = (V, E)$ as an undirected graph that has at least two vertices. Every edge $(e)$ on this ...
278 views

### How do I interpret this divide and conquer algorithm for removing duplicates in a list?

Consider the following divide and conquer algorithm to remove duplicates in a list. The text is in French. What is the meaning of the variables $c1, c2, d1, d2$? Why are only the variables $c1, d1$ ...
483 views

### Why are Complexity Notations Called Asymptotic?

Why do we use the term "asymptotic" in complexity. Although I know what an asymptote is, but what is an asymptote doing here?
38 views

### Where, besides Scheme reports (RnRS) has Stoy's notation for auxiliary semantic functions been used?

The denotational semantics of R4RS, R5RS and R7RS Scheme (included in the language report) uses the same notation that was used by J. E. Stoy in his book, "Denotational Semantics: the Scott-Strachey ...
268 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 ...
45 views

### Question on interpreting logical notation, relating to alphabets, theoretical comp sci

$\exists x \in \Sigma^* (t=sx)$ Have I interpreted the above into words correctly?: "There exists a symbol 'x', which is a member of the set which contains all possible strings of alphabet sigma, ...
When talking about DFAs and NFAs as 5-tuples, it's common to use the letter $Q$ to denote the set of states in the automaton and to denote individual states with names like $q_0$, $q_1$, etc. Is ...
I am studying for a test in Logic right now, and saw the symbol $\underset{x}{=}$, which is used like this: $I \underset{x}{=} I'$. I've seen it in the solutions of questions like this one: Prove ...