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
Version:
Accepted Manuscript

Actions


Access Document


Files:
Publisher copy:
10.1016/j.jcss.2016.11.001

Authors


More by this author
Department:
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
DOI:
EISSN:
1090-2724
ISSN:
0022-0000
Pubs id:
pubs:668158
URN:
uri:110718e8-46b4-460d-8882-93a34d054bc6
UUID:
uuid:110718e8-46b4-460d-8882-93a34d054bc6
Local pid:
pubs:668158

Terms of use


Metrics


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