An application of games to the completeness problem for formalized theories

Cited In (only showing first 100 items - show all)

Extensions of an idea of McNaughton
First-order logic on finite trees
The quantifier structure of sentences that characterize nondeterministic time complexity
Succinct definitions in the first order theory of graphs
On dot-depth two
Complete theories of unars
On distinguishing sets of structures by first-order sentences of minimal quantifier rank
Logic and Game Theory
Expressive power and succinctness of the positive calculus of binary relations
Some undecidable determined games
The closure of monadic NP
Inherent complexity of recursive queries
Theories of linear order
Algorithmic uses of the Feferman-Vaught theorem
Games, equations and dot-depth two monoids
Finite-model theory -- A personal perspective
Continuous time temporal logic with counting
Upper and lower bounds for first order expressibility
Definability with bounded number of bound variables
The complexity of graph connectivity
Star-free languages are Church-Rosser congruential
One unary function says less than two in existential second order logic
Generalized hex and logical characterizations of polynomial space
Finitely representable databases
Queries with arithmetical constraints
An until hierarchy and other applications of an Ehrenfeucht-Fraïssé game for temporal logic
Decidable metric logics
Invariance under stuttering in a temporal logic of actions
On the zero-one 4-law for the Erdős-Rényi random graphs
The Banach spaces \(l_ p(n)\) for large p and n
Number of quantifiers is better than number of tape cells
A logical approach to asymptotic combinatorics. II: Monadic second-order properties
Algebras for querying text regions: Expressive power and optimization
Computational complexity of logical theories of one successor and another unary function
On winning strategies in Ehrenfeucht-Fraïssé games
Trees, congruences and varieties of finite semigroups
On almost future temporal logics
Future temporal logic needs infinitely many modalities
Logic over words on denumerable ordinals
On the computational complexity of the theory of Abelian groups
Definability in dynamic logic
On the Ehrenfeucht-Fraïssé game in theoretical computer science (extended abstract)
Star-free sets of words on ordinals
The theorems of beth and Craig in abstract model theory II. Compact logics
A Practical Approach to Courcelle's Theorem
An optimal lower bound on the number of variables for graph identification
Tree acceptors and some of their applications
Complexity of Boolean algebras
Universal zero-one \(k\)-law
Classifying regular events in symbolic logic
Representation-finite triangular algebras form an open scheme
Infinite spectra of first-order properties for random hypergraphs
Cyclic congruences of slim semimodular lattices and non-finite axiomatizability of some finite structures
Model-interpretability into trees and applications
A representation theorem for languages with generalized quantifiers through back-and-forth methods
Classifying \(\aleph_ 0\)-categorical theories
On simplicity of formulas
Structure and complexity of relational queries
On winning Ehrenfeucht games and monadic NP
Games, equations and the dot-depth hierarchy
The first order definability of graphs with separators via the Ehrenfeucht game
Parametrization over inductive relations of a bounded number of variables
When is arithmetic possible?
Calculus with the quantifier of elementary equivalence
Model theory of the regularity and reflection schemes
On complexity of Ehrenfeucht-Fraïssé games
An Ehrenfeucht-Fraïssé game approach to collapse results in database theory
Probabilities of First-Order Sentences about Unary Functions
Model theory of monadic predicate logic with the infinity quantifier
Complexity classes and theories of finite models
Probabilities of Sentences about Very Sparse Random Graphs
Elementary equivalence and relatively free products of lattices
The invariant problem for binary string structures and the parallel complexity theory of queries
Automatic models of first order theories
Solutions and query rewriting in data exchange
On the expressive power of counting
On limit points of spectra of first-order sentences with quantifier depth 4
Synthesis of a DNF formula from a sample of strings using Ehrenfeucht-Fraïssé games
On quantifier-rank equivalence between linear orders
Generalized implicit definitions on finite structures
On the bounded theories of finite trees
Succinct ordering and aggregation constraints in algebraic array theories
On the expressive power of hybrid branching-time logics
The metric linear-time branching-time spectrum on nondeterministic probabilistic processes
On the expressive power of hybrid branching-time logics
Topological model theory with an interior operator: Consistency properties and back — and forth arguments
Local properties of query languages
An infinite hierarchy of temporal logics over branching time
The Ehrenfeucht-Fraïssé method and the planted clique conjecture
An extension of the Ehrenfeucht-Fraïssé game for first order logics augmented with Lindström quantifiers
The expressive power of Malitz quantifiers for linear orderings
Ehrenfeucht-Fraïssé games on ordinals
Synthesis of quantifier-free DNF sentences from inconsistent samples of strings with EF games and SAT
A technique for proving decidability of containment and equivalence of linear constraint queries
How to win a game with features
Arity bounds in first-order incremental evaluation and definition of polynomial time database queries
Zero-one laws for random \(k\)-partite graphs
To be announced
Decomposable graphs and definitions with no quantifier alternation
Comparing the power of monadic NP games

This page was built for publication: An application of games to the completeness problem for formalized theories

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3274971)