\input zb-basic
\input zb-ioport
\iteman{io-port 05313322}
\itemau{Egri, L\'aszl\'o; Larose, Beno{\^\i}t; Tesson, Pascal}
\itemti{Directed $st$-connectivity is not expressible in symmetric Datalog.}
\itemso{Aceto, Luca (ed.) et al., Automata, languages and programming. 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 7--11, 2008. Proceedings, Part II. Berlin: Springer (ISBN 978-3-540-70582-6/pbk). Lecture Notes in Computer Science 5126, 172-183 (2008).}
\itemab
Summary: We show that the directed $st$-connectivity problem cannot be expressed in symmetric Datalog, a fragment of Datalog introduced in [{\it L. Egri}, {\it B. Larose} and {\it P. Tesson}, ``Symmetric Datalog and constraint satisfaction problems in logspace", in: Proceedings of the 22nd Annual IEEE Symposium on Logic in Computer Science, LICS 2007, 193--202 (2007)]. It was shown there that symmetric Datalog programs can be evaluated in logarithmic space and that this fragment of Datalog captures logspace when augmented with negation, and an auxiliary successor relation $S$ together with two constant symbols for the smallest and largest elements with respect to $S$. In contrast, undirected $st$-connectivity is expressible in symmetric Datalog and is in fact one of the simplest examples of the expressive power of this logic. It follows that undirected non-$st$-connectivity can be expressed in restricted symmetric monotone Krom SNP, whereas directed non-$st$-connectivity is only definable in the more expressive restricted monotone Krom SNP. By results of [{\it B. Larose} and {\it P. Tesson}, ``Universal algebra and hardness results for constraint satisfaction problems", Lect. Notes Comput. Sci. 4596, 267--278 (2007; Zbl 1171.68731)], the inexpressibility result for directed $st$-connectivity extends to a wide class of homomorphism problems that fail to meet a certain algebraic condition.
\itemrv{~}
\itemcc{}
\itemut{}
\itemli{doi:10.1007/978-3-540-70583-3\_15}
\end