scientific article; zbMATH DE number 515737
From MaRDI portal
Publication:4283240
zbMath0792.68061MaRDI QIDQ4283240
Publication date: 7 August 1994
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
infinitary logicexpressivenessfinite model theoryinductive definabilitylogical languagesdatabase query language Datalogfixpoint logic with counting termspolynomial-time computable queries
Analysis of algorithms and problem complexity (68Q25) Other nonclassical logic (03B60) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other infinitary logic (03C75)
Related Items (19)
Canonization for two variables and puzzles on the square ⋮ How to define a linear order on finite models ⋮ Metafinite model theory ⋮ Is Polynomial Time Choiceless? ⋮ Capturing the polynomial hierarchy by second-order revised Krom logic ⋮ Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus ⋮ Expressiveness of efficient semi-deterministic choice constructs ⋮ Tailoring recursion for complexity ⋮ On the expressive power of counting ⋮ A semideterministic approach to object creation and nondeterminism in database queries ⋮ Metafinite model theory ⋮ Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs ⋮ Undecidability results on two-variable logics ⋮ Choiceless Logarithmic Space ⋮ Sequences, datalog, and transducers ⋮ Querying spatial databases via topological invariants ⋮ An algebra for pomsets. ⋮ Adding for-loops to first-order logic ⋮ Canonisation and Definability for Graphs of Bounded Rank Width
This page was built for publication:
