𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Rudimentary Languages and Second-Order Logic

✍ Scribed by Malika More; Frédéric Olive

Publisher
John Wiley and Sons
Year
1997
Tongue
English
Weight
446 KB
Volume
43
Category
Article
ISSN
0044-3050

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The aim of this paper is to point out the equivalence between three notions respectively issued from recursion theory, computational complexity and finite model theory. One the one hand, the rudimentary languages are known to be characterized by the linear hierarchy. On the other hand, this complexity class can be proved to correspond to monadic second‐order logic with addition. Our viewpoint sheds some new light on the close connection between these domains: We bring together the two extremal notions by providing a direct logical characterization of rudimentary languages and a representation result of second‐order logic into these languages. We use natural arithmetical tools, and our proofs contain no ingredient from computational complexity.

📜 SIMILAR VOLUMES

α Logic and Infinitary Languages
α Logic and Infinitary Languages
✍ Newton C. A. da Costa; Charles C. Pinter 📂 Article 📅 1976 🏛 John Wiley and Sons 🌐 English ⚖ 490 KB
Characterizing Second Order Logic with F
Characterizing Second Order Logic with First Order Quantifiers
✍ David Harel 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 257 KB

CHARACTERIZING SECOND ORDER LOGIC WITH FIRST ORDER QU-4NTIFIERX by DAVID HAREL in Cambridge, Massachusets (U.S.A.) l) ') The author is indebted to W. J. WALKOE, A. R. MEYER, A. SHAMIR and a rcfeiee for comments on previous versions.

From finitary to infinitary second-order
From finitary to infinitary second-order logic
✍ George Weaver; Irena Penev 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 158 KB

## Abstract A back and forth condition on interpretations for those second‐order languages without functional variables whose non‐logical vocabulary is finite and excludes functional constants is presented. It is shown that this condition is necessary and sufficient for the interpretations to be eq

A secondary semantics for Second Order I
A secondary semantics for Second Order Intuitionistic Propositional Logic
✍ Mauro Ferrari; Camillo Fiorentini; Guido Fiorino 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 159 KB

## Abstract In this paper we propose a Kripke‐style semantics for second order intuitionistic propositional logic and we provide a semantical proof of the disjunction and the explicit definability property. Moreover, we provide a tableau calculus which is sound and complete with respect to such a s