A Polynomial-Time Algorithm for Merging Structured Documents

Nobutaka SUZUKI

doi:10.1093/ietisy/e88-d.10.2341

A Polynomial-Time Algorithm for Merging Structured Documents

Nobutaka SUZUKI

Full Text Views

0

Share
Cite this

Summary :

Document merging is essential to synchronizing several versions of a document concurrently edited by two or more users. A few methods for merging structured documents have been proposed so far, and yet the methods may not always merge given documents appropriately. As an aid for finding an appropriate merging, using another approach we propose a polynomial-time algorithm for merging structured documents. In the approach, we merge given two documents (treated as ordered trees) by optimally transforming the documents into isomorphic ones, using operations such as add (add a new node), del (delete an existing node), and upd (make two nodes have the same label).

Publication: IEICE TRANSACTIONS on Information Vol.E88-D No.10 pp.2341-2353

Publication Date: 2005/10/01

Publicized

Online ISSN

DOI: 10.1093/ietisy/e88-d.10.2341

Type of Manuscript: PAPER

Category: Contents Technology and Web Information Systems

Cite this

Copy

Nobutaka SUZUKI, "A Polynomial-Time Algorithm for Merging Structured Documents" in IEICE TRANSACTIONS on Information, vol. E88-D, no. 10, pp. 2341-2353, October 2005, doi: 10.1093/ietisy/e88-d.10.2341.
Abstract: Document merging is essential to synchronizing several versions of a document concurrently edited by two or more users. A few methods for merging structured documents have been proposed so far, and yet the methods may not always merge given documents appropriately. As an aid for finding an appropriate merging, using another approach we propose a polynomial-time algorithm for merging structured documents. In the approach, we merge given two documents (treated as ordered trees) by optimally transforming the documents into isomorphic ones, using operations such as add (add a new node), del (delete an existing node), and upd (make two nodes have the same label).
URL: https://globals.ieice.org/en_transactions/information/10.1093/ietisy/e88-d.10.2341/_p

Copy

@ARTICLE{e88-d_10_2341,
author={Nobutaka SUZUKI, },
journal={IEICE TRANSACTIONS on Information},
title={A Polynomial-Time Algorithm for Merging Structured Documents},
year={2005},
volume={E88-D},
number={10},
pages={2341-2353},
abstract={Document merging is essential to synchronizing several versions of a document concurrently edited by two or more users. A few methods for merging structured documents have been proposed so far, and yet the methods may not always merge given documents appropriately. As an aid for finding an appropriate merging, using another approach we propose a polynomial-time algorithm for merging structured documents. In the approach, we merge given two documents (treated as ordered trees) by optimally transforming the documents into isomorphic ones, using operations such as add (add a new node), del (delete an existing node), and upd (make two nodes have the same label).},
keywords={},
doi={10.1093/ietisy/e88-d.10.2341},
ISSN={},
month={October},}

Copy

TY - JOUR
TI - A Polynomial-Time Algorithm for Merging Structured Documents
T2 - IEICE TRANSACTIONS on Information
SP - 2341
EP - 2353
AU - Nobutaka SUZUKI
PY - 2005
DO - 10.1093/ietisy/e88-d.10.2341
JO - IEICE TRANSACTIONS on Information
SN -
VL - E88-D
IS - 10
JA - IEICE TRANSACTIONS on Information
Y1 - October 2005
AB - Document merging is essential to synchronizing several versions of a document concurrently edited by two or more users. A few methods for merging structured documents have been proposed so far, and yet the methods may not always merge given documents appropriately. As an aid for finding an appropriate merging, using another approach we propose a polynomial-time algorithm for merging structured documents. In the approach, we merge given two documents (treated as ordered trees) by optimally transforming the documents into isomorphic ones, using operations such as add (add a new node), del (delete an existing node), and upd (make two nodes have the same label).
ER -