scientific article; zbMATH DE number 4008383

MaRDI QIDQ3758820zbMATH OpenFDO

Authors Yuri Gurevich

Publication date 1984

zbMATH Keywords

first-order logic with finite structurespolynomial time logicsPTIME computable predicates

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Classical first-order logic (03B10) Abstract data types; algebraic specification (68Q65) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Infinitary logic and inductive definability over finite structures
• Logical hierarchies in PTIME
• On fixed-point logic with counting
• The expressive power of fixed-point logic with counting
• scientific article; zbMATH DE number 4009811

Cited in

(65)

• scientific article; zbMATH DE number 1555193 (Why is no real title available?)
• The expressive power of stratified logic programs
• Mechanical translation of set theoretic problem specifications into efficient RAM code - a case study
• Metafinite model theory
• Implicit definability and infinitary logic in finite model theory (extended abstract)
• Infinitary logics and 0-1 laws
• First order logic, fixed point logic and linear order
• Generalized implicit definitions on finite structures
• On the expressibility and the computability of untyped queries
• Using the Hamiltonian path operator to capture NP
• Applicative theories for logarithmic complexity classes
• Formal frameworks for approximate reasoning
• scientific article; zbMATH DE number 1223623 (Why is no real title available?)
• Finite-model theory -- A personal perspective
• Henkin quantifiers and complete problems
• A polynomial excluded-minor approximation of treedepth
• On the expressive power of data dependencies
• The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• The computational complexity of asymptotic problems. I: Partial orders
• Aggregate operators in constraint query languages
• Fixed-point extensions of first-order logic
• Minimal predicates, fixed-points, and definability
• The concept of truth in a finite universe
• Verifiable properties of database transactions
• Counting modulo quantifiers on finite structures
• Computing queries with higher-order logics
• Infinitary logic for computer science
• scientific article; zbMATH DE number 3903964 (Why is no real title available?)
• Reflective relational machines
• Datalog vs first-order logic
• Characterizing complexity classes by higher type primitive recursive definitions
• Bounded linear logic: A modular approach to polynomial-time computability
• A recipe for the complexity analysis of non-classical logics
• Rank logic is dead, long live rank logic!
• Homomorphism preservation on quasi-wide classes
• Tailoring recursion for complexity
• First-order spectra with one variable
• scientific article; zbMATH DE number 2079031 (Why is no real title available?)
• Generalized quantifiers and pebble games on finite structures
• 0-1 laws and decision problems for fragments of second-order logic
• Destructive rule-based properties and first-order logic
• Hereditarily-finite sets, data bases and polynomial-time computability
• Relativised homomorphism preservation at the finite level
• Inductive definitions over finite structures
• Querying spatial databases via topological invariants
• A monotone preservation result for Boolean queries expressed as a containment of conjunctive queries
• Metafinite model theory
• Exact query reformulation with first-order ontologies and databases
• Preservation theorems in finite model theory
• Equivalence in finite-variable logics is complete for polynomial time
• scientific article; zbMATH DE number 4009811 (Why is no real title available?)
• scientific article; zbMATH DE number 6866317 (Why is no real title available?)
• Some Turing-complete extensions of first-order logic
• How to define a linear order on finite models
• Computing on structures
• The context of inference
• Linear ordering on graphs, anti-founded sets and polynomial time computability
• Characterizing complexity classes by general recursive definitions in higher types
• A logic for PTIME and a parameterized halting problem
• Descriptive complexity of deterministic polylogarithmic time and space
• Infinitary logic and inductive definability over finite structures
• scientific article; zbMATH DE number 1086678 (Why is no real title available?)
• Forbidden induced subgraphs and the Łoś-Tarski theorem
• ASNP: a tame fragment of existential second-order logic

This page was built for publication:

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