I have been approached to submit an extended version of a research paper in a journal. The original paper is already published in a conference proceedings by publisher A.
What "degree of extension" do I have to provide so that publisher B will (legally?) be able to publish my work?
Also, does "extended version" in this case mean additional results, or purely textual extension?
In most subareas of Computer Science having the paper with "at least 30% of new material" would be acceptable. This is particularly true of conference->journal paper transition, for instance when a conference version of the paper is extended with new results, more thorough description of the research contribution (and/or methods, materials, related work) and then submitted to a journal. Sometimes this also happens when a conference organizes a special issue of the best papers in a journal.
Nobody will measure how many words/letters you added, but you should be able to convince the reviewers/editors that the paper is extended. Pointing out the differences between the previous publication and the extended paper in the introduction would normally help to reviewers to assess if the extension is enough. Basically, what you want to avoid is Salami Slicing or Least Publishable Unit (see comment by BlackPudding at Is it unethical to submit for review multiple articles which overlap in some respect?)
I don't think there's a single "default" answer here. However, I would suggest that if you are planning to publish in B's journal, that you do both kinds of extension: provide both additional explanations that were in the original material, plus present different results (if possible) than what was in conference proceeding A. You should also avoid direct repetition of material, where possible.
However, before agreeing to this, I would also consider asking the journal editor to provide you some examples of what he or she considers "extended versions" of other proceedings, and review them to see what you think of the extensions. If you're not comfortable with the changes (in that they're not expansive enough to be a "new" paper), then you're free to tell the journal you're not interested.
As pointed out by aeismail, every journal have different policy. Usually, the journals/conferences accepting extended papers mention such things in there Call for Paper as well.
For example, this is a quote from CFP of Special Issue on Emerging Systems and Applications for Wireless Health Computing
All authors who presented papers at Wireless Health 2013 are invited to submit extended versions of their papers to IEEE TETC for inclusion in this special issue. Given that the Wireless Health 2013 proceedings will be published, it is required that submissions to the special issue have at least 30% new content.
Though, it is not very clear what exactly 30% new content means here, but it does indicate that your extended paper should have at least some new significant observation from may be at least the same results of your original paper.
