Reachability is in DynFO

February 26, 2015 · The Ethereal · 🏛 International Colloquium on Automata, Languages and Programming

🔮 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 Samir Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, Thomas Zeume arXiv ID 1502.07467 Category cs.LO: Logic in CS Cross-listed cs.CC, cs.DS Citations 45 Venue International Colloquium on Automata, Languages and Programming Last Checked 1 month ago
Abstract
Patnaik and Immerman introduced the dynamic complexity class DynFO of database queries that can be maintained by first-order dynamic programs with the help of auxiliary relations under insertions and deletions of edges (Patnaik and Immerman 1997). This article confirms their conjecture that the Reachability query is in DynFO. As a byproduct it is shown that the rank of a matrix with small values can be maintained in DynFO(+,x). It is further shown that the (size of the) maximum matching of a graph can be maintained in non-uniform DynFO, another extension of DynFO, with non-uniform initialisation of the auxiliary relations.
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