Metafinite model theory

DOI10.1006/inco.1997.2675zbMath0892.68033OpenAlexW2045916776MaRDI QIDQ1383163

Erich Grädel, Yuri Gurevich

Publication date: 4 May 1998

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1997.2675

zbMATH Keywords

descriptive complexitymetafinite structures

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Applications of model theory (03C98) Descriptive complexity and finite models (68Q19)

Related Items

Computing queries with higher-order logics ⋮ A new thesis concerning synchronised parallel computing -- simplified parallel ASM thesis ⋮ Unnamed Item ⋮ Finitely representable databases ⋮ On elementary logics for quantitative dependencies ⋮ Queries with arithmetical constraints ⋮ Expressive power of SQL. ⋮ Expressive power and abstraction in Essence ⋮ Safe Recursion Over an Arbitrary Structure: PAR, PH and DPH ⋮ Expressibility of Higher Order Logics ⋮ Database Theory, Yuri, and Me ⋮ Periodic generalized automata over the reals ⋮ Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals ⋮ Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals ⋮ The Computational Complexity of Quantified Reciprocals ⋮ From a zoo to a zoology: Towards a general theory of graph polynomials ⋮ Primitive recursion in the abstract ⋮ A Proof System with Bounded Non-determinism in Database Transformations ⋮ Logics which capture complexity classes over the reals ⋮ On polynomial time computation over unordered structures

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finite-model theory -- A personal perspective
• A normal form for arithmetical representation of \({\mathcal N}{\mathcal P}\)-sets
• Fixed-point extensions of first-order logic
• Nonconvergence, undecidability, and intractability in asymptotic problems
• 0-1 laws for recursive structures
• Computable queries for relational data bases
• An arithmetical characterization of NP
• Nonconvergence in the theory of random orders
• Optimization, approximation, and complexity classes
• Extended order-generic queries
• Finitely representable databases
• Handling infinite temporal data
• Completeness results for recursive data bases
• Register machine proof of the theorem on exponential diophantine representation of enumerable sets
• Relational queries computable in polynomial time
• The Complexity of Enumeration and Reliability Problems
• Almost sure theories
• On Moschovakis closure ordinals
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Deux ou trois choses que je sais de L_n
• Evolving Algebras 1993: Lipari Guide
• The expressive power of fixed-point logic with counting