scientific article; zbMATH DE number 803291

Publication date: 9 October 1995

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Turing machines optimization problems finite automata compactness theorem finite model theory complexity classes fixed-point logic oracles 0-1 laws Lindström quantifiers logics with fixed-point operators

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (only showing first 100 items - show all)

ON DOUBLE-MEMBERSHIP GRAPHS OF MODELS OF ANTI-FOUNDATION ⋮ Second-Order Finite Automata ⋮ On Preservation Theorems for Two-Variable Logic ⋮ A Pigeonhole Property for Relational Structures ⋮ Algebraic and logical characterizations of deterministic linear time classes ⋮ Relativization of Gurevich’s Conjectures ⋮ Convergence and Nonconvergence Laws for Random Expansions of Product Structures ⋮ The complexity class θp2: Recent results and applications in AI and modal logic ⋮ The Directed Geodetic Structure of a Strong Digraph ⋮ Satisfiability of ECTL* with Tree Constraints ⋮ Reasoning About Strategies ⋮ Bounds for the Quantifier Depth in Finite-Variable Logics ⋮ Composition Over the Natural Number Ordering with an Extra Binary Relation ⋮ Definability in the class of all -frames – computability and complexity ⋮ Unnamed Item ⋮ Expressive Power and Succinctness of the Positive Calculus of Relations ⋮ Computer-Supported Exploration of a Categorical Axiomatization of Modeloids ⋮ Logics capturing relativized complexity classes uniformly ⋮ Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem ⋮ Inductive definitions in logic versus programs of real-time cellular automata ⋮ Capturing the polynomial hierarchy by second-order revised Krom logic ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An Infinite Automaton Characterization of Double Exponential Time ⋮ Pure Pointer Programs with Iteration ⋮ On the complexity of existential positive queries ⋮ Safe Recursion Over an Arbitrary Structure: PAR, PH and DPH ⋮ On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic ⋮ The concept of truth in a finite universe ⋮ On the Complexity of RSRL ⋮ On the expressibility and the computability of untyped queries ⋮ The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey ⋮ Definability of Combinatorial Functions and Their Linear Recurrence Relations ⋮ Recursive Definitions and Fixed-Points ⋮ Simulation of the nested relational algebra by the flat relational algebra, with an application to the complexity of evaluating powerset algebra expressions ⋮ Locally finite languages ⋮ Learning logic programs with structured background knowledge ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The descriptive complexity approach to LOGCFL ⋮ The monadic quantifier alternation hierarchy over grids and graphs ⋮ Linear Recurrence Relations for Graph Polynomials ⋮ selp: A Single-Shot Epistemic Logic Program Solver ⋮ Primitive recursion in the abstract ⋮ Complexity thresholds in inclusion logic ⋮ Subshifts, Languages and Logic ⋮ Logical Foundations of XML and XQuery ⋮ Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems ⋮ One-Dimensional Logic over Trees ⋮ Arity hierarchies ⋮ An Infinitary System for the Least Fixed-Point Logic restricted to Finite Models ⋮ An explicit construction of graphs of bounded degree that are far from being Hamiltonian ⋮ Stability theory, permutations of indiscernibles, and embedded finite models ⋮ Trees, grids, and MSO decidability: from graphs to matroids ⋮ The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions. ⋮ One unary function says less than two in existential second order logic ⋮ Generalized hex and logical characterizations of polynomial space ⋮ A note on the Kolmogorov data complexity and nonuniform logical definitions ⋮ On the complexity of decision using destinies in \(H\)-bounded structures ⋮ Closure properties of locally finite \(\omega\)-languages ⋮ Arithmetical definability and computational complexity ⋮ A logical approach to locality in pictures languages ⋮ String theories involving regular membership predicates: from practice to theory and back ⋮ Parameterized model checking of rendezvous systems ⋮ Expressive power and succinctness of the positive calculus of binary relations ⋮ Verification of agent navigation in partially-known environments ⋮ First-order queries on databases embedded in an infinite structure ⋮ Controlled query evaluation with open queries for a decidable relational submodel ⋮ A parameterized view on the complexity of dependence logic ⋮ Canonization for two variables and puzzles on the square ⋮ Second-order finite automata ⋮ The complexity of model checking multi-stack systems ⋮ Graph properties checkable in linear time in the number of vertices ⋮ Algorithmic uses of the Feferman-Vaught theorem ⋮ FO(ID) as an extension of DL with rules ⋮ Metafinite model theory ⋮ Choice functions and well-orderings over the infinite binary tree ⋮ Satisfiability of \(\mathrm{ECTL}^*\) with local tree constraints ⋮ Subshifts as models for MSO logic ⋮ A representation theorem for (\(q\)-)holonomic sequences ⋮ MSOL partitioning problems on graphs of bounded treewidth and clique-width ⋮ Bisimulation invariant monadic-second order logic in the finite ⋮ A progression semantics for first-order logic programs ⋮ Analysis and application of adaptive sampling ⋮ Verification of relational transducers for electronic commerce ⋮ Farrell polynomials on graphs of bounded tree width ⋮ Counting on CTL\(^*\): On the expressive power of monadic path logic ⋮ The Specker-Blatter theorem does not hold for quaternary relations ⋮ Quantifier rank for parity of embedded finite models. ⋮ Incremental recomputation in local languages. ⋮ On the power of tree-walking automata. ⋮ On the complexity of single-rule datalog queries. ⋮ Ordered completion for first-order logic programs on finite structures ⋮ Locality and modular Ehrenfeucht-Fraïssé games ⋮ An optimal construction of Hanf sentences ⋮ Algorithmic correspondence and completeness in modal logic. V. Recursive extensions of SQEMA ⋮ The joy of probabilistic answer set programming: semantics, complexity, expressivity, inference ⋮ Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus ⋮ The enumeration of vertex induced subgraphs with respect to the number of components ⋮ Book review of: E. Grädel, P. Kolaitis, L. Libkin, M. Marx, I. Spencer, M. Vardi, Y. Venema, S. Weinstein, Finite model theory and its applications

This page was built for publication: