Definability with bounded number of bound variables

DOI10.1016/0890-5401(89)90055-2zbMath0711.03004OpenAlexW2053510959MaRDI QIDQ922523

Dexter Kozen

Publication date: 1989

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(89)90055-2

zbMATH Keywords

temporal logictree modelsbounded- degree treesEhrenfeucht-Fraissé gamek-variable property

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Logic in computer science (03B70) Semantics in the theory of computing (68Q55) Model theory of finite structures (03C13) Other model constructions (03C30)

Related Items (34)

On inflationary fix-point operators safety ⋮ Finite \(H\)-dimension does not imply expressive completeness ⋮ On the Ehrenfeucht-Fraïssé game in theoretical computer science ⋮ Generalized quantifiers and pebble games on finite structures ⋮ How to define a linear order on finite models ⋮ Star-free picture expressions are strictly weaker than first-order logic ⋮ Complexity of equations valid in algebras of relations. I: Strong non-finitizability ⋮ Expressibility of properties of relations ⋮ Unnamed Item ⋮ Propositional interval neighborhood logics: expressiveness, decidability, and undecidable extensions ⋮ On the Decision Problem for Two-Variable First-Order Logic ⋮ A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS ⋮ Algebraization of quantifier logics, an introductory overview ⋮ The \(k\)-variable property is stronger than H-dimension \(k\) ⋮ WEAKLY ITERATED BLOCK PRODUCTS AND APPLICATIONS TO LOGIC AND COMPLEXITY ⋮ Infinitary logics and 0-1 laws ⋮ Descriptive complexity of finite structures: Saving the quantifier rank ⋮ The axiom of elementary sets on the edge of Peircean expressibility ⋮ The light side of interval temporal logic: the Bernays-Schönfinkel fragment of CDT ⋮ An optimal lower bound on the number of variables for graph identification ⋮ On the Weisfeiler-Leman dimension of fractional packing ⋮ Unnamed Item ⋮ First-order logic with two variables and unary temporal logic ⋮ On Expressive Powers of Timed Logics: Comparing Boundedness, Non-punctuality, and Deterministic Freezing ⋮ On simplicity of formulas ⋮ Unnamed Item ⋮ Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems ⋮ Is ``Some-other-time sometimes better than ``Sometime for proving partial correctness of programs? ⋮ Varieties ⋮ The first order definability of graphs with separators via the Ehrenfeucht game ⋮ Almost Everywhere Equivalence of Logics in Finite Model Theory ⋮ An until hierarchy and other applications of an Ehrenfeucht-Fraïssé game for temporal logic ⋮ Expressiveness of concept expressions in first-order description logics ⋮ Deciding the guarded fragments by resolution

Cites Work

• Preservation of expressive completeness in temporal models
• Complexity of Boolean algebras
• Definability in dynamic logic
• Upper and lower bounds for first order expressibility
• The computational complexity of logical theories
• An application of games to the completeness problem for formalized theories
• Unbounded program memory adds to the expressive power of first-order programming logic
• On Moschovakis closure ordinals
• Deux ou trois choses que je sais de L_n
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Definability with bounded number of bound variables