Active questions tagged notation - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2020-01-20T02:13:45Z https://cs.stackexchange.com/feeds/tag/notation https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/118637 0 Transformation Function: Gonzalez and Woods Turing101 https://cs.stackexchange.com/users/106281 2019-12-17T12:46:03Z 2020-01-16T14:02:25Z <p>I have been reading Image Processing from Gonzalez and Woods and in the chapter Image Transformation I have come across this equation</p> <p><span class="math-container">$$T \left(u, v\right) = \sum_{x=0}^{M-1} { \sum_{y=0}^{N-1} { f \left(x, y\right) \, r \left(x, y, u, v\right) } } \,.$$</span></p> <p>I am unable to understand this mathematical notation. Any help will be highly appreciated. Thanks</p> https://cs.stackexchange.com/q/118313 1 Why in the code i ≃ n? Michael https://cs.stackexchange.com/users/112683 2019-12-10T11:33:57Z 2019-12-10T13:40:07Z <pre><code>i=2; while(i&lt;n) { write('*'); i=i*i; } </code></pre> <p>Why <span class="math-container">$n ≃ i$</span>?</p> <p>I mean suppose <span class="math-container">$n=1000$</span> and so <span class="math-container">$i= 2,4,16,32,256,65536$</span> is in every steps.</p> <p>In the book wrote <span class="math-container">$2^2 power(k)$</span> is pattern for growing <span class="math-container">$i$</span> so <span class="math-container">$n ≃ i$</span> and...</p> <p>Now 65536 or 256 isn't equal to 1000 or around 1000.</p> <p>But why <span class="math-container">$n ≃ i$</span>?</p> <p>This chapter is about notations.</p> https://cs.stackexchange.com/q/35815 1 Reverse Polish to infix Tim https://cs.stackexchange.com/users/26241 2014-12-31T21:39:50Z 2019-12-08T20:57:06Z <p>I have to convert "A = B C + D E + ×" from reverse polish notation to infix. I'm a bit confused because of the equals sign. Is that an operator too?</p> <p>This is my answer: A = (B+C) × (D+E)<br> Is this correct or would this be written another way?</p> https://cs.stackexchange.com/q/115967 3 Difference between ⫾ (U+2AFE) and ⫿ (U+2AFF) in the context of Dijkstra's Guarded Command Language? user110815 https://cs.stackexchange.com/users/0 2019-10-18T08:41:48Z 2019-10-18T18:13:00Z <p>Continuing <a href="https://tex.stackexchange.com/questions/435986/how-to-draw-the-box-of-dijkstras-guarded-command-language">https://tex.stackexchange.com/questions/435986/how-to-draw-the-box-of-dijkstras-guarded-command-language</a>, what is the difference in the intended usage of ⫾ (Dijkstra choice, U+2AFE) and ⫿ (n-ary Dijkstra choice, U+2AFF) in the context of the Guarded Command Language (GCL) of Dijkstra? In other words, when do you use ⫾ and when ⫿ for typesetting GCL programs?</p> <p>Related: </p> <ul> <li><p><a href="http://latex.org/forum/viewtopic.php?t=32939" rel="nofollow noreferrer">http://latex.org/forum/viewtopic.php?t=32939</a></p></li> <li><p><a href="https://tex.stackexchange.com/a/435995">Barbara's take on GCL</a></p></li> </ul> https://cs.stackexchange.com/q/115321 2 Typesetting LTL in Unicode? MdAyq7 https://cs.stackexchange.com/users/109998 2019-10-01T17:14:39Z 2019-10-09T04:17:14Z <p>Unicode has an abundance of open circles, diamonds and boxes. Using these, we can typeset linear-time temporal logic formulas such as</p> <p><span class="math-container">$$(\mathop{⬦}ψ)\ \,\land\ \,\mathop{⬦}(θ\ \mathsf{U}\ \mathop{◻}\mathop{○}φ)\ \ .$$</span></p> <p>However, in my browser, the sizes of the symbols vary too much; the heights don't match, and the result looks ugly. The same happens in LaTeX (though, you could fiddle with sizes there manually in some circumstances, but it's a mess). Are there any "proper" Unicode codepoints made specifically for typesetting LTL formulas? I failed to find any, but, maybe, I have not looked everywhere. As the pre-Unicode LTL standard take a look into the papers and books by Manna/Pnueli, e.g., <a href="http://theory.stanford.edu/~zm/tvors3.html" rel="nofollow noreferrer">http://theory.stanford.edu/~zm/tvors3.html</a> .</p> <p>Crosspost: <a href="http://latex.org/forum/viewtopic.php?f=46&amp;t=32886" rel="nofollow noreferrer">http://latex.org/forum/viewtopic.php?f=46&amp;t=32886</a></p> https://cs.stackexchange.com/q/113416 4 Exact meaning of $2^{\mathcal{O}(f(n))}$ Dan https://cs.stackexchange.com/users/98686 2019-09-04T16:02:55Z 2019-09-04T17:38:55Z <p>In Sipser's Introduction to the Theory of Computation he uses the notation <span class="math-container">$2^{\mathcal{O}(f(n))}$</span> to denote some asymptotic running time.</p> <p>For example he says that the running time of a single-tape deterministic turing machine simulating a multi-tape non-deterministic turing machine is</p> <p><span class="math-container">$\mathcal{O}(t(n)b^{t(n)})=2^{\mathcal{O}(t(n))}$</span> where <span class="math-container">$b$</span> is the maximal number of options in the transtition function.</p> <p>I was wondering if someone can clarify the exact definition of this for me:</p> <p>My assumption is that if <span class="math-container">$g(n)=2^{\mathcal{O}(f(n))}$</span> then there exists <span class="math-container">$N \in \mathbb{Z}$</span> and <span class="math-container">$c \in \mathbb{R}$</span> s.t.</p> <p><span class="math-container">$g(n) \leq 2^{cf(n)}=(2^{f(n)})^c$</span> for all <span class="math-container">$n&gt;N$</span>.</p> <p>Thank you</p> https://cs.stackexchange.com/q/112017 3 Weight functions in graph algorithms RichArt https://cs.stackexchange.com/users/75941 2019-07-20T15:10:25Z 2019-07-21T02:02:27Z <p>In text books, for instance in the 3rd edition of <em>Introduction to Algorithms</em>, Cormen, on page 625, the weights of the edge set <span class="math-container">$E$</span> is defined with a weight function <span class="math-container">$w:E\rightarrow \mathbb{R}$</span>.</p> <p>Why is it defined in this way? Why do we need a function? I mean, we all know when working with a graph, that the meaning is just that an edge <span class="math-container">$(u,v)$</span> has a weight <span class="math-container">$w$</span>. So, why is it written with a function? I remember the first time I saw this definition I was very confused. Only after actually going through an algorithm and reading it again, I realized that it really just means that every edge has its weight.</p> <p>So, I still don't fully understand why it is written in this complicated way and what exactly it means though, and it would be very nice if someone could tell me that in a understandable language.</p> https://cs.stackexchange.com/q/44552 3 Properties of Reverse Polish Notation expressions that are algebraically invariant Nathaniel M. Beaver https://cs.stackexchange.com/users/35657 2015-07-20T03:55:57Z 2019-07-12T07:56:37Z <p>The RPN expressions</p> <pre><code>a b + c * </code></pre> <p>and</p> <pre><code>f d e + * </code></pre> <p>are algebraically equivalent, though the names of the variables are different and the order of evaluation is slightly different. The expressions</p> <pre><code>a b * c + a b * c * </code></pre> <p>though they have the same length and number of variables as the first expression, are not algebraically equivalent, i.e. in general</p> <pre><code>c (a + b) ≠ c + a * b c (a + b) ≠ a * b * c </code></pre> <p>Without substituting values for any of the variables, is there a property that we could compute which is the same for <code>a b + c *</code> and <code>f d e + *</code> but not for <code>a b + c *</code> and <code>a b * c +</code> or <code>a b * c *</code>?</p> <p>Assume the variables are real numbers, not e.g. matrices, so <code>+</code> and <code>*</code> are commutative, but <code>-</code> and <code>÷</code> are not.</p> <p>This is a simple example of a broader question I am interested in: what are some properties that RPN expressions (i.e. unambiguous expression trees) have that are different for algebraically different expressions but do not change when the names or order of evaluation of the variables change?</p> <p>This would be useful because it would be a kind of fingerprint for algebraic expressions that would not change merely because of choice of variable names.</p> <p>I realize that this could be a big topic; references to sections of textbooks or research articles are welcome.</p> https://cs.stackexchange.com/q/111563 1 Asymptotic notation and random variables user1246462 https://cs.stackexchange.com/users/107313 2019-07-06T22:43:31Z 2019-07-07T17:30:18Z <p>I have two random variables <span class="math-container">$X$</span> and <span class="math-container">$Y$</span> and I want to bound the value of one in terms of the other (for now, I don't care about the actual distribution of their values). </p> <p>Suppose that the two variables can have different distributions with values chosen from <span class="math-container">$[1, n]$</span>. But <span class="math-container">$X$</span> is always upper bounded by <span class="math-container">$Y \cdot c\log{n}$</span> for some constant <span class="math-container">$c$</span>. Can I write this as <span class="math-container">$X = O(Y\log{n})$</span> (if I care about the behavior for large <span class="math-container">$n$</span>). I'm not sure what is the convention wrt to random variables and asymptotic notation.</p> https://cs.stackexchange.com/q/111461 1 Meaning of L* if L is a language ffff https://cs.stackexchange.com/users/107207 2019-07-03T12:29:43Z 2019-07-04T04:38:37Z <p>I can't find anywhere the meaning of <span class="math-container">$L^*$</span>, given that <span class="math-container">$L$</span> is a language. I know <span class="math-container">$^*$</span> means repetition, for example <span class="math-container">$0^*$</span> = <span class="math-container">$\{ \epsilon, 0, 00, 000, \dots \}$</span>. Or if <span class="math-container">$A$</span> is an alphabet <span class="math-container">$A^*$</span> are all the possible words.</p> <p>Does <span class="math-container">$L^*$</span> mean the language whose words are the concatenation of the words of <span class="math-container">$L$</span>?</p> <p>For example if <span class="math-container">$L=\{ 01^n \mid n&gt;0 \}$</span></p> <p>then is <span class="math-container">$L^* = \{ 01^{n_1}01^{n_2} \dots \mid n_1&gt;0, n_2&gt;0, ... \}$</span>?</p> https://cs.stackexchange.com/q/111375 3 Why is subarray $A[p..k-1]$ empty when $k=p$? DataBSc https://cs.stackexchange.com/users/101539 2019-07-01T15:19:54Z 2019-07-03T09:40:25Z <p>I'm working through a proof of correctness for merge sort.</p> <p>I'm given a loop invariant for a for loop, which makes reference to a subarray <span class="math-container">$A[p..k-1]$</span>. During the initialization step of the correctness proof, my textbook says "Prior to the ﬁrst iteration of the loop, we have <span class="math-container">$k=p$</span>, so that the subarray <span class="math-container">$A[p..k-1]$</span> is empty".</p> <p>In other words we're saying <span class="math-container">$A[p..p-1]$</span> is empty. Suppose <span class="math-container">$p=1$</span>, then it's saying <span class="math-container">$A[1..0]$</span> is empty. Why is this considered empty? Is it just an axiom that subarray <span class="math-container">$A[a..b]$</span> is empty if <span class="math-container">$a&gt;b$</span>?</p> https://cs.stackexchange.com/q/110756 2 When and what must be present on the left-hand side of the turnstile in metalogics? gaazkam https://cs.stackexchange.com/users/81796 2019-06-16T15:33:04Z 2019-06-16T18:53:10Z <p>Let me show the problem on an example...</p> <p>An actual task from one of the former exams:</p> <blockquote> <p>Consider a simple functional language:</p> <p><span class="math-container">$$e::= x|n|e_1e_2|\lambda x.e$$</span></p> <p>With typing rules:</p> <p><span class="math-container">$$\tau ::= \mathtt{int} | \mathtt{foo} | \tau_1 \rightarrow \tau_2$$</span></p> <p><span class="math-container">$$\Gamma \vdash n : \mathtt{int}$$</span></p> <p><span class="math-container">$$\Gamma (x : \tau) \vdash x : \tau$$</span></p> <p><span class="math-container">$$\begin{array} {c} \Gamma(x : \tau) \vdash e : \rho \\ \hline \Gamma \vdash \lambda x.e : \tau \rightarrow \rho\end{array}$$</span></p> <p><span class="math-container">$$\begin{array}{c} \Gamma\vdash e_1:\tau\rightarrow \rho\quad\Gamma\vdash e_2:\tau \\ \hline \Gamma\vdash e_1e_2 : \rho\end{array}$$</span></p> <p><span class="math-container">$$\begin{array}{c}\Gamma\vdash e:\tau \\ \hline \Gamma\vdash e: \mathtt{foo}\end{array}$$</span></p> <p>Where the environment <span class="math-container">$\Gamma$</span> is a partial function from the set of variables into the set of types and <span class="math-container">$\Gamma(x:t)$</span> denotes an environment that assignts the type <span class="math-container">$t$</span> to the variable <span class="math-container">$x$</span> and works like <span class="math-container">$\Gamma$</span> for all other variables.</p> <p>Derive types for the following expressions:</p> <p><em>(omitted for brevity)</em></p> <p><strong>Example</strong>: Type derivation for <span class="math-container">$\lambda x.\lambda y.x$</span>:</p> <p><span class="math-container">$$\begin{array}{c}x:\alpha,\;y:\beta\vdash x:\alpha \\ \hline x:\alpha\vdash \lambda y.x:\beta\rightarrow\alpha \\ \hline \vdash\lambda x.\lambda y. x : \alpha \rightarrow (\beta\rightarrow\alpha) \end{array}$$</span></p> </blockquote> <p>It is this example that perplexes me. Why is it necessary to put <span class="math-container">$x:\alpha$</span> on the left-hand side of <span class="math-container">$\vdash$</span> in the second step of the derivation? My thinking is that <span class="math-container">$\lambda x.y : \beta\rightarrow \alpha$</span> results from both <span class="math-container">$x:\alpha$</span> <strong>and</strong> <span class="math-container">$y:\beta$</span> so there's no reason to put <span class="math-container">$x:\alpha$</span> on the lhs of <span class="math-container">$\vdash$</span> but not <span class="math-container">$y:\beta$</span>.</p> <p>But <span class="math-container">$\begin{array}{c}x:\alpha,\;y:\beta\vdash x:\alpha,\; y:\beta \\ \hline x:\alpha,\; y:\beta\vdash \lambda y.x:\beta\rightarrow\alpha \end{array}$</span> is a tautology that brings in nothing, so we should instead simplify this to <span class="math-container">$\begin{array}{c}x:\alpha,\;y:\beta \\ \hline \vdash \lambda y.x:\beta\rightarrow\alpha \end{array}$</span>. Note that this is precisely what the third step of derivation seems to be doing: <span class="math-container">$\begin{array}{c} x:\alpha\vdash \lambda y.x:\beta\rightarrow\alpha \\ \hline \vdash\lambda x.\lambda y. x : \alpha \rightarrow (\beta\rightarrow\alpha) \end{array}$</span> They simply put nothing on the left-hand side of the <span class="math-container">$\vdash$</span>.</p> <p>What am I missing here? Is this related to the form of the axiom that seems to be used here - <span class="math-container">$\begin{array} {c} \Gamma(x : \tau) \vdash e : \rho \\ \hline \Gamma \vdash \lambda x.e : \tau \rightarrow \rho\end{array}$</span> - where the environment used above the vertical line contains the assignment <span class="math-container">$x:\tau$</span> while the environment used below the vertical line is devoid of this assignment? Which is why in <span class="math-container">$x:\alpha\vdash \lambda y.x:\beta\rightarrow\alpha$</span> the assignment <span class="math-container">$x:\alpha$</span> must be present before the <span class="math-container">$\vdash$</span>, but the assignment <span class="math-container">$y:\beta$</span> must not? Is my reasoning correct? But if it is, then why does the third step seem to differ and is of the form <span class="math-container">$\vdash\lambda x.\lambda y. x : \alpha \rightarrow (\beta\rightarrow\alpha)$</span> and not <span class="math-container">$\lambda y.x : \beta\rightarrow\alpha \vdash\lambda x.\lambda y. x : \alpha \rightarrow (\beta\rightarrow\alpha)$</span>?</p> <p>Or am I splitting hairs here? But my thinking is that I'm not certain what degree of accuratness is required by this professor so I wouldn't like to loose points on something of this sort... Could you clear my confusion?</p> https://cs.stackexchange.com/q/110667 2 Substituting a term for a variable in a context CuriousKid7 https://cs.stackexchange.com/users/93428 2019-06-14T07:36:26Z 2019-06-14T07:36:26Z <p>At <a href="http://www1.maths.leeds.ac.uk/~pmtng/Slides/syntax.pdf" rel="nofollow noreferrer">this link</a> you can read Nicola Gambino's slides on one way to approach the formal syntax of Martin-Löf dependent type theory. (They are concise and very readable.)</p> <p>On slide 10, he gives a standard definition of a <em>context</em> as a list of the form <span class="math-container">$$x_1:A_1, \ldots, x_n:A_n$$</span> where the <span class="math-container">$x_i$</span> denote pairwise distinct <em>variables</em>. </p> <p>Now, on slide 17, he gives a standard example of a structural rule for the type theory, often called the substitution rule:</p> <p><span class="math-container">$$\frac{x : A, \Gamma \vdash J \quad a : A}{\Gamma[a / x] \vdash J[a / x]}$$</span> where <span class="math-container">$J$</span> denotes a consequent of a generic judgment. Note that <span class="math-container">$\Gamma$</span> is supposed to be a context in the premise.</p> <p><strong>But what exactly does <span class="math-container">$\Gamma[a / x]$</span> mean?</strong></p> <p>We need <span class="math-container">$\Gamma[a / x]$</span> to be a context for the conclusion of the rule to be a well-formed judgment, but just replacing the variable <span class="math-container">$x$</span> with the <em>term</em> <span class="math-container">$a$</span> may give <span class="math-container">$\Gamma[a / x]$</span> the wrong form since <span class="math-container">$a$</span> need not be a variable. Therefore, there seems to be an immediate issue here.</p> <p>Could someone clarify the definition of substituting a term for a variable in a context? </p> https://cs.stackexchange.com/q/110434 1 What's the difference between Acfg and ALLcfg Ken https://cs.stackexchange.com/users/106300 2019-06-09T22:03:28Z 2019-06-09T22:38:05Z <p>In computational theory, and talking about CFGs, Turing Machines, and so forth I haven't a satisfactory explanation or definition for what A<em>TM</em> means versus ALL<em>TM</em> or the same or similar uses with CFGs, etc. Does the single A stand for any, some, one, or all instances of the class whether it's a TM, a CFG, or anything else? Conversely, E<em>TM</em> and EQ<em>TM</em> are obvious as to what they mean.</p> https://cs.stackexchange.com/q/108717 1 What is this weird gate? Nobody In Particular https://cs.stackexchange.com/users/104653 2019-04-29T22:07:50Z 2019-04-30T01:33:14Z <p><a href="https://i.stack.imgur.com/W57eK.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/W57eK.png" alt="odd not gate"></a></p> <p>This came from a picture of something that I'm supposed to make, and I can't find it in the program I'm supposed to use (LogicWorks). It looks like it 'not's only one of its inputs, but that doesn't make sense because that input comes from a not gate (not pictured here); it would make more sense for this part to be no gate at all, just two connected wires.</p> <p>It would be helpful to say what this is called and/or what it does.</p> https://cs.stackexchange.com/q/107238 1 What is the equivalent of the integers symbol Z for n bit only integers? Paul Uszak https://cs.stackexchange.com/users/31167 2019-04-20T00:53:11Z 2019-04-20T02:20:08Z <p>We refer to the set of all integers as <span class="math-container">$\mathbb{Z}$</span>. Now suppose we have a set of integers that can be held within a computer variable of <span class="math-container">$n$</span> bits width. Clearly they can only be of <span class="math-container">$2^{n}$</span> range, signed or not. How would we symbolise that? Is there something that is done to the zed, or does it remain simply <span class="math-container">$\mathbb{Z}$</span>?</p> https://cs.stackexchange.com/q/107209 1 Can the notation for polynomial reduction, A ≤p B be reversed in computability theory? Daruis soli https://cs.stackexchange.com/users/103150 2019-04-19T10:36:01Z 2019-04-19T13:12:43Z <p>I don't know this is a proper question on this forum but I was reading about computability theory and I saw the reduction concept and its notation like this: <span class="math-container">$A \le_pB$</span>. I just wanted to know is this notation can be reversed? that is, can I write this down like <span class="math-container">$A\ge_p B$</span> And still have a meaning? I searched a lot but this notation always been like the former and I got confused.</p> https://cs.stackexchange.com/q/105880 5 Why do ¬, ∀ and ∃ have the same precedence? Phil https://cs.stackexchange.com/users/101901 2019-03-21T15:00:26Z 2019-03-22T07:35:00Z <p>I thought the order of precedence of operators and quantifiers was arbitrary, but I don't really understand why those three have the same "strength" in relation to other operators (e.g., ¬ will have precedence over ∧, but not over ∀). This leads to the rule being that ¬, ∀ and ∃ will bind to the closest predicate on their right (if I understood correctly). Why is this?</p> https://cs.stackexchange.com/q/51532 1 What is the Haskell-style type signature called (i.e., who is it named after)? Jake Romer https://cs.stackexchange.com/users/11274 2016-01-06T11:04:12Z 2019-03-06T23:26:40Z <p>A type signature in Haskell is written in the following format:</p> <pre><code>functionName :: arg1Type -&gt; arg2Type -&gt; returnType </code></pre> <p>There's a (hyphenated, after a person or persons) name for this style of type signature (which predates Haskell), but it's escaping me and I can't find it anywhere. </p> https://cs.stackexchange.com/q/104207 0 Did Menezes et al. switch the letters $\mu$ and $\lambda$ in Floyd's cycle detection note 3.8? R. Chopin https://cs.stackexchange.com/users/86544 2019-02-11T22:55:03Z 2019-02-11T23:34:31Z <p>The letters <span class="math-container">$\mu$</span> and <span class="math-container">$\lambda$</span> are usually used to represent, respectively, the length of the tail of the graph and length of the cycle in the graph. But Menezes on <a href="http://cacr.uwaterloo.ca/hac/about/chap3.pdf" rel="nofollow noreferrer">note 3.8</a>, page 91 (or PDF-page 6), seems to have swapped their roles.</p> <p><img src="https://i.stack.imgur.com/JHtGj.png" alt="Menezes swapping the usual roles of <span class="math-container">$\mu$</span> and <span class="math-container">$\lambda$</span> in Floyd&#39;s cycle detection algorithm"></p> <p>There's nothing wrong with the description, but isn't there a usual-role swap there?</p> https://cs.stackexchange.com/q/103838 2 How I can find all equivalence classes by Myhill-Nerode? Marie.L https://cs.stackexchange.com/users/99983 2019-02-04T17:15:01Z 2019-02-05T13:43:18Z <p>first of all I'm sorry for my bad English and second I'm sorry for my mistakes of understanding the following topic, I still going to school and learning this for interest.</p> <p>The topic is Myhill-Nerode and the equivalence classes of a regular or non regular language.</p> <p>I know that every element of a equivalence class by Myhill-Nerode fulfills this property:</p> <p><span class="math-container">$\equiv_{A} \triangleq\{(x, y) | \forall z \in \Sigma^{*} \cdot(x z \in A \leftrightarrow y z \in A)\}$</span></p> <p>If I understand this right, than a equivalence class consist of element (words) <span class="math-container">$x$</span> which we can expand with a word <span class="math-container">$y$</span> but for all words <span class="math-container">$x$</span> and <span class="math-container">$y$</span> of the same class must apply, adding a word <span class="math-container">$z$</span> to them both must be in or out of the language.</p> <p>Hope that is right until now.</p> <p>Now I will show you my problem:</p> <p>I have the language (its from a book): </p> <p><span class="math-container">$\mathrm{B} \triangleq\left\{73 \mathrm{a}^{n} 7 \mathrm{b}^{\mathrm{m}} | \mathrm{n}, \mathrm{m} \in \mathbb{N} \wedge \mathrm{n}=\mathrm{m}+2\right\}$</span> with <span class="math-container">$\Sigma_{\mathrm{M}} \triangleq\{\mathrm{a}, \mathrm{b}, 3,7\}$</span></p> <p>And a complete solution:</p> <p><span class="math-container">$1: [\lambda]\equiv_{B}=\{\lambda\}$</span></p> <p><span class="math-container">$2: \equiv_{B}=\{7\}$</span></p> <p><span class="math-container">$3: \left[73 a^{k}\right] \equiv_{B}=\left\{73 a^{k}\right\}$</span> für <span class="math-container">$k \in \mathbb{N}$</span></p> <p><span class="math-container">$4: \left[73 a^{l+2} 7\right] \equiv_{B} =\left\{73 \mathrm{a}^{\imath+2+n} 7 \mathrm{b}^{\mathrm{n}} | \mathrm{n} \in \mathbb{N}\right\} \quad$</span> für <span class="math-container">$l \in \mathbb{N}$</span></p> <p><span class="math-container">$5: _{\equiv \mathrm{B}}=\Sigma^{*} \backslash\left([\lambda]_{\equiv \mathrm{B}} \cup_{\equiv \mathrm{B}}\right. \cup\left(\bigcup_{k \in \mathbb{N}}\left[73 a^{k}\right] \equiv_{B}\right) \cup \left(\bigcup_{\mathfrak{l} \in \mathbb{N}}\left[73 \mathrm{a}^{\ l+ 2} 7\right] \equiv_{\mathrm{B}}\right) )$</span></p> <p>So in <span class="math-container">$1$</span> they build a class of the empty word <span class="math-container">$\lambda$</span> and <span class="math-container">$z = B$</span> has to be the language by her self to be in the language?</p> <p>In <span class="math-container">$2$</span> they build they build the class of <span class="math-container">$7$</span> and z has to be something like this <span class="math-container">$z = \left\{3 \mathrm{a}^{n} 7 \mathrm{b}^{\mathrm{m}} | \mathrm{n}, \mathrm{m} \in \mathbb{N} \wedge \mathrm{n}=\mathrm{m}+2\right\}$</span> to be in the language.</p> <p>In <span class="math-container">$3$</span> they build a class or better infinitely many classes. But here is my problem. I cannot find a <span class="math-container">$z$</span> which is working for all classes.</p> <p>For example we have the words <span class="math-container">$x_i$</span> and <span class="math-container">$z_i$</span></p> <p><span class="math-container">$x_1 = 73 \to z_1= {a}^{n+2}7b^n$</span> with <span class="math-container">$n\in N$</span></p> <p><span class="math-container">$x_2 = 73a \to z_2= {a}^{n+1}7b^n$</span> with <span class="math-container">$n\in N$</span></p> <p><span class="math-container">$x_3 = 73a^2 \to z_3= {a}^{n}7b^n$</span> with <span class="math-container">$n\in N$</span></p> <p><span class="math-container">$x_4 = 73a^3 \to z_4= {a}^{n}7b^n+1$</span> with <span class="math-container">$n\in N$</span></p> <p>and so on.</p> <p>But why is this ok? I Mean they are 2 words in this class for example <span class="math-container">$x_1$</span> and <span class="math-container">$x_2$</span> who <span class="math-container">$x_2$</span> would not be in <span class="math-container">$B$</span> with <span class="math-container">$z_1$</span>.</p> <p>I hope you can tell me on a simple and understanding way how those classes by Myhill work and how i can find them without making big mistakes.</p> https://cs.stackexchange.com/q/103584 1 Constructing a new graph. G'. What does it mean v ∈ S_{i+1}? Dmomo https://cs.stackexchange.com/users/81234 2019-01-30T00:42:50Z 2019-01-31T07:29:24Z <blockquote> <p>John lives in a city whose streets has the same length. His apartment is located at a specified node H. John need to do his errands where he visits each of k different shop in order. However, each store have more than one location in his city. More particularly, for each 1 ≤ i ≤ k there is a set <span class="math-container">$S_{i}$</span> of vertices at which a branch of the <span class="math-container">$i^{th}$</span> shop is located (you can assume that the <span class="math-container">$S_{i}$</span> are disjoint). Construct a new graph G' as following:</p> <p>Create a new graph G' whose nodes are given by both a node of G, representing John’s current location, and a number 0 ≤ i ≤ k, giving the number of stops that John has successfully made. In particular, the vertices of G' are exactly given by (v, i) with v ∈ Node and i ∈ {0, 1,..., k}. Edges in G' are between (u, i) and (v, i) if (u, v) is an edge of G, or between (u, i) and (v, i + 1) if (u, v) is an edge of G and v ∈ <span class="math-container">$S_{i+1}$</span>.</p> </blockquote> <p><strong>What does it really mean by "between (u,i) and (v,i+1) if (u,v) is an edge of G and V v ∈ <span class="math-container">$S_{i+1}$</span>"?</strong></p> <p>Let's say we have simple graph G as below: <a href="https://i.stack.imgur.com/DGoVW.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/DGoVW.png" alt="enter image description here"></a></p> <p>Here is my attempt of constructing the new graph G'. </p> <p>How many new nodes do we need to make, 3 or 4 copies? I only make 3 so far since there are only 3 errands. Please let me know if my G' is correct. Thank you.<a href="https://i.stack.imgur.com/2CpSb.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/2CpSb.png" alt="enter image description here"></a></p> https://cs.stackexchange.com/q/103012 0 Terminology for worst-case N-complexity on $O(1)$ insert after amortisation cnst https://cs.stackexchange.com/users/11551 2019-01-17T23:51:59Z 2019-01-19T07:59:07Z <p>Normally, when discussing amortisation and worst-case complexity, amortisation negates the worst-case scenarios, and the BigO describes the average for the operation (the way it's used in interviews nowadays).</p> <p>For example, when an insertion of an element requires reallocation and copying of the array, increasing the size in two, it is still said that insertion is <span class="math-container">$O(1)$</span>, not <span class="math-container">$O(n)$</span>; the worst-case performance is rarely mentioned. Compare this with sorting algorithms, where the worst case could be <span class="math-container">$O(n^2)$</span>, whereas the average case could be <span class="math-container">$O(n\log{}n)$</span>, and this is always specified and discussed.</p> <ul> <li><p>What is the terminology to express this N-level complexity for the <span class="math-container">$O(1)$</span> insertion that requires reallocation with copy of <span class="math-container">$O(N)$</span> elements?</p></li> <li><p>What is the alternative terminology for expressing an optimisation approach, with delayed copy, where the worst-case complexity remains constant-time, provided the operation to allocate new chunk of memory itself is constant. In other words, where you keep both arrays, and do a lazy-copy approach.</p></li> </ul> <p>Specifically, both of the above could be described as amortisation. But I'm having trouble finding out the absolutely correct terminology for this nuanced problem, as how do you distinguish between these two different scenarios in describing amortisation?!</p> https://cs.stackexchange.com/q/101324 47 O(·) is not a function, so how can a function be equal to it? doubleE https://cs.stackexchange.com/users/63468 2018-12-10T08:47:22Z 2018-12-20T23:17:10Z <p>I totally understand what big <span class="math-container">$O$</span> notation means. My issue is when we say <span class="math-container">$T(n)=O(f(n))$</span> , where <span class="math-container">$T(n)$</span> is running time of an algorithm on input of size <span class="math-container">$n$</span>.</p> <p>I understand semantics of it. But <span class="math-container">$T(n)$</span> and <span class="math-container">$O(f(n))$</span> are two different things.</p> <p><span class="math-container">$T(n)$</span> is an exact number, But <span class="math-container">$O(f(n))$</span> is not a function that spits out a number, so technically we can't say <span class="math-container">$T(n)$</span> <strong><em>equals</em></strong> <span class="math-container">$O(f(n))$</span>, if one asks you what's the <strong><em>value</em></strong> of <span class="math-container">$O(f(n))$</span>, what would be your answer? There is no answer.</p> https://cs.stackexchange.com/q/101311 1 What is the meaning of max() in intro. to algorithms? Papaya Automata https://cs.stackexchange.com/users/92841 2018-12-10T00:41:10Z 2018-12-10T01:24:12Z <p>I'm reading chapter 3(growth functions) of CLRS and in giving an example of proving theta for a standard quadratic function the book gives the following value for <span class="math-container">$n_0 = 2 \cdot max(|b|/a, \sqrt{|c|/a})$</span> .</p> <p>I'm confused regarding what <strong>"max"</strong> means in this context. The quadratic function is <span class="math-container">$an^2 + bn + c$</span> and the constants give are <span class="math-container">$c_1 = a/4, c_2 =7a/4$</span>.</p> <p>I'm thinking it might mean which ever of the parameters yields a larger value? </p> https://cs.stackexchange.com/q/101270 0 Clarify the steps: what happened in this mathematical modelling of TSP? Ryan Cameron https://cs.stackexchange.com/users/96149 2018-12-09T09:51:07Z 2018-12-09T11:51:57Z <p>Source: <a href="http://examples.gurobi.com/traveling-salesman-problem" rel="nofollow noreferrer">http://examples.gurobi.com/traveling-salesman-problem</a></p> <p>I don't get this part: (look at the source)</p> <blockquote> <p><span class="math-container">$$\sum_{i,j\in\{1,2,3\},i\neq j} x_{ij}=3&gt;2=|\{1,2,3\}|-1$$</span></p> </blockquote> <p>I get that <span class="math-container">$x_{ij}$</span> is equal to 3, but why the "> 2" ?</p> <p>And what is the deal with subtracting 1 from a set? How do you even do that?</p> <p>How come <span class="math-container">$|\{1,2,3\}|-1 = 3 &gt; 2$</span> ?!?</p> <p>Okay so: <span class="math-container">$$|\{1,2,3\}|-1 = 2$$</span></p> <p>So how is he allowed to write: <span class="math-container">$$|\{1,2,3\}|-1 = 3 &gt; 2$$</span></p> <p>?</p> <p>That is basically the same as writing: (which is incorrect right?) <span class="math-container">$$2 = 3 &gt; 2$$</span></p> <p>I don't get this part at all, please elaborate on what happened in as simple language as possible. My level is high school final math level.</p> https://cs.stackexchange.com/q/101153 1 How the language $\{a^nb^mc^nd^m | n \geq1, \ m\geq1\}$ is used to check whether formal and actual parameters are equal? Mr. Sigma. https://cs.stackexchange.com/users/58433 2018-12-07T05:47:06Z 2018-12-09T03:54:20Z <p>How does the language <span class="math-container">$L=\{a^nb^mc^nd^m \mid n \geq1, m\geq1\}$</span> abstract the problem of checking that the number of formal parameters in the declaration of a procedure agrees with the number of actual parameters in a use of the procedure? </p> <p>I simply didn't get what each of the variables <span class="math-container">$a,b,c,d,n$</span> and <span class="math-container">$m$</span> will represent? Seems <span class="math-container">$1^{st}$</span> pair <span class="math-container">$(n,m)$</span> is for formal parameters and later for actual. But I didn't get why there are <span class="math-container">$a$</span> and <span class="math-container">$b$</span>? Couldn't only single variable be ample? </p> https://cs.stackexchange.com/q/100679 0 How to denote a graph class which allows only $k$ instances of a certain induced subgraph? padawan https://cs.stackexchange.com/users/17185 2018-11-28T22:34:39Z 2018-11-28T22:58:24Z <p>Suppose that a graph class <span class="math-container">$\mathcal{C}$</span> is defined as follows:</p> <blockquote> <p>A graph <span class="math-container">$G$</span> belongs to <span class="math-container">$\mathcal{C}$</span> if, and only if <span class="math-container">$G$</span> is chordal, but has at most <span class="math-container">$k$</span> <span class="math-container">$5$</span>-cycles.</p> </blockquote> <p>I am aware that the definition of <span class="math-container">$\mathcal{C}$</span> is contradictory. However, I am looking for a notation like</p> <p><span class="math-container">$G \in C_4\text{-free} + k*(C_5)$</span></p> <p>Is there such notation in the literature?</p> https://cs.stackexchange.com/q/100357 4 In ISGCI, unit interval graphs are denoted as ($C_{n+4}$,$S_3$,claw,net)-free. Is this an accurate notation? padawan https://cs.stackexchange.com/users/17185 2018-11-21T02:26:58Z 2018-11-21T10:55:02Z <p>When I search <a href="http://graphclasses.org/classes/gc_299.html" rel="nofollow noreferrer">unit interval graphs</a> in ISGCI, it says that the unit interval graphs (<strong>UIG</strong>) are equivalent to (<span class="math-container">$C_{n+4}$</span>,<span class="math-container">$S_3$</span>,claw,net)-free graphs.</p> <p>I am confused about the definition of an <span class="math-container">$S_3$</span> graph. I am aware that in some resources, <span class="math-container">$S_n$</span> means <span class="math-container">$K_{1,n}$</span>, and in others <span class="math-container">$S_{n-1}$</span> means <span class="math-container">$K_{1,n}$</span>.</p> <p>However, in both cases, (<span class="math-container">$C_{n+4}$</span>,<span class="math-container">$S_3$</span>,claw,net)-free <span class="math-container">$\equiv$</span> <strong>UIG</strong> seems like a wrong notation.</p> <p>If <span class="math-container">$S_3$</span> is <span class="math-container">$K_{1,3}$</span>, then <span class="math-container">$S_3$</span> is also a <a href="http://mathworld.wolfram.com/ClawGraph.html" rel="nofollow noreferrer">claw graph</a>. Thus, (<span class="math-container">$S_3$</span>,claw)-free is a redundant notation. On the other hand, if <span class="math-container">$S_3$</span> is <span class="math-container">$K_{1,2}$</span>, then it is wrong because a path of length 3 is realizable as a unit interval graph.</p> <p>If this notation is true, then can I also write <strong>UIG</strong> <span class="math-container">$\equiv$</span> (<span class="math-container">$C_{n+4}$</span>,<span class="math-container">$S_3$</span>,<span class="math-container">$K_{1,2}$</span>,<span class="math-container">$P_2$</span>,claw,net)-free?<br> If not, then is it correct to write that <strong>UIG</strong> <span class="math-container">$\equiv$</span> (<span class="math-container">$C_{n+4}$</span>,claw,net)-free?</p> https://cs.stackexchange.com/q/87051 1 Does big-Oh notation in optimization follow the same convention as in CS? Olórin https://cs.stackexchange.com/users/23030 2018-01-20T22:08:53Z 2018-11-07T17:26:12Z <p>I first learned big-Oh (little-Oh, big-Theta.....) complexity for growth of functions using CLRS in a computer science class. </p> <p>Now I am doing a project on optimization. In our optimization class, we were introduced to the notion of rate of convergence which are characterized by the ratio:</p> <p>$\lim\limits_{k \to \infty} \dfrac{|x_{k+1} - L|}{|x_k-L|}$</p> <p>where $L$ is the limit of the sequence $(x_k)$. And from there we define linear, superlinear and sublinear convergence raes.</p> <p>However, when I looked up on some reference online, the above notions of rate of convergence is almost never used. Instead, all the convergence rates are characterized in <a href="https://www.cs.cmu.edu/~ggordon/10725-F12/slides/05-gd-revisited.pdf" rel="nofollow noreferrer">terms of big-Oh</a>. Quoting from the slides:</p> <blockquote> <p><strong><em>Theorem</em></strong>: Gradient decent with fixed step size $t\le\frac{1}{L}$ satisfies $f(x^{(k)})-f(x^*)\le\frac{\|x^{(0)}-x^*\|^2}{2tk}$.</p> <p>I.e. gradient decent has convergence rate $O\left(\frac{1}{k}\right)$.</p> <p>I.e. to get $f(x^{(k)})-f(x^*)\le\epsilon$, we need $O\left(\frac{1}{k}\right)$ iterations.</p> </blockquote> <p>Unfortunately, these authors never define what their notations mean. I am in need of citing the definitions of big-Oh for my class project.</p> <p>Is there any disparity between the rate of convergence in terms of big-Oh (and other asymptotic) used in optimization versus that used in CS (as can be found in a standard textbook such as CLRS)? </p> <p>Is there an optimization textbook that addresses big-Oh notation?</p>