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
Bibliographic Details
- 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
Item Description
- Keywords:
- Pubs id:
-
pubs:668158
- UUID:
-
uuid:110718e8-46b4-460d-8882-93a34d054bc6
- Local pid:
- pubs:668158
- Deposit date:
- 2017-01-26
Terms of use
- Copyright holder:
- Elsevier Inc
- Copyright date:
- 2016
- Notes:
- Copyright © 2016 Elsevier Inc. This is the accepted manuscript version of the article. The final version is available online from Elsevier at: https://doi.org/10.1016/j.jcss.2016.11.001
If you are the owner of this record, you can report an update to it here: Report update to this record