Results 1 to 10 of about 1,546,334 (124)
A Denotational Semantics for First-Order Logic [PDF]
, 2000 In Apt and Bezem [AB99] (see cs.LO/9811017) we provided a computational interpretation of first-order formulas over arbitrary interpretations. Here we complement this work by introducing a denotational semantics for first-order logic.
Krzysztof R. Apt
openalex +7 more sources
The succinctness of first-order logic on linear orders [PDF]
, 2004 Succinctness is a natural measure for comparing the strength of different logics. Intuitively, a logic L_1 is more succinct than another logic L_2 if all properties that can be expressed in L_2 can be expressed in L_1 by formulas of (approximately) the ...
Martin Grohe, Nicole Schweikardt
openalex +6 more sources
Efficient First-Order Temporal Logic for Infinite-State Systems [PDF]
, 2007 In this paper we consider the specification and verification of infinite-state systems using temporal logic. In particular, we describe parameterised systems using a new variety of first-order temporal logic that is both powerful enough for this form of ...
Clare Dixon +3 more
openalex +5 more sources
Order-Invariant First-Order Logic over Hollow Trees [PDF]
, 2020 We show that the expressive power of order-invariant first-order logic collapses to first-order logic over hollow trees. A hollow tree is an unranked ordered tree where every non leaf node has at most four adjacent nodes: two siblings (left and right ...
Grange, Julien, Segoufin, Luc
core +3 more sources
Game semantics for first-order logic [PDF]
, 2010 We refine HO/N game semantics with an additional notion of pointer (mu-pointers) and extend it to first-order classical logic with completeness results.
Olivier Laurent +1 more
core +4 more sources
Separating Regular Languages with First-Order Logic [PDF]
, 2014 Given two languages, a separator is a third language that contains the first one and is disjoint from the second one. We investigate the following decision problem: given two regular input languages of finite words, decide whether there exists a first ...
Place, Thomas, Zeitoun, Marc
core +3 more sources
First-Order Logic Foundation of Relativity Theories [PDF]
, 2006 Motivation and perspective for an exciting new research direction interconnecting logic, spacetime theory, relativity--including such revolutionary areas as black hole physics, relativistic computers, new cosmology--are presented in this paper.
Madarasz, Judit X. +2 more
core +6 more sources
A definability theorem for first order logic [PDF]
, 1997 For any first order theory T we construct a Boolean valued model M, in which precisely the T--provable formulas hold, and in which every (Boolean valued) subset which is invariant under all automorphisms of M is definable by a first order formula.
Carsten Butz +3 more
core +8 more sources
Continuous first order logic and local stability [PDF]
, 2008 We develop continuous first order logic, a variant of the logic described in \cite{Chang-Keisler:ContinuousModelTheory}. We show that this logic has the same power of expression as the framework of open Hausdorff cats, and as such extends Henson's logic ...
Usvyatsov, Alexander, Yaacov, Itaï Ben
core +5 more sources
A first-order logic for string diagrams [PDF]
, 2015 Equational reasoning with string diagrams provides an intuitive means of proving equations between morphisms in a symmetric monoidal category. This can be extended to proofs of infinite families of equations using a simple graphical syntax called !-box ...
Kissinger, Aleks, Quick, David
core +2 more sources