✦ LIBER ✦

Arity and alternation in second-order logic

✍ Scribed by J.A. Makowsky; Y.B. Pnueli

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 844 KB
Volume: 78
Category: Article
ISSN: 0168-0072
DOI: 10.1016/0168-0072(95)00013-5

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Ann. Pure Appl. Logic: Erratum to “Arity

Ann. Pure Appl. Logic: Erratum to “Arity and alternation in second-order logic” 78 (1996) 189–202

📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 52 KB

Unfortunately the paper contains three minor inaccuracies, none of which zlo u$k,v the main results. \* The result wrongly attributed in the proof of Proposition 2 to Ajtai and Fagin [l], is due to R. Fagin in Monadic generalized spectra, Zeitschrift tiir Mathematische Logik and Grundlagen der Mathe

Rudimentary Languages and Second-Order L

Rudimentary Languages and Second-Order Logic

✍ Malika More; Frédéric Olive 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 446 KB

## 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,

Reduction of second-order logic to modal

Reduction of second-order logic to modal logic

✍ S. K. Thomason 📂 Article 📅 1975 🏛 John Wiley and Sons 🌐 English ⚖ 464 KB

Circle graphs and monadic second-order l

Circle graphs and monadic second-order logic

✍ Bruno Courcelle 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 357 KB

This article is part of a project consisting in expressing, whenever possible, graph properties and graph transformations in monadic second-order logic or in its extensions using modulo p cardinality set predicates or auxiliary linear orders. A circle graph is the intersection graph of a set of chor

Monadic Second Order Logic And Its Fragm

Monadic Second Order Logic And Its Fragments

✍ Giacomo Lenzi 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 230 KB

Various recent results about monadic second order logic and its fragments are presented. These results have been obtained in the framework of the EU TMR Project GETGRATS.

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.