Article

A Formal Investigation of Diff3

Authors:

FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science: 27th International Conference, New Delhi, India, December 12-14, 2007. Proceedings

Pages 485 - 496

https://doi.org/10.1007/978-3-540-77050-3_40

Published: 15 March 2023 Publication History

Abstract

The diff3 algorithm is widely considered the gold standard for merging uncoordinated changes to list-structured data such as text files. Surprisingly, its fundamental properties have never been studied in depth.

We offer a simple, abstract presentation of the diff3 algorithm and investigate its behavior. Despite abundant anecdotal evidence that people find diff3’s behavior intuitive and predictable in practice, characterizing its good properties turns out to be rather delicate: a number of seemingly natural intuitions are incorrect in general. Our main result is a careful analysis of the intuition that edits to “well-separated” regions of the same document are guaranteed never to conflict.

References

[1]

Smith, R.: GNU diff3, Version 2.8.1, April 2002; distributed with GNU diffutils package (1988)

Google Scholar

[2]

Lindholm T. A three-way merge for xml documents DocEng 2004: Proceedings of the 2004 ACM symposium on Document engineering 2004 New York ACM Press 1-10

Crossref

Google Scholar

[3]

Chawathe S.S., Rajamaran A., Garcia-Molina H., and Widom J. Change detection in hierarchically structured information ACM SIGMOD Record 1996 25 2 493-504

Crossref

Google Scholar

[4]

Lanham, M., Kang, A., Hammer, J., Helal, A., Wilson, J.: Format-independent change detection and propagation in support of mobile computing. In: Brazilian Symposium on Databases (SBBD), Gramado, Brazil, pp. 27–41 (October 2002)

Google Scholar

[5]

MacKenzie, D., Eggert, P., Stallman, R.: Comparing and Merging Files with GNU diff and patch. Network Theory Ltd. Printed version of GNU manual (2003)

Google Scholar

[6]

Miller W. and Myers E.W. A file comparison program Softw., Pract. Exper. 1985 15 11 1025-1040

Crossref

Google Scholar

[7]

Myers E.W. An o(nd) difference algorithm and its variations Algorithmica 1986 1 2 251-266

Crossref

Google Scholar

[8]

Ukkonen E. Algorithms for approximate string matching Information and Control 1985 64 1-3 100-118

Crossref

Google Scholar

[9]

Foster, J.N., Greenwald, M.B., Kirkegaard, C., Pierce, B.C., Schmitt, A.: Exploiting schemas in data synchronization. Journal of Computer and System Sciences (2007) To appear. Extended abstract in Database Programming Languages (DBPL) (2005)

Google Scholar

[10]

Mens T. A state-of-the-art survey on software merging IEEE Trans. Software Eng. 2002 28 5 449-462

Crossref

Google Scholar

[11]

Stallman, R., et al.: Comparing and merging files, Manual for GNU diffutils (2002), available at www.gnu.org

Google Scholar

Index Terms

A Formal Investigation of Diff3
1. Applied computing

Index terms have been assigned to the content through auto-classification.

Recommendations

A formal investigation of Diff3
FSTTCS'07: Proceedings of the 27th international conference on Foundations of software technology and theoretical computer science

The diff3 algorithm is widely considered the gold standard formerging uncoordinated changes to list-structured data such as text files. Surprisingly, its fundamental properties have never been studied in depth.

We offer a simple, abstract presentation ...
An axiomatic account of formal argumentation
AAAI'05: Proceedings of the 20th national conference on Artificial intelligence - Volume 2

Argumentation theory has become an important topic in the field of AI. The basic idea is to construct arguments in favor and against a statement, to select the "acceptable" ones and, finally, to determine whether the statement can be accepted or not. ...
Formal Definitions of Reason Fallacies to Aid Defect Exploration in Argument Gaming
ICLA 2009: Proceedings of the 3rd Indian Conference on Logic and Its Applications - Volume 5378

Reason fallacies are fallacious reasons presented in arguments during argumentative discussions. The fallacious reasons do not support the claim of argument and therefore, the argument gets defeated. Defect exploration is the process of analysing ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science: 27th International Conference, New Delhi, India, December 12-14, 2007. Proceedings

Dec 2007

556 pages

ISBN:978-3-540-77049-7

DOI:10.1007/978-3-540-77050-3

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 15 March 2023

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Index Terms

Recommendations