First-order queries on structures of bounded degree are computable with constant delay

Simple item page
dc.creatorDurand, Arnaud
dc.creatorGrandjean, Etienne
dc.date2005-07-07
dc.date.accessioned2026-07-07T03:23:12Z
dc.date.available2026-07-07T03:23:12Z
dc.descriptionA bounded degree structure is either a relational structure all of whose relations are of bounded degree or a functional structure involving bijective functions only. In this paper, we revisit the complexity of the evaluation problem of not necessarily Boolean first-order queries over structures of bounded degree. Query evaluation is considered here as a dynamical process. We prove that any query on bounded degree structures is $\constantdelaylin$, i.e., can be computed by an algorithm that has two separate parts: it has a precomputation step of linear time in the size of the structure and then, it outputs all tuples one by one with a constant (i.e. depending on the size of the formula only) delay between each. Seen as a global process, this implies that queries on bounded structures can be evaluated in total time $O(f(|ϕ|).(|\calS|+|ϕ(\calS)|))$ and space $O(f(|ϕ|).|\calS|)$ where $\calS$ is the structure, $ϕ$ is the formula, $ϕ(\calS)$ is the result of the query and $f$ is some function. Among other things, our results generalize a result of \cite{Seese-96} on the data complexity of the model-checking problem for bounded degree structures. Besides, the originality of our approach compared to that \cite{Seese-96} and comparable results is that it does not rely on the Hanf's model-theoretic technic (see \cite{Hanf-65}) and is completely effective.
dc.description18 pages, 1 figure
dc.identifierhttps://arxiv.org/abs/cs/0507020
dc.identifierhttp://arxiv.org/abs/cs/0507020
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/32854
dc.subjectLogic in Computer Science
dc.subjectComputational Complexity
dc.titleFirst-order queries on structures of bounded degree are computable with constant delay
dc.typetext

Files

Collections

arXiv