# Tag Info

17

Order of precedence is simply a notional convenience. There is no notion of strength here, just notation. All three operators are unary operators with notation "$\circ\ \cdot$", where $\circ$ denotes the operator symbol $\exists, \forall,\neg$ and $\cdot$ the operand. There can never be any ambiguity in which order to apply these operators: the operator to ...

7

Here is the original statement in CLRS. Assume that we have a connected, undirected graph $G$ with a weight function $w: E\to\Bbb R$, and we wish to find a minimum spanning tree for $G$. It is pretty good to understand "a weight function $w:E\rightarrow \mathbb{R}$" as "an edge has a weight". In fact, that is how I would interpret that notation in a rush ...

5

It means that each edge has only one weight, which is defined as a real number. So, this definition in compact form excludes many cases, for example: an edge doesn't have weight at all an edge has two (or more) weights an edge has weight as a complex number etc.

3

Non-deterministic guarded choice is an associative-commutative binary operator. My guess is that the character ⫾ U+2AFE is intended to be used as an infix binary operator and the character ⫿ U+2AFF, which is larger and described as “n-ary”, is intended to be used as a prefix operator which is typeset larger, in prefix position, and typically with a subscript ...

3

I don't know if there is a correct or recommended usage of Unicode codepoints for the LTL operators, but the mapping we used in LaTeX was the following: □ (U+25A1) => \Box ◇ (U+25C7) => \Diamond ○ (U+25CB) => \medcirc (from txfonts/pxfonts)

3

The class $O(f(n))$ consists of all functions $\phi$ such that for some $N,c > 0$, we have $\phi(n) \leq Cf(n)$ for all $n \geq N$. The class $2^{O(f(n))}$ is simply $$2^{O(f(n))} = \{ 2^{\phi(n)} : \phi(n) = O(f(n)) \},$$ which is essentially what you wrote. A different way of looking at this is that $O(f(n))$ stands for some function $\phi(n)$ such ...

3

I thought the order of precedence of operators and quantifiers was arbitrary Certainly the rules of precedence could be set up in different ways, but some ways are more helpful and convenient than others, and there are principled reasons for this. but I don't really understand why those three have the same "strength" in relation to other operators (e.g., ...

2

For bounded sets, the usual convention is to use interval notation. Specifically, $[a,b]$ means "real numbers between $a$ and $b$, inclusive", while $[a\mathinner{\ldotp \ldotp}b]$ means "integers between $a$ and $b$, inclusive". Changing any of the square brackets to curved means that endpoint is not included: $a \not\in (a,b]$, for example. In this case, ...

2

Given a language $L$, let $L_0 = \{\epsilon\}$ and, for $i\geq 1$, let $L_i = \{w_1\circ \dots\circ w_i \mid w_j\in L \text{ for each } j\}$, where $\circ$ denotes concatenation. Then the Kleene closure of $L$ is the language $L^* = \bigcup_{i\geq 0} L_i$.

2

It's a convention. One reason for the convention is that the length of an array $A[i..j]$ is $j-i+1$, so if $j=i-1$, we should get an array of length zero. Due to this reason, we sometime consider $A[i..j]$ to be undefined when $j < i-1$; in other cases, the issue does not arise, and $A[i..j]$ is just the empty array whenever $j < i$. In yet other ...

1

The symbol $\space ≃ \space$ means "asymptotically equal to". So when you read $n ≃ i$, you can read it as $n$ asymptotically approaches $i$. This means that the more $n$ increase in size, the more $i$ increase in size but $n$ never become equal to $i$. I mean suppose $n=1000$ and so $i=2,4,16,32,256,65536$ is in every steps. This contains an error: ...

1

Yes, you may consider this as axiom. Or try to make a definition that still works for a > b case - most probably it will give you an empty array in this case. For example, "all elements with indexes i >= a and i < b".

1

Perhaps what you're missing (although you seem to suspect) is that the left hand side of the $⊢$ is not just for specifying what types variables have. In fact, as you've noted, it doesn't necessarily have all (or only) the variables on the right hand side (although in this situation it does only have variables, not things like $λy.x : α→β$). What it's doing ...

1

A[i..j] is a convention. We could define it any way we like, but we define it in a way that gives useful results. One property is that if we reduce the right index by 1, then we lose the rightmost element. For example, going from A[5..10] to A[5..9] we lose element 10. So what is A[i..i] and what would you expect going from A[i..i] to A[i..i-1]?

1

The notation $A \le_pB$ means problem $A$ can be reduced to problem $B$ in polynomial time, and that $B$ is at least as hard as $A$, because solving $B$ means solving $A$. $A \le_pB$ $\equiv$ $B \ge_pA$ It does $\mathbf{not}$, however, mean $B \le_pA$, and to claim as much you would have to show the appropriate reduction.

Only top voted, non community-wiki answers of a minimum length are eligible