Simon S
• Member for 9 years, 1 month
• Last seen more than a month ago
• Leipzig, Germany

A language is decidable, iff it is semi-decidable and its complement is semi-decidable. Moreover, a language is recursive-enumerable iff it is semi-decidable and thus you can find an unrestricted ...

To get the CPL by this definition you first take the average distance from a certain vertex to any other vertex: $$d_v = {{\sum_{v \ne w} d(v,w)} \over {|V(G)| - 1}}$$ After doing so for every vertex ...

Counter-example: $L_1 = \{a^n b^n c^m \mid m,n \ge 1 \}$ $L_2 = \{a^m b^n c^n \mid m,n \ge 1 \}$ $L = (L_1 \cdot L_2^*) \cup \epsilon$ is context-free. Any nonempty word $x \in L^\#$ has a prefix $... View answer 5 votes Yes$G\$ has a unique MST (assuming it is not a multigraph). Take a look at Kruskal's algorithm: the edges are ordered ascending by weight and then added to the MST unless there is a cycle. After ...

There is an alternative, more compact kind of array representation which might be better if you are working with diamonds as defined in the paper you linked (for axis aligned rectangles you need to ...