www.uhasselt.be
DSpace

Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/15816

Title: Simplifying XML Schema: Single-type approximations of regular tree languages
Authors: GELADE, Wouter
Idziaszek, Tomasz
Martens, Wim
Neven, Frank
Paredaens, Jan
Issue Date: 2013
Citation: JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 79 (6), p. 910-936
Abstract: XML Schema Definitions (XSDs) can be adequately abstracted by the single-type regular tree languages. It is well known that these form a strict subclass of the robust class of regular unranked tree languages. Sadly, in this respect, XSDs are not closed under the basic operations of union and set difference, complicating important tasks in schema integration and evolution. The purpose of this paper is to investigate how the union and difference of two XSDs can be approximated within the framework of single-type regular tree languages. We consider both optimal lower and upper approximations. We also address the more general question of how to approximate an arbitrary regular tree language by an XSD and consider the complexity of associated decision problems.
Notes: Martens, W (reprint author), Univ Bayreuth, Bayreuth, Germany. Email: wouter.gelade@uhasselt.be; idziaszek@mimuw.edu.pl; wim.martens@uni-bayreuth.de; frank.neven@uhasselt.be; jan.paredaens@ua.ac.be
URI: http://hdl.handle.net/1942/15816
DOI: http://dx.doi.org/10.1016/j.jcss.2013.01.009
ISI #: 000319368900009
ISSN: 0022-0000
Category: A1
Type: Journal Contribution
Validation: ecoom, 2014
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
Postprint version457.72 kBAdobe PDF
Published version499.54 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.