Studia Logica 72 (2):147-156 (2002)

It has been shown recently that monodic first-order temporal logic without functional symbols but with equality is incomplete, i.e., the set of the valid formulae of this logic is not recursively enumerable. In this paper we show that an even simpler fragment consisting of monodic monadic two-variable formulae is not recursively enumerable.
Keywords Philosophy   Logic   Mathematical Logic and Foundations   Computational Linguistics
Categories (categorize this paper)
Reprint years 2004
DOI 10.1023/A:1021352309671
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 58,518
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

Complexity of Monodic Guarded Fragments Over Linear and Real Time.Ian Hodkinson - 2006 - Annals of Pure and Applied Logic 138 (1):94-125.
Linear-Time Temporal Logics with Presburger Constraints: An Overview ★.Stéphane Demri - 2006 - Journal of Applied Non-Classical Logics 16 (3-4):311-347.

View all 6 citations / Add more citations

Similar books and articles


Added to PP index

Total views
126 ( #79,251 of 2,421,925 )

Recent downloads (6 months)
2 ( #352,488 of 2,421,925 )

How can I increase my downloads?


My notes