Definable relations in Turing degree structures

In this paper we investigate questions about the definability of classes of n-computably enumerable (c. e.) sets and degrees in the Ershov difference hierarchy. It is proved that the class of all c. e. sets is definable under the set inclusion ? in all finite levels of the difference hierarchy. It is also proved the definability of all m-c. e. degrees in each higher level of the hierarchy. Besides, for each level n, n ≥ 2, of the hierarchy a definable non-trivial subset of n-c. e. degrees is established.     

Bounded query classes and the difference hierarchy

LetA be any nonrecursive set. We define a hierarchy of sets (and a corresponding hierarchy of degrees) that are reducible toA based on bounding the number of queries toA that an oracle machine can make. WhenA is the halting problemK our hierarchy of sets interleaves with the difference hierarchy on the r.e. sets in a logarithmic way; this follows from a tradeoff between the number of parallel queries and the number of serial queries needed to compute a function with oracleK.Supported in part by NSF grant CCR-8808949. Part of this work was completed while this author was a student at Stanford University supported by fellowships from the National Science Foundation and from the Fannie and John Hertz FoundationSupported in part by NSF grant CCR-8803641Part of this work was completed while this author was on sabbatical leave at the University of California, Berkeley     

Complexity of fuzzy answer set programming under Łukasiewicz semantics

Fuzzy answer set programming (FASP) is a generalization of answer set programming (ASP) in which propositions are allowed to be graded. Little is known about the computational complexity of FASP and almost no techniques are available to compute the answer sets of a FASP program. In this paper, we analyze the computational complexity of FASP under Łukasiewicz semantics. In particular we show that the complexity of the main reasoning tasks is located at the first level of the polynomial hierarchy, even for disjunctive FASP programs for which reasoning is classically located at the second level. Moreover, we show a reduction from reasoning with such FASP programs to bilevel linear programming, thus opening the door to practical applications. For definite FASP programs we can show P-membership. Surprisingly, when allowing disjunctions to occur in the body of rules – a syntactic generalization which does not affect the expressivity of ASP in the classical case – the picture changes drastically. In particular, reasoning tasks are then located at the second level of the polynomial hierarchy, while for simple FASP programs, we can only show that the unique answer set can be found in pseudo-polynomial time. Moreover, the connection to an existing open problem about integer equations suggests that the problem of fully characterizing the complexity of FASP in this more general setting is not likely to have an easy solution.     

Addition and multiplication of sets

Ordinal addition and multiplication can be extended in a natural way to all sets. I survey the structure of the sets under these operations. In particular, the natural partial ordering associated with addition of sets is shown to be a tree. This allows us to prove that any set has a unique representation as a sum of additively irreducible sets, and that the non-empty elements of any model of set theory can be partitioned into infinitely many submodels, each isomorphic to the original model. Also any model of set theory has an isomorphic extension in which the empty set of the original model is non-empty. Among other results, the relations between the arithmetical operations and the transitive closure and the adductive hierarchy are elucidated. (© 2007 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

The enumeration spectrum hierarchy of n‐families

We introduce a hierarchy of sets which can be derived from the integers using countable collections. Such families can be coded into countable algebraic structures preserving their algorithmic properties. We prove that for different finite levels of the hierarchy the corresponding algebraic structures have different classes of possible degree spectra.     

The Hausdorff-Ershov Hierarchy in Euclidean Spaces

The topological arithmetical hierarchy is the effective version of the Borel hierarchy. Its class Δ^ta₂ is just large enough to include several types of pointsets in Euclidean spaces ℝ^k which are fundamental in computable analysis. As a crossbreed of Hausdorff's difference hierarchy in the Borel class Δ^B₂ and Ershov's hierarchy in the class Δ⁰₂ of the arithmetical hierarchy, the Hausdorff-Ershov hierarchy introduced in this paper gives a powerful classification within Δ^ta₂. This is based on suitable characterizations of the sets from Δ^ta₂ which are obtained in a close analogy to those of the Δ^B₂ sets as well as those of the Δ⁰₂ sets. A helpful tool in dealing with resolvable sets is contributed by the technique of depth analysis. On this basis, the hierarchy properties, in particular the strict inclusions between classes of different levels, can be shown by direct constructions of witness sets. The Hausdorff-Ershov hierarchy runs properly over all constructive ordinals, in contrast to Ershov's hierarchy whose denotation-independent version collapses at level ω². Also, some new characterizations of concepts of decidability for pointsets in Euclidean spaces are presented.     

A note on DOL length sets

Length sets of polynomially bounded DOL systems are considered by analyzing sets K ∩ {n : n ? q} where K is a DOL length set. It turns out that DOL and PDOL systems behave in different ways with respect to these sets. Especially, it follows that all DOL length sets— contrary to PDOL length sets—are not generated unambiguously, i.e. without repetitions, by DOL systems. Moreover it is proved that the number of axioms used determines an infinite hierarchy of length set families both in DOL and PDOL case.     

Prolegomenon to the relation between social theory and method*

Building on the work of Noam Chomsky (1963), this paper presents a hierarchy of grammars and associated computational automata in order to inform social theory construction and method. A detailed exposition of linguistic forms within the grammar hierarchy reveals clear analogues with common social scientific paradigms. Two of these paradigms (which are termed structural and process approaches) are already being widely exploited by formal methodological techniques. A third paradigm, which is rooted in a tradition of interpretive sociology, has been more resistant to formalization. Using arguments from theoretical computer science, the paper suggests that existing quantitative methodologies can be extended to accommodate qualitative arguments which subsume empirical domains as diverse as natural language and structurational phenomena.     

On existence of complete sets for bounded reducibilities

Classical reducibilities have complete sets U that any recursively enumerable set can be reduced to U. This paper investigates existence of complete sets for reducibilities with limited oracle access. Three characteristics of classical complete sets are selected and a natural hierarchy of the bounds on oracle access is built. As the bounds become stricter, complete sets lose certain characteristics and eventually vanish. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Denotational semantics for intuitionistic type theory using a hierarchy of domains with totality

A modified version of Normann's hierarchy of domains with totality [9] is presented and is shown to be suitable for interpretation of Martin-L?f's intuitionistic type theory. This gives an interpretation within classical set theory, which is natural in the sense that -types are interpreted as sets of pairs and -types as sets of choice functions. The hierarchy admits a natural definition of the total objects in the domains, and following an idea of Berger [3] this makes possible an interpretation where a type is defined to be true if its interpretation contains a total object. In particular, the empty type contains no total objects and will therefore be false (in any non-empty context). In addition, there is a natural equivalence relation on the total objects, so we derive a hierarchy of topological spaces (quotient spaces wrt. the Scott topology), and give a second interpretation using this hierarchy. Received: 11 December 1995 / Revised version: 14 October 1996     

Optimality Conditions and Geometric Properties of a Linear Multilevel Programming Problem with Dominated Objective Functions

In this paper, a model of a linear multilevel programming problem with dominated objective functions (LMPPD(l)) is proposed, where multiple reactions of the lower levels do not lead to any uncertainty in the upper-level decision making. Under the assumption that the constrained set is nonempty and bounded, a necessary optimality condition is obtained. Two types of geometric properties of the solution sets are studied. It is demonstrated that the feasible set of LMPPD(l) is neither necessarily composed of faces of the constrained set nor necessarily connected. These properties are different from the existing theoretical results for linear multilevel programming problems.     

Simultaneously non-convergent frequencies of words in different expansions

We consider expanding maps such that the unit interval can be represented as a full symbolic shift space with bounded distortion. There are already theorems about the Hausdorff dimension for sets defined by the set of accumulation points for the frequencies of words in one symbolic space at a time. We show that the dimension is preserved when such sets defined using different maps are intersected. More precisely, it is proven that the dimension of any countable intersection of sets defined by their sets of accumulation for frequencies of words in different expansions, has dimension equal to the infimum of the dimensions of the sets that are intersected. As a consequence, the set of numbers for which the frequencies do not exist has full dimension even after countable intersections. We also prove that this holds for a dense set of non-integer base expansions.     

Multiblock latent root regression. Application to epidemiological data

Several papers have already stressed the interest of latent root regression and its similarities to partial least squares regression. A new formulation of this method which makes it even simpler than the original method to set up a prediction model is discussed. Furthermore, it is shown how this method can be extended not only to the case where it is desired to predict several response variables from a set of predictors but also to the multiblock setting where the aim is to predict one or several data sets from several other data sets. The interest of the method is illustrated on the basis of a data set pertaining to epidemiology.     

Similarity,inclusion and entropy measures between type-2 fuzzy sets based on the Sugeno integral

Similarity measures of type-2 fuzzy sets are used to indicate the similarity degree between type-2 fuzzy sets. Inclusion measures for type-2 fuzzy sets are the degrees to which a type-2 fuzzy set is a subset of another type-2 fuzzy set. The entropy of type-2 fuzzy sets is the measure of fuzziness between type-2 fuzzy sets. Although several similarity, inclusion and entropy measures for type-2 fuzzy sets have been proposed in the literatures, no one has considered the use of the Sugeno integral to define those for type-2 fuzzy sets. In this paper, new similarity, inclusion and entropy measure formulas between type-2 fuzzy sets based on the Sugeno integral are proposed. Several examples are used to present the calculation and to compare these proposed measures with several existing methods for type-2 fuzzy sets. Numerical results show that the proposed measures are more reasonable than existing measures. On the other hand, measuring the similarity between type-2 fuzzy sets is important in clustering for type-2 fuzzy data. We finally use the proposed similarity measure with a robust clustering method for clustering the patterns of type-2 fuzzy sets.     

Asymptotic enumeration of full graphs

A full graph on n vertices, as defined by Fulkerson, is a representation of the intersection and containment relations among a system of n sets. It has an undirected edge between vertices representing intersecting sets, and a directed edge from a to b if the corresponding set A contaisn B. We give a unified argument to show that asymptotically, almost all full graphs can be obtained by taking an arbitrary undirected graph in the n vertices, distinguishing a clique in this graph that need not be maximal, and then adding directed edges going out from each vertex in the clique to all vertices to which there is not already an existing undirected edge. © 1996 John Wiley & Sons, Inc.     

On Genericity and Ershov's Hierarchy

It is natural to wish to study miniaturisations of Cohen forcing suitable to sets of low arithmetic complexity. We consider extensions of the work of Schaeffer [9] and Jockusch and Posner [6] by looking at genericity notions within the Δ₂ sets. Different equivalent characterisations of 1‐genericity suggest different ways in which the definition might be generalised. There are two natural ways of casting the notion of 1‐genericity: in terms of sets of strings and in terms of density functions, as we will see here. While these definitions coincide at the first level of the difference hierarchy, they turn out to differ at other levels. Furthermore, these differences remain when the remainder of the Δ⁰₂ sets are considered. While the string characterization of 1‐genericity collapses at the second level of the difference hierarchy to 2‐genericity, the density function definition gives a very interesting hierarchy at level w and above. Both of these results point towards the deep similarities exhibited by the n‐c.e. degrees for n ≥ 2.     

Refined hierarchy of formulas

In this paper a hierarchy of predicate logic which refines the hierarchy by the number of quantor alterations is introduced and studied. Theorem 1 shows that the hierarchy constructed is the most refined in a certain sense. Theorem 2 describes hierarchy classes in terms of properties of the corresponding models. In Theorems 3 and 4, the connection between the hierarchy of formulas and the hierarchy of sets presented in [1] and the index sets is studied.Translated from Algebra i Logika, Vol. 30, No. 5, pp. 568–582, September–October, 1991.     

A cumulative hierarchy of sets for constructive set theory

The von Neumann hierarchy of sets is heavily used as a basic tool in classical set theory, being an underlying ingredient in many proofs and concepts. In constructive set theories like without the powerset axiom however, it loses much of its potency by ceasing to be a hierarchy of sets as its single stages become only classes. This article proposes an alternative cumulative hierarchy which does not have this drawback and provides examples of how it can be used to prove new theorems in .