Adding for-loops to first-order logic

Citation
F. Neven et al., Adding for-loops to first-order logic, INF COMPUT, 168(2), 2001, pp. 156-186
Citations number
16
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION AND COMPUTATION
ISSN journal
08905401 → ACNP
Volume
168
Issue
2
Year of publication
2001
Pages
156 - 186
Database
ISI
SICI code
0890-5401(20010801)168:2<156:AFTFL>2.0.ZU;2-W
Abstract
We study the query language BQL: the extension of the relational algebra wi th for-loops. We also study FO(FOR): the extension of first-order logic wit h a for-loop variant of the partial fixpoint operator. In contrast to the k nown situation with query languages, which include while-loops instead of f or-loops, BQL and FO(FOR) are not equivalent. Among the topics we investiga te are: the precise relationship between BQL and FO(FOR); inflationary vers us noninflationary iteration the relationship with logics that have the abi lity to count: and nested versus unnested loops. (C) 2001 Academic Press.