Upper and lower bounds for first order expressibility

DOI10.1016/0022-0000(82)90011-3zbMath0503.68032OpenAlexW1984581643MaRDI QIDQ1173404

Publication date: 1982

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(82)90011-3

zbMATH Keywords

Turing machines alternating pebbling game combinatorial properties in the language without ordering first order expressibility as a measure of complexity time/space complexity

Mathematics Subject Classification ID

Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).

Related Items (62)

GAMES AND CARDINALITIES IN INQUISITIVE FIRST-ORDER LOGIC ⋮ Universal quantifiers and time complexity of random access machines ⋮ Finite Variable Logics in Descriptive Complexity Theory ⋮ On the Ehrenfeucht-Fraïssé game in theoretical computer science ⋮ On asymptotic probabilities in logics that capture DSPACE(log n) in presence of ordering ⋮ PEBBLE GAMES AND LINEAR EQUATIONS ⋮ Generalized quantifiers and pebble games on finite structures ⋮ Canonization for two variables and puzzles on the square ⋮ Isomorphisms and 1-L reductions ⋮ Reachability and the power of local ordering ⋮ How to define a linear order on finite models ⋮ Unnamed Item ⋮ A query language for NC ⋮ Monadic second-order properties of very sparse random graphs ⋮ Hierarchies in transitive closure logic, stratified Datalog and infinitary logic ⋮ The dimension of the negation of transitive closure ⋮ Reachability is harder for directed than for undirected finite graphs ⋮ An Extension of the Ehrenfeucht-Fraïssé Game for First Order Logics Augmented with Lindström Quantifiers ⋮ The Kolmogorov expressive power of Boolean query languages ⋮ On the relative expressiveness of description logics and predicate logics ⋮ Tailoring recursion for complexity ⋮ Preservation theorems in finite model theory ⋮ Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas ⋮ Arboreal categories and equi-resource homomorphism preservation theorems ⋮ Expressibility of properties of relations ⋮ On the Decision Problem for Two-Variable First-Order Logic ⋮ Parametrization over inductive relations of a bounded number of variables ⋮ The expressive power of fixed-point logic with counting ⋮ Definability with bounded number of bound variables ⋮ When is arithmetic possible? ⋮ Pebble Games over Ordered Structural Abstractions ⋮ Properties that characterize LOGCFL ⋮ Computing on structures ⋮ The expressiveness of a family of finite set languages ⋮ On the Unusual Effectiveness of Logic in Computer Science ⋮ The \(k\)-variable property is stronger than H-dimension \(k\) ⋮ Implicit definability and infinitary logic in finite model theory ⋮ Capturing complexity classes by fragments of second-order logic ⋮ Infinitary logics and 0-1 laws ⋮ A restricted second order logic for finite structures ⋮ The axiom of elementary sets on the edge of Peircean expressibility ⋮ Metafinite model theory ⋮ Finite-model theory -- A personal perspective ⋮ An optimal lower bound on the number of variables for graph identification ⋮ Number of variables is equivalent to space ⋮ Fragments of first-order logic over infinite words ⋮ Unnamed Item ⋮ Large finite structures with few \(L^k\)-types ⋮ Infinitary logic for computer science ⋮ Ehrenfeucht-Fraïssé Games on Random Structures ⋮ An extension of fixpoint logic with a symmetry-based choice construct ⋮ Reflective relational machines ⋮ A restricted second order logic for finite structures ⋮ On simplicity of formulas ⋮ A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties ⋮ Fixed-Point Definability and Polynomial Time ⋮ On the power of built-in relations in certain classes of program schemes ⋮ Asymptotic probabilities of extension properties and random \(l\)-colourable structures ⋮ How many variables are needed to express an existential positive query? ⋮ Path constraints in semistructured databases ⋮ An Infinitary System for the Least Fixed-Point Logic restricted to Finite Models ⋮ Logical and schematic characterization of complexity classes

Cites Work

This page was built for publication: Upper and lower bounds for first order expressibility