scientific article; zbMATH DE number 4008383

zbMATH Open0622.03030MaRDI QIDQ3758820FDOQ3758820

Authors: Yuri Gurevich 

Publication date: 1984

Title of this publication is not available (Why is that?)

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

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)

Cited In (64)

• Metafinite model theory
• First order logic, fixed point logic and linear order
• Generalized implicit definitions on finite structures
• Rank logic is dead, long live rank logic!
• Title not available (Why is that?)
• Forbidden induced subgraphs and the Łoś-Tarski theorem
• The expressive power of stratified logic programs
• Mechanical translation of set theoretic problem specifications into efficient RAM code - a case study
• On the expressibility and the computability of untyped queries
• Implicit definability and infinitary logic in finite model theory (extended abstract)
• Infinitary logics and 0-1 laws
• Using the Hamiltonian path operator to capture NP
• Title not available (Why is that?)
• Applicative theories for logarithmic complexity classes
• Formal frameworks for approximate reasoning
• Henkin quantifiers and complete problems
• Finite-model theory -- A personal perspective
• 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
• Minimal predicates, fixed-points, and definability
• The concept of truth in a finite universe
• Aggregate operators in constraint query languages
• Fixed-point extensions of first-order logic
• Verifiable properties of database transactions
• Infinitary logic for computer science
• Counting modulo quantifiers on finite structures
• Computing queries with higher-order logics
• Title not available (Why is that?)
• Reflective relational machines
• Datalog vs first-order logic
• A recipe for the complexity analysis of non-classical logics
• Characterizing complexity classes by higher type primitive recursive definitions
• Bounded linear logic: A modular approach to polynomial-time computability
• Homomorphism preservation on quasi-wide classes
• Tailoring recursion for complexity
• First-order spectra with one variable
• Generalized quantifiers and pebble games on finite structures
• Destructive rule-based properties and first-order logic
• Hereditarily-finite sets, data bases and polynomial-time computability
• 0-1 laws and decision problems for fragments of second-order logic
• 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
• Preservation theorems in finite model theory
• Exact query reformulation with first-order ontologies and databases
• Equivalence in finite-variable logics is complete for polynomial time
• Title not available (Why is that?)
• Title not available (Why is that?)
• Some Turing-complete extensions of first-order logic
• Computing on structures
• How to define a linear order on finite models
• 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
• Title not available (Why is that?)
• ASNP: a tame fragment of existential second-order logic
• Title not available (Why is that?)

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)