12

The classic consequence of $a^nb^n$ being context-free rather than regular is on opening and closing brackets. $a^nb^n$ represents the simplest possible case of this: no interleaving of opens and closes and no intervening characters. Regular expressions can't even deal with this most basic case.


8

There are two parts to this: (a) selecting a graph (experimental design) to determine which pairs of essays the students will evaluate in the peer grading process, and (b) ranking all the essays, based upon the student's peer grades, to determine which the teacher should rank. I will suggest some methods for each. Choosing a graph Problem statement. The ...


7

Average degree and mean degree are the same. In the $G(n,m)$ model, the average degree is $2m/n$. In the $G(n,p)$ model, the expected average degree is $np$. The actual average degree has normal distribution with mean $np$ and standard deviation $\sqrt{2(1-\tfrac{1}{n})p(1-p)}$, so it is pretty close to $np$ with high probability. When $p=c/n$ for fixed $c$,...


5

"new flow arrivals" means "arrivals of new flows". A flow is a TCP connection (roughly); each individual TCP connection is a separate "flow". So, this is talking about new TCP connections, and the rate/time at which the server receives new TCP connections. Contrarily to the statement you quoted, web requests won't necessarily be Poisson. There are many ...


4

If you want to model an alldiff() constraint in SAT, there are several options. Here are two different options you can try: One way is to expand $\text{alldiff}(x_1,\dots,x_n)$ into $n(n-1)/2$ inequality constraints: $(x_1 \ne x_2) \land (x_1 \ne x_3) \land \cdots$. Now you can express each inequality constraint $x_i \ne x_j$ on $b$-bit values in turn as ...


4

This answer considers two cases: the overlapping relation between two disks, which is a very simple problem. the ovelapping or covering of a disk by a set of other disks, which is somewhat harder in general. Case of two disks It is indeed a good idea to use center and radius to represent your circles. However I think you are not thinking of circles, which ...


4

I'm not sure how to approach your particular problem, but here is an attempt. Consider the recipe you are using as a collection of steps, some of which depend on others; for a salad you might have "make dressing", "shred lettuce", "slice cucumber" etc. The dependencies are given through resources, which here are ingredients, possibly in some processed state,...


4

You can't. You can't express this without using quadratic constraints. Your requirement is about Euclidean distance. The Euclidean distance is inherently quadratic. To be more precise about that: the problem cannot be expressed using solely using linear constraints, as the Euclidean distance is non-linear. That said, you can solve your one-sentence ...


4

It seems you're looking for a symmetric set similarity measure. (Symmetric since, as you point out, $A$ should match $B$ as much as $B$ matches $A$. Set similarity since each person's preference is defined by a set of objects.) A number of these are used in the CS literature. Probably the most common is Jaccard similarity, defined by $|A\cap B|/|A\cup B|$...


3

The river crossing problem using integer programming is solved by Börndorfer et al. in [1]. [1] Borndörfer, Ralf, Martin Grötschel, and Andreas Löbel. Alcuin's transportation problems and integer programming. ZIB, 1995.


3

How do you physically characterize the load of a processor, is it equivalent to CPU utilization? The program is modelling load like this. Whether you feel it's a good way to model load, and whether you can think of any real version of load that works like this is a separate issue. You are running a storage facility for water. The key "facts" about water ...


3

Kociemba wrote very nice algorithm, which is the fastest working algorithm returning optimal or almost optimal solution very efficiently. If you want to derive your own system, try in steps: 0) invent notation for the cube, do not try to optimize it. 1) try BFS or something like A* (this one will be harder, with heuristics). 2) try some kind of memoization, ...


3

You are looking for a four-dimensional convex polytope that contains all of the points $(x_1,x_2,x_3,x_4)$ that satisfy your condition, and but not any point $(x_1,x_2,x_3,x_4)$ that doesn't satisfy your condition. (That's because any system of linear inequalities forms a convex polytope.) It's not quite clear to me from your question about what your ...


3

Short answer: indirection. For instance, each object could have a field that contains an index into the id array. Or, you could use pointers. Standard union-find data structures often use pointers instead of integers/indices/arrays. Thus, each object has a pointer to another object in the same equivalence class. See, e.g., https://en.wikipedia.org/wiki/...


3

If you want to say something about an RDF triple (i.e., an rdf:Statement), you can use reification: @prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> . @prefix voc: <https://example.com/vocabulary#> . @prefix : <https://example.com/instances#> . :Triple42 rdf:type rdf:Statement . :Triple42 rdf:subject :...


3

Object-oriented programming languages are designed to support programming. Whether they "properly" model the real world is beside the point and not the primary goal. So, when you ask "why haven't [these requirements] been included?", it's likely because those weren't considered relevant or necessary to the goal of supporting programming....


2

I do not know if there is a variant of Petri nets that captures your intent exactly -- there probably is, there are so many -- but the feature can be expressed with regular Petri nets. Just add a transition that creates tokens in multiple places, one per original transitions. Then, all three follow-up transitions can fire after the preceding one is done. ...


2

Our matrix is modelled as a graph $G = (V,E)$ with directed edges $E$ between cells $V$. We denote $V_{kl}$ as the set of nodes $j$ that respect $d_{jl} \leq k$. The edges $E$ exist between all nodes $j \in V_{kl}$ and node $l$, for any $l \in V$. Activated edges represent movements (such as players moving with the ball to an adjacent cell or passing the ...


2

Integer linear programming Let me suggest another way of formulating this with ILP that might be worth trying. Define combination to mean a list of all of the balls in a single box. For instance, the combination might be (7,15) meaning that the box contains ball 7 and ball 15. Of course, we can enumerate all legal values for the combination, i.e., for ...


2

One approach to distinguish between (1) vs (2)-or-(3) is to use a statistical hypothesis test. A statistical hypothesis test can tell you whether the amount of change is too large to be explained by random chance. One reasonable approach might be to use linear regression: try to model intensity as a linear function of time $y = at+b$, and then use a ...


2

have not heard of use of abstract languages to model the rubiks cube. however, there is a huge amount of group theory intrinsically associated with it, and there are natural ways to represent group theory using languages (and automata). as for using the theory to solve the cube, there are many standard algorithms and it would be difficult for newcomers to ...


2

It sounds like you want to compute the intersection of two languages. Depending upon what kind of languages you are looking at and how they're represented, you might look into the "product construction" and closure properties for your class of languages. For instance, for regular languages, there is a standard method for computing the intersection of two ...


2

If you only have to encode this (and don't have any other constraints on $x_i$), you can then use the following constraints: $x_1 < x_2 < \dots < x_{n-1} < x_n \leq k$ which is $n$ constraints. Let $m=\lceil \log_2 k\rceil$ and $x_i = b_{im}, b_{i(m-1)}, \dots, b_{i1}$, where $m$ is the high bit and $1$ is the low bit. Define $d_{ij} = b_{ij}\...


2

This can been seen as a variation of the job shop problem where you want to find the policy that yields the minimum makespan (time taken for all machines to process all jobs); as well as a variation of the assignment problem (find the optimal pairing of workers to jobs that minimizes cost). The variation in both cases is an added dependency between jobs (Job ...


2

Any optimal solution to the problem must satisfy $$ d_v = \min_{u\colon (u,v) \in E} (d_u + \ell_{uv}), $$ as well as $d_s = 0$, of course. Assuming the graph is connected, you can prove by induction on the length (number of edges) of a shortest path from $s$ to $v$ that $d_v$ is at most the distance from $s$ to $v$, which we denote by $d^*_v$. In particular,...


2

Generally, the idea of a (normal) petri-net is to efficiently represent a system to model an arbitrary amount of 'agents' that change their state depending on certain transitions. (This would quite quickly get out of hand in a state machine) So, the basic strategy is to first determine what your 'agents' are and model them as your tokens. The state of an ...


2

If you find it challenging to apply Petri Nets in modeling an application then it may help to consider the following mapping between the types of words found in a text description of an application with the types of Petri Net elements found in a Petri Net diagram of the application: Nouns are candidates for places. Verbs are nominees for transitions (and/or ...


2

Let $x \in [-10,10] \cap \mathbb Z$ and $y \in \{0,1\}$. Suppose that $$y = \begin{cases} 1 & \text{if } x \geq 3\\ 0 & \text{if } x \leq 2\end{cases}$$ To ensure that $y \neq 0$ when $x \geq 3$, use $$y \geq \frac{x-2}{8}$$ To ensure that $y \neq 1$ when $x \leq 2$, use $$y \leq \frac{x+10}{13}$$ Pictorially, The trivial inequality ...


2

If you want to weight then cosine_similarity is an option. What this does is weight items that are not common in the population higher. Not sure how but I would base uniqueness on the two populations separately. Some very common among women but uncommon among men should still have high weighting. You could have the people rank their list and use that as ...


2

I will use a = 1, b = 2, etc... If a is set then c must be false and EITHER b or d must be true: 10a + c <= 10 10a + b + d <= 11 10a - b - d <= 9 Finally, if a is not set then the rest must be true: 10 - 10a - b - c - d <= 7


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