Eliminating Recursion from Monadic Datalog Programs on Trees

May 10, 2015 · The Ethereal · 🏛 International Symposium on Mathematical Foundations of Computer Science

🔮 THE ETHEREAL: The Ethereal
Pure theory — exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Filip Mazowiecki, Joanna Ochremiak, Adam Witkowski arXiv ID 1505.02444 Category cs.LO: Logic in CS Cross-listed cs.DB Citations 2 Venue International Symposium on Mathematical Foundations of Computer Science Last Checked 5 months ago
Abstract
We study the problem of eliminating recursion from monadic datalog programs on trees with an infinite set of labels. We show that the boundedness problem, i.e., determining whether a datalog program is equivalent to some nonrecursive one is undecidable but the decidability is regained if the descendant relation is disallowed. Under similar restrictions we obtain decidability of the problem of equivalence to a given nonrecursive program. We investigate the connection between these two problems in more detail.
Community shame:
Not yet rated
📄 View on arXiv 🌐 View on ar5iv 📑 PDF 🎉 Report Code Found
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

📜 Similar Papers

In the same crypt — Logic in CS