An application of games to the completeness problem for formalized theories
From MaRDI portal
Publication:3274971
DOI10.4064/fm-49-2-129-141zbMath0096.24303OpenAlexW1555138513MaRDI QIDQ3274971
Publication date: 1961
Published in: Fundamenta Mathematicae (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/213582
Related Items (only showing first 100 items - show all)
Differential Game Logic ⋮ Structure and Power: an Emerging Landscape ⋮ On the Ehrenfeucht-Fraïssé game in theoretical computer science ⋮ A zero‐one law for a random subset ⋮ Unnamed Item ⋮ A logical approach to asymptotic combinatorics. II: Monadic second-order properties ⋮ Probabilities of Sentences about Very Sparse Random Graphs ⋮ Probabilities of First-Order Sentences about Unary Functions ⋮ A game-theoretic equivalence to the Hahn-Banach theorem ⋮ Cyclic congruences of slim semimodular lattices and non-finite axiomatizability of some finite structures ⋮ Short Monadic Second Order Sentences about Sparse Random Graphs ⋮ Modeloids. I ⋮ Extensions of an idea of McNaughton ⋮ 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 ⋮ On Almost Future Temporal Logics ⋮ First-order logic on finite trees ⋮ The complexity of graph connectivity ⋮ To be announced ⋮ Comparing the power of monadic NP games ⋮ Back and Forth in Positive Logic ⋮ EHRENFEUCHT-FRAÏSSÉ GAMES ON A CLASS OF SCATTERED LINEAR ORDERS ⋮ Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas ⋮ A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth ⋮ Arboreal categories and equi-resource homomorphism preservation theorems ⋮ Segment transit function of the induced path function of graphs and its first-order definability ⋮ Generalized quantifiers and well orderings ⋮ First-order logic axiomatization of metric graph theory ⋮ First-order properties of bounded quantifier depth of very sparse random graphs ⋮ First-order zero-one law for the uniform model of the random graph ⋮ Foundations and Philosophy of Mathematics in Warsaw, the School of Andrzej Mostowski and Philosophy ⋮ Unnamed Item ⋮ Model-interpretability into trees and applications ⋮ A Feferman-Vaught Decomposition Theorem for Weighted MSO Logic. ⋮ Complete theories of unars ⋮ Graph Connectivity, Monadic NP and built-in relations of moderate degree ⋮ Complete theories of unars ⋮ Propositional Games with Explicit Strategies ⋮ A Practical Approach to Courcelle's Theorem ⋮ An undecidable linear order that is \(n\)-decidable for all \(n\) ⋮ Some applications of topology to program semantics ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On dot-depth two ⋮ Unnamed Item ⋮ On the elementary theory of inductive order ⋮ On Q-Resolution and CDCL QBF Solving ⋮ Uniformly Automatic Classes of Finite Structures ⋮ How to win a game with features ⋮ The probability nesting game ⋮ Topological model theory with an interior operator: Consistency properties and back — and forth arguments ⋮ The theorems of beth and Craig in abstract model theory II. Compact logics ⋮ Logical complexity of induced subgraph isomorphism for certain families of graphs ⋮ Logic and Game Theory ⋮ Unnamed Item ⋮ On semidirect and two-sided semidirect products of finite $\mathcal {J}$trivial monoids ⋮ Complexity classes and theories of finite models ⋮ Modulo-counting quantifiers over finite trees ⋮ Shrinking games and local formulas ⋮ Future temporal logic needs infinitely many modalities ⋮ One unary function says less than two in existential second order logic ⋮ Generalized hex and logical characterizations of polynomial space ⋮ Succinct definitions in the first order theory of graphs ⋮ A pebbling comonad for finite rank and variable logic, and an application to the equirank-variable homomorphism preservation theorem ⋮ Expressive power and succinctness of the positive calculus of binary relations ⋮ Model theory of monadic predicate logic with the infinity quantifier ⋮ Ehrenfeucht-Fraïssé games on ordinals ⋮ On the computational complexity of the theory of Abelian groups ⋮ Universal zero-one \(k\)-law ⋮ Small model property reflects in games and automata ⋮ The expressive power of Malitz quantifiers for linear orderings ⋮ Invariance under stuttering in a temporal logic of actions ⋮ Algorithmic problems concerning first-order definability of modal formulas on the class of all finite frames ⋮ Computational complexity of logical theories of one successor and another unary function ⋮ An Ehrenfeucht-Fraïssé game approach to collapse results in database theory ⋮ Algorithmic uses of the Feferman-Vaught theorem ⋮ Finitely representable databases ⋮ Monadic second-order properties of very sparse random graphs ⋮ Ehrenfeucht games and ordinal addition ⋮ Hierarchies in transitive closure logic, stratified Datalog and infinitary logic ⋮ On winning Ehrenfeucht games and monadic NP ⋮ Automatic models of first order theories ⋮ Solutions and query rewriting in data exchange ⋮ Queries with arithmetical constraints ⋮ Complexity of Boolean algebras ⋮ The Boolean algebra of the theory of linear orders ⋮ Continuous time temporal logic with counting ⋮ On complexity of Ehrenfeucht-Fraïssé games ⋮ Definability in dynamic logic ⋮ Computing branching distances with quantitative games ⋮ On limit points of spectra of first-order sentences with quantifier depth 4 ⋮ Parametrization over inductive relations of a bounded number of variables ⋮ Number of quantifiers is better than number of tape cells ⋮ Definability with bounded number of bound variables ⋮ When is arithmetic possible? ⋮ Partial isomorphisms and intuitionistic logic ⋮ Some undecidable determined games ⋮ Upper and lower bounds for first order expressibility ⋮ Classifying regular events in symbolic logic ⋮ The quantitative linear-time-branching-time spectrum
This page was built for publication: An application of games to the completeness problem for formalized theories
