Results 11 to 20 of about 2,834 (69)
Computabilities of Validity and Satisfiability in Probability Logics over Finite and Countable Models [PDF]
, 2014 The $\epsilon$-logic (which is called $\epsilon$E-logic in this paper) of Kuyper and Terwijn is a variant of first order logic with the same syntax, in which the models are equipped with probability measures and in which the $\forall x$ quantifier is ...
Yang, Greg
core +1 more source
Complete Additivity and Modal Incompleteness [PDF]
, 2019 In this paper, we tell a story about incompleteness in modal logic. The story weaves together a paper of van Benthem, `Syntactic aspects of modal incompleteness theorems,' and a longstanding open question: whether every normal modal logic can be ...
Holliday, Wesley H., Litak, Tadeusz
core +2 more sources
(Un)Decidability Results for Word Equations with Length and Regular Expression Constraints [PDF]
, 2013 We prove several decidability and undecidability results for the satisfiability and validity problems for languages that can express solutions to word equations with length constraints.
Ganesh, Vijay +3 more
core
First Order Theories of Some Lattices of Open Sets
, 2017 We show that the first order theory of the lattice of open sets in some natural topological spaces is $m$-equivalent to second order arithmetic. We also show that for many natural computable metric spaces and computable domains the first order theory of ...
Kudinov, Oleg, Selivanov, Victor
core +1 more source
On Descriptive Complexity, Language Complexity, and GB [PDF]
, 1995 We introduce $L^2_{K,P}$, a monadic second-order language for reasoning about trees which characterizes the strongly Context-Free Languages in the sense that a set of finite trees is definable in $L^2_{K,P}$ iff it is (modulo a projection) a Local Set ...
Rogers, James
core +3 more sources
Monadic Second-Order Logic with Arbitrary Monadic Predicates
, 2017 We study Monadic Second-Order Logic (MSO) over finite words, extended with (non-uniform arbitrary) monadic predicates. We show that it defines a class of languages that has algebraic, automata-theoretic and machine-independent characterizations.
Fijalkow, Nathanaël, Paperman, Charles
core +3 more sources
A semantical framework for hybrid knowledge bases [PDF]
, 2010 In the ongoing discussion about combining rules and ontologies on the Semantic Web a recurring issue is how to combine first-order classical logic with nonmonotonic rule languages.
Bruijn, Jos de +3 more
core +2 more sources
The Church Problem for Countable Ordinals
, 2009 A fundamental theorem of Buchi and Landweber shows that the Church synthesis problem is computable. Buchi and Landweber reduced the Church Problem to problems about ω-games and used the determinacy of such games as one of the main tools to show its ...
Rabinovich, Alexander
core +1 more source
The First-Order Theory of Sets with Cardinality Constraints is Decidable
, 2004 We show that the decidability of the first-order theory of the language that combines Boolean algebras of sets of uninterpreted elements with Presburger arithmetic operations. We thereby disprove a recent conjecture that this theory is undecidable.
Kuncak, Viktor, Rinard, Martin
core +3 more sources
Some Concerns Regarding Ternary-relation Semantics and Truth-theoretic Semantics in General [PDF]
, 2017 This paper deals with a collection of concerns that, over a period of time, led the author away from the Routley–Meyer semantics, and towards proof- theoretic approaches to relevant logics, and indeed to the weak relevant logic MC of meaning ...
Brady, Ross T.
core