Journal article icon

Journal article

Determinacy and rewriting of functional top–down and MSO tree transformations

Abstract:

A query is determined by a view, if the result of the query can be reconstructed from the result of the view. We consider the problem of deciding for two given (functional) tree transformations, whether one is determined by the other. If the view transformation is induced by a tree transducer that may copy, then determinacy is undecidable. For a large class of noncopying views, namely compositions of extended linear top–down tree transducers, we show that determinacy is decidable, where queri...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
  • (Accepted manuscript, pdf, 233.1KB)
Publisher copy:
10.1016/j.jcss.2016.11.001

Authors


More by this author
Institution:
University of Oxford
Oxford college:
University College
Role:
Author
Publisher:
Elsevier Publisher's website
Journal:
Journal of Computer and System Sciences Journal website
Volume:
85
Pages:
57-73
Publication date:
2016-11-22
Acceptance date:
2016-11-04
DOI:
EISSN:
1090-2724
ISSN:
0022-0000
Source identifiers:
668158
Keywords:
Pubs id:
pubs:668158
UUID:
uuid:110718e8-46b4-460d-8882-93a34d054bc6
Local pid:
pubs:668158
Deposit date:
2017-01-26

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP