Computational model theory: an overview
complexity of relational computationscomputational model theoryexpressibilityfinite model theoryfixpoint logicsinfinitary logicsrelational machinerelational model of database computation
Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Model theory of finite structures (03C13) Other infinitary logic (03C75) Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Database theory (68P15)
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.
- scientific article; zbMATH DE number 939032
- Models of computation. An introduction to computability theory
- Model theory in computer science: my own recurrent themes
- Models and computability
- scientific article; zbMATH DE number 6845502
- scientific article; zbMATH DE number 1534487
- Computability and computable models
- scientific article; zbMATH DE number 733393
- Model-theoretic methods of analysis of computer arithmetic
- scientific article; zbMATH DE number 1533641
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)