StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
2946258
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
0
CommunityOwnedDate
CreationDate
2010-05-31T22:28:55.567
FavoriteCount
0
LastActivityDate
2010-05-31T23:18:18.367
LastEditDate
2010-05-31T23:18:18.367
LastEditorUserId
0
OwnerUserId
0
ParentId
2945418
PostTypeId
2
Score
1
ViewCount
0
LastEditorDisplayName
Aryabhatta
text
Body
This seem to be a very hard problem! I believe that even the decision problem to determine if a sequence of transforms exists (to convert source to target) is an <a href="http://en.wikipedia.org/wiki/Undecidable_problem" rel="nofollow noreferrer">Undecidable Problem</a>. Look at the <a href="http://en.wikipedia.org/wiki/Tag_system" rel="nofollow noreferrer">Tag System</a> page on the page of <a href="http://en.wikipedia.org/wiki/List_of_undecidable_problems" rel="nofollow noreferrer">List of Undecidable Problems</a>. In fact, it looks like the decision verion of your problem is at least as hard as the <a href="http://en.wikipedia.org/wiki/Collatz_conjecture" rel="nofollow noreferrer">Collatz Conjecture</a>, which states that the sequence <pre><code>n -> n/2 if n is even n -> 3n+1 if n is odd </code></pre> always ends in 1. This conjecture can be stated as: given the set of transforms <pre><code>a -> bc b -> a c -> aaa </code></pre> Can the word <pre><code>aaa...aaa (a repeated n times) </code></pre> eventually be transformed to the word <pre><code>a </code></pre> (The single letter a). Since the transformations only take one character at a time, the order does not matter: a word can be viewed as a multiset and is applicable to your problem. This set of transforms for the Collatz Conjecture was gotten from here: <a href="http://logica.ugent.be/liesbeth/TagColOK.pdf" rel="nofollow noreferrer">http://logica.ugent.be/liesbeth/TagColOK.pdf</a> (see page 7). Basically we cannot even be sure if any algorithm for this particular problem will ever terminate on all inputs. I guess you just need to explore all paths (using BFS/A* whatever) and hope you get lucky. Of course, if your rules of transformation always reduced the number of symbols, then an exhaustive search (even DFS) would surely halt. So, as you said, do a BFS/heuristic. But, now after this information, I guess you can do it confidently. :-)
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POReducing a set of non-unique elements via transformations
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. This table or related slice is empty.
UserOwnerUserId
1. This table or related slice is empty.
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. POReducing a set of non-unique elements via transformations
 singulars
 PostTypePostTypeId
 PTQuestion
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTAcceptedByOriginator
CommentsPostId
1. This table or related slice is empty.

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.