The Settling Time Reducibility Ordering and {Delta}Formula Sets

The settling time reducibility ordering gives an ordering oncomputably enumerable sets based on their enumerations. The<_st ordering is in fact an ordering on c.e. sets, since itis independent of the particular enumeration chosen. In thisarticle, we show that it is not possible to extend this orderingin an approximation-independent way to sets in general, or even to n-c.e. sets for anyfixed n 3.     

Computability in Specification

In reference (Foundation of specification. Journal of Logicand Computation, 15, 951–974, 2005), the author introducesa core specification theory (CST) in order to provide a logicalframework for the design and exploration of specification languages.In this article, we formulate two highly expressive extensionsof CST. The first (CST_U) is CST + a universe of types and thesecond (CST_US) permits specifications themselves to be dataitems. Finally, we shall explore their metamathematical propertiesand, in particular, provide an interpretation into first-orderarithmetic.     

Complexity Issues in Axiomatic Extensions of Lukasiewicz Logic

In this article, the computational complexity of all axiomaticextensions of ukasiewicz propositional logic and the arithmeticalcomplexity of both the general and standard semantics of theircorresponding predicate logics is determined.     

On Non-axiomatizability of Superintuitionistic Predicate Logics of Some Classes of Well-founded and Dually Well-founded Kripke Frames

The article presents general results on non-axiomatizabilityfor superintuitionistic predicate logics. In particular, thelogics of all well-ordered, all dually well-ordered, and alldually well-founded Kripke frames (in the semantics with nestedand with constant domains) are -hard, and the logic of all Kripke frames of finite heightis not recursively axiomatizable (although it is known to be -arithmetical). A resulton Kripke-incompleteness is stated as well.     

Relativized Degree Spectra

We present a relativized version of the notion of a degree spectrumof a structure with respect to finitely many abstract structures.We study the connection to the notion of joint spectrum. Weprove that some properties of the degree spectrum as a minimalpair theorem and the existence of quasi-minimal degrees aretrue for the relative spectrum.