Simon S
  • Member for 9 years, 1 month
  • Last seen more than a month ago
  • Leipzig, Germany
Decidable languages and unrestricted grammars?
Accepted answer
7 votes

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 ...

View answer
Characteristic path length
Accepted answer
7 votes

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 ...

View answer
Does the following transformation preserve context-freeness?
5 votes

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
Minimum spanning tree with two minimum edge weights
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 ...

View answer
choice of data structure for domino tilings
3 votes

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 ...

View answer
Turing machine and coming up with an idea
3 votes

Try using visual designers like this or turingkara-en, which also contains exercises. Keep in mind that the TM is meant to be a theoretical, minimalistic model to simplify proofs. Programming on the ...

View answer
Is there an efficient method to store large DAGs?
2 votes

Try constructing a reduced ordered binary decision diagram (ROBDD) as described here. The reducing algorithm removes redundant nodes, and reuses equal subtrees in the decision tree, such that every ...

View answer