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

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

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

(77)

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

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)