by Tadeusz Litak and Sven Helmer
Reference:
Tadeusz Litak and Sven Helmer: On the Termination Problem for Declarative XML Message Processing, Chapter in Sourav S. Bhowmick, Josef Küng, Roland Wagner, eds.: Database and Expert Systems Applications, Lecture Notes in Computer Science, vol. 5690, pp. 83–97, Springer Berlin Heidelberg, 2009. We define a formal syntax and semantics for the Rule Definition Language (RDL) of DemaqLite, which is a fragment of the declarative XML message processing system Demaq. Based on this definition, we prove that the termination problem for any practically useful sublanguage of DemaqLiteRDL is undecidable, as any such language can emulate a Single Register Machine--a Turing-complete model of computation proposed by Shepherdson and Sturgis.
Bibtex Entry:
@incollection{LitakH09:dexa,
year={2009},
isbn={978-3-642-03572-2},
booktitle={Database and Expert Systems Applications},
volume={5690},
keywords={conf},
series={Lecture Notes in Computer Science},
editor={Bhowmick, Sourav S. and K\"{u}ng, Josef and Wagner, Roland},
doi={10.1007/978-3-642-03573-9_7},
title={On the Termination Problem for Declarative XML Message Processing},
url={http://dx.doi.org/10.1007/978-3-642-03573-9_7},
publisher={Springer Berlin Heidelberg},
author={Litak, Tadeusz and Helmer, Sven},
comment = {<div class="abstract">We define a formal syntax and semantics for the Rule Definition Language (RDL) of DemaqLite, which is a fragment of the declarative XML message processing system Demaq. Based on this definition, we prove that the termination problem for any practically useful sublanguage of DemaqLiteRDL is undecidable, as any such language can emulate a Single Register Machine--a Turing-complete model of computation proposed by Shepherdson and Sturgis.</div>},
pages={83--97}
}