An application of games to the completeness problem for formalized theories

Cited in

(only showing first 100 items - show all)

Finite information logic
Foundations and philosophy of mathematics in Warsaw, the school of Andrzej Mostowski and philosophy
Graph connectivity, monadic NP and built-in relations of moderate degree
An undecidable linear order that is \(n\)-decidable for all \(n\)
On limit points of spectra of first-order sentences with quantifier depth 4
Arboreal categories and equi-resource homomorphism preservation theorems
Segment transit function of the induced path function of graphs and its first-order definability
The quantifier structure of sentences that characterize nondeterministic time complexity
Extensions of an idea of McNaughton
Succinct definitions in the first order theory of graphs
Synthesis of a DNF formula from a sample of strings using Ehrenfeucht-Fraïssé games
First-order logic on finite trees
On quantifier-rank equivalence between linear orders
On dot-depth two
On distinguishing sets of structures by first-order sentences of minimal quantifier rank
On the expressive power of hybrid branching-time logics
The metric linear-time branching-time spectrum on nondeterministic probabilistic processes
Expressive power and succinctness of the positive calculus of binary relations
Some undecidable determined games
Complete theories of unars
Generalized implicit definitions on finite structures
On the bounded theories of finite trees
Succinct ordering and aggregation constraints in algebraic array theories
Logic and Game Theory
On the expressive power of hybrid branching-time logics
The closure of monadic NP
Inherent complexity of recursive queries
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
Theories of linear order
Algorithmic uses of the Feferman-Vaught theorem
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
Finite-model theory -- A personal perspective
Games, equations and dot-depth two monoids
Ehrenfeucht-Fraïssé games on ordinals
Continuous time temporal logic with counting
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
Upper and lower bounds for first order expressibility
How to win a game with features
Definability with bounded number of bound variables
Star-free languages are Church-Rosser congruential
Arity bounds in first-order incremental evaluation and definition of polynomial time database queries
One unary function says less than two in existential second order logic
Generalized hex and logical characterizations of polynomial space
The complexity of graph connectivity
Zero-one laws for random \(k\)-partite graphs
Finitely representable databases
Queries with arithmetical constraints
Decomposable graphs and definitions with no quantifier alternation
To be announced
Decidable metric logics
Comparing the power of monadic NP games
Invariance under stuttering in a temporal logic of actions
An until hierarchy and other applications of an Ehrenfeucht-Fraïssé game for temporal logic
\(\text{BTL}_{2}\) and the expressive power of \(\text{ECTL}^{+}\)
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
A generalization of Ehrenfeucht's game and some applications
Number of quantifiers is better than number of tape cells
Monadic second-order properties of very sparse random graphs
A pebbling comonad for finite rank and variable logic, and an application to the equirank-variable homomorphism preservation theorem
Algebras for querying text regions: Expressive power and optimization
Minimal models of theories of one function symbol
A logical approach to asymptotic combinatorics. II: Monadic second-order properties
Logical complexity of induced subgraph isomorphism for certain families of graphs
Computational complexity of logical theories of one successor and another unary function
On winning strategies in Ehrenfeucht-Fraïssé games
Dialogue games for many-valued logics -- an overview
How to win a game with features
Trees, congruences and varieties of finite semigroups
The modal logics of the poison game
Some applications of topology to program semantics
A game-theoretic equivalence to the Hahn-Banach theorem
The Boolean algebra of the theory of linear orders
Future temporal logic needs infinitely many modalities
On almost future temporal logics
Logic over words on denumerable ordinals
Shrinking games and local formulas
On the computational complexity of the theory of Abelian groups
A Feferman-Vaught Decomposition Theorem for Weighted MSO Logic.
Back-and-forth systems for fuzzy first-order models
Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
Algorithmic problems concerning first-order definability of modal formulas on the class of all finite frames
Definability in dynamic logic
Modulo-counting quantifiers over finite trees
On the Ehrenfeucht-Fraïssé game in theoretical computer science (extended abstract)
Star-free sets of words on ordinals
The strategic balance of games in logic
Complete theories of unars
An optimal lower bound on the number of variables for graph identification
The theorems of beth and Craig in abstract model theory II. Compact logics
Universal zero-one k-law
Small model property reflects in games and automata
Complexity of Boolean algebras
Tree acceptors and some of their applications
Classifying regular events in symbolic logic

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)