Upper and lower bounds for first order expressibility
From MaRDI portal
Publication:1173404
Cites work
- Almost sure theories
- An application of games to the completeness problem for formalized theories
- scientific article; zbMATH DE number 3467028 (Why is no real title available?)
- scientific article; zbMATH DE number 3474957 (Why is no real title available?)
- scientific article; zbMATH DE number 3501006 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- Maze recognizing automata and nondeterministic tape complexity
- Number of quantifiers is better than number of tape cells
- On the Tape Complexity of Deterministic Context-Free Languages
- Probabilities on finite models
- Properties of almost all graphs and complexes
Cited in
(76)- Isomorphisms and 1-L reductions
- Properties that characterize LOGCFL
- Capturing complexity classes by fragments of second-order logic
- Infinitary logics and 0-1 laws
- An optimal lower bound on the number of variables for graph identification
- An extension of fixpoint logic with a symmetry-based choice construct
- Reflective relational machines
- A restricted second order logic for finite structures
- On the power of built-in relations in certain classes of program schemes
- Logical and schematic characterization of complexity classes
- Canonization for two variables and puzzles on the square
- Reachability and the power of local ordering
- How to define a linear order on finite models
- A query language for NC
- The Kolmogorov expressive power of Boolean query languages
- Path constraints in semistructured databases
- Generalized quantifiers and pebble games on finite structures
- Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
- How many variables are needed to express an existential positive query?
- Monadic second-order properties of very sparse random graphs
- Large finite structures with few \(L^k\)-types
- On the relative expressiveness of description logics and predicate logics
- On the unusual effectiveness of logic in computer science
- Number of variables is equivalent to space
- An infinitary system for the least fixed-point logic restricted to finite models
- An extension of the Ehrenfeucht-Fraïssé game for first order logics augmented with Lindström quantifiers
- Pebble games over ordered structural abstractions
- PEBBLE GAMES AND LINEAR EQUATIONS
- Reachability is harder for directed than for undirected finite graphs
- Ehrenfeucht-Fraïssé Games on Random Structures
- Fixed-Point Definability and Polynomial Time
- Universal quantifiers and time complexity of random access machines
- Finite Variable Logics in Descriptive Complexity Theory
- On the Decision Problem for Two-Variable First-Order Logic
- Computing on structures
- Implicit definability and infinitary logic in finite model theory (extended abstract)
- The dimension of the negation of transitive closure
- Tailoring recursion for complexity
- Expressibility of properties of relations
- The expressive power of fixed-point logic with counting
- The parameterized space complexity of model-checking bounded variable first-order logic
- On the Ehrenfeucht-Fraïssé game in theoretical computer science (extended abstract)
- On asymptotic probabilities in logics that capture \(\mathrm{DSPACE}(\log n)\) in presence of ordering
- \(\mathrm{FO}=\mathrm{FO}^3\) for linear orders with monotone binary relations
- A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
- Infinitary logic for computer science
- Fragments of first-order logic over infinite words
- The axiom of elementary sets on the edge of Peircean expressibility
- GAMES AND CARDINALITIES IN INQUISITIVE FIRST-ORDER LOGIC
- Metafinite model theory
- A restricted second order logic for finite structures
- 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
- Count-free Weisfeiler-Leman and group isomorphism
- First order logic, fixed point logic and linear order
- The pebble-relation comonad in finite model theory
- Cutting planes width and the complexity of graph isomorphism refutations
- The pebble-relation comonad in finite model theory
- The expressiveness of a family of finite set languages
- The \(k\)-variable property is stronger than H-dimension \(k\)
- On the parallel complexity of group isomorphism via Weisfeiler-Leman
- Finite-model theory -- A personal perspective
- The umbilical cord of finite model theory
- From quantifier depth to quantifier number: separating structures with k variables
- Near-optimal lower bounds on quantifier depth and Weisfeiler-Leman refinement steps
- Multi-structural games and beyond
- Linear algebraic quantifiers
- Existential and positive games: a comonadic and axiomatic view
- Advances in algorithmic meta theorems (invited paper)
- Supercritical size-width tree-like resolution trade-offs for graph isomorphism
- On simplicity of formulas
- Asymptotic probabilities of extension properties and random l-colourable structures
- Parametrization over inductive relations of a bounded number of variables
- Definability with bounded number of bound variables
- When is arithmetic possible?
This page was built for publication: Upper and lower bounds for first order expressibility
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1173404)
