scientific article
From MaRDI portal
Publication:3758820
zbMath0622.03030MaRDI QIDQ3758820
Publication date: 1984
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Abstract data types; algebraic specification (68Q65) Classical first-order logic (03B10) Complexity of computation (including implicit computational complexity) (03D15)
Related Items (46)
A polynomial excluded-minor approximation of treedepth ⋮ Computing queries with higher-order logics ⋮ Henkin quantifiers and complete problems ⋮ Fixed-point extensions of first-order logic ⋮ Datalog vs first-order logic ⋮ Generalized quantifiers and pebble games on finite structures ⋮ Mechanical translation of set theoretic problem specifications into efficient RAM code - a case study ⋮ Inductive definitions over finite structures ⋮ Exact Query Reformulation with First-Order Ontologies and Databases ⋮ The monadic second-order logic of graphs, II: Infinite graphs of bounded width ⋮ The computational complexity of asymptotic problems. I: Partial orders ⋮ How to define a linear order on finite models ⋮ Descriptive complexity of deterministic polylogarithmic time and space ⋮ Metafinite model theory ⋮ Relativised homomorphism preservation at the finite level ⋮ Preservation theorems in finite model theory ⋮ First-order spectra with one variable ⋮ 0-1 laws and decision problems for fragments of second-order logic ⋮ Computing on structures ⋮ Tailoring recursion for complexity ⋮ Implicit definability and infinitary logic in finite model theory ⋮ 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 ⋮ Metafinite model theory ⋮ Using the Hamiltonian path operator to capture NP ⋮ Finite-model theory -- A personal perspective ⋮ The concept of truth in a finite universe ⋮ Characterizing complexity classes by general recursive definitions in higher types ⋮ Aggregate operators in constraint query languages ⋮ On the expressibility and the computability of untyped queries ⋮ A Logic for PTIME and a Parameterized Halting Problem ⋮ Homomorphism preservation on quasi-wide classes ⋮ A monotone preservation result for Boolean queries expressed as a containment of conjunctive queries ⋮ Infinitary logic for computer science ⋮ The Context of Inference ⋮ Reflective relational machines ⋮ On the expressive power of data dependencies ⋮ Verifiable properties of database transactions ⋮ Querying spatial databases via topological invariants ⋮ Counting modulo quantifiers on finite structures ⋮ Unnamed Item ⋮ Formal frameworks for approximate reasoning ⋮ Hereditarily-finite sets, data bases and polynomial-time computability ⋮ The expressive power of stratified logic programs ⋮ ASNP: a tame fragment of existential second-order logic
This page was built for publication:
