Computational model theory: an overview

From MaRDI portal





This is an overview of computational model theory from the point of view of infinitary logics, especially the fixpoint logics and variants of \(L^\omega_{\infty\omega}\). The relational model of database computation uses a first-order logic, perhaps extended by a fixpoint operator: over a relational structure (database) \textbf{D}, given an operator \(\Phi\) from \(n\)-ary relations to \(n\)-ary relations, let \(\Phi^0= \emptyset\), \(\Phi^{m+1} =\Phi (\Phi^m)\). If \(\Phi\) is inflationary (ie., \(T\subseteq \Phi(T)\) for all \(T)\), and \(\Phi^\infty =\bigcup_m \Phi^m\), then \(\Phi^\infty =\Phi (\Phi^\infty)\) if \textbf{D} is finite. By extending the first-order logic with such fixpoints, one can get relational languages capable of recursion. Such a language can be simulated by a relational machine, which is a Turing-type machine that can do arithmetic but has limited access to cardinality properties of its database. Many expressibility problems can be efficiently dealt with by using the language \(L^\omega_{\infty \omega} =\bigcup_k L^k_{\infty \omega} \). Here, \(L^k_{\infty \omega}\) is the least class of formulas containing all first-order formulas of at most \(k\) variables, and closed under first-order operations and infinite disjunctions so long as the resulting formulas have at most \(k\) variables. \(L^\omega_{\infty \omega}\) is an extension of fixpoint logic, and the ``recursively enumerable fragment of \(L^\omega_{\infty \omega}\) corresponds to an arithmetical hierarchy arising from the relational machines. The article concludes with some consequences in complexity of relational computations.











This page was built for publication: Computational model theory: an overview

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210768)