Subrecursive functions on partial sequences

The paper studies a domain theoretical notion of primitive recursion over partial sequences in the context of Scott domains. Based on a non-monotone coding of partial sequences, this notion supports a rich concept of parallelism in the sense of Plotkin. The complexity of these functions is analysed by a hierarchy of classes similar to the Grzegorczyk classes. The functions considered are characterised by a function algebra generated by continuity preserving operations starting from computable initial functions. Its layers are related to those above by showing , thus generalising results of Schwichtenberg/Müller and Niggl. Received: 18 November 1996     

Subrecursive degrees and fragments of Peano Arithmetic

Let T ₀?T ₁ denote that each computable function, which is provable total in the first order theory T ₀, is also provable total in the first order theory T ₁. Te relation ? induces a degree structure on the sound finite Π₂ extensions of EA (Elementary Arithmetic). This paper is devoted to the study of this structure. However we do not study the structure directly. Rather we define an isomorphic subrecursive degree structure <≤,?>, and then we study <≤,?> by ubrecursive and computability-theoretic means. Furthermore, we introduce and investigate some operators on the degrees of <≤,?>. These operators corresponds to inferencerules in formal arithmetic. One operator corresponds to the Σ₁ collection rule. Another operator corresponds to the Σ₁ induction rule.     

A restricted computation model on Scott domains and its partial primitive recursive functionals

The paper builds on both a simply typed term system and a computation model on Scott domains via so-called parallel typed while programs (PTWP). The former provides a notion of partial primitive recursive functional on Scott domains supporting a suitable concept of parallelism. Computability on Scott domains seems to entail that Kleene's schema of higher type simultaneous course-of-values recursion (scvr) is not reducible to partial primitive recursion. So extensions and PTWP are studied that are closed under scvr. The twist are certain type 1 G?del recursors for simultaneous partial primitive recursion. Formally, denotes a function , however, is modelled such that is finite, or in other words, a partial sequence. As for PTWP, the concept of type writable variables is introduced, providing the possibility of creating and manipulating partial sequences. It is shown that the PTWP-computable functionals coincide with those definable in plus a constant for sequential minimisation. In particular, the functionals definable in denoted can be characterised by a subclass of PTWP-computable functionals denoted . Moreover, hierarchies of strictly increasing classes in the style of Heinermann and complexity classes are introduced such that . These results extend those for and PTWP [Nig94]. Finally, scvr is employed to define for each type the enumeration functional of all finite elements of . Received January 30, 1996     

Isomorphisms,definable relations,and Scott families for integral domains and commutative semigroups

In the present article, we prove the following four assertions: (1) For every computable successor ordinal α, there exists a Δ _α ⁰ -categorical integral domain (commutative semigroup) which is not relatively Δ _α ⁰ -categorical (i.e., no formally Σ _α ⁰ Scott family exists for such a structure). (2) For every computable successor ordinal α, there exists an intrinsically Σ _α ⁰ -relation on the universe of a computable integral domain (commutative semigroup) which is not a relatively intrinsically Σ _α ⁰ -relation. (3) For every computable successor ordinal α and finite n, there exists an integral domain (commutative semigroup) whose Δ _α ⁰ -dimension is equal to n. (4) For every computable successor ordinal α, there exists an integral domain (commutative semigroup) with presentations only in the degrees of sets X such that Δ _α ⁰ (X) is not Δ _α ⁰ . In particular, for every finite n, there exists an integral domain (commutative semigroup) with presentations only in the degrees that are not n-low.     

Pulsating hierarchies

The research was supported by the Russian Foundation for Fundamental Research (Grant 93-011-16014).     

偏序集中网和滤子的Scott收敛及其Scott拓扑

本文的目的是在偏序集上直接定义和研究网和滤子的Scott收敛理论,指出其相互之间的协调性,及其它们的导出拓扑与Scott拓扑的一致性.     

Wilson's theorem for consensus functions on hierarchies

Wilson in 1972 gave a generalization of Arrow's theorem without the Pareto axiom. We prove a version of Wilson's theorem for consensus functions on hierarchies.     

模糊dcpo上的L-模糊Scott余拓

研究模糊dcpo上的L-模糊Scott余拓扑(即关于L-模糊集成为Scott闭集的程度映射)和L-Scott余拓扑(即全体L-Scott闭集构成的余拓扑),考察它们的特殊化L-序及其与模糊Scott连续映射的关系.     

From hierarchies to well-foundedness

We highlight that the connection of well-foundedness and recursive definitions is more than just convenience. While the consequences of making well-foundedness a sufficient condition for the existence of hierarchies (of various complexity) have been extensively studied, we point out that (if parameters are allowed) well-foundedness is a necessary condition for the existence of hierarchies e.g. that even in an intuitionistic setting \({(\Pi_1^0-\mathsf{CA}_0)_\alpha \vdash \mathsf{wf}(\alpha)\, {\rm where}\, (\Pi_1^0-\mathsf{CA}_0)_\alpha}\) stands for the iteration of \({\Pi^0_1}\) comprehension (with parameters) along some ordinal \({\alpha}\) and \({\mathsf{wf}(\alpha)}\) stands for the well-foundedness of \({\alpha}\) .     

A note on the generalized symmetries of lattice hierarchies

We show that the recursion operators of the integrable lattice equations usually considered in the literature can also be used to generate hierarchies of differential-delay equations. All members of these hierarchies of lattice and differential-delay equations commute. It is thus seen that differential-delay hierarchies provide a broader context within which to place lattice hierarchies.     

Commutator identities and integrable hierarchies

Theoretical and Mathematical Physics - The approach based on commutator identities for elements of associative algebras was previously effectively used to investigate $$(2{+}1)$$ -dimensional...     

Nested hierarchies in planar graphs

We construct a partial order relation which acts on the set of 3-cliques of a maximal planar graph G and defines a unique hierarchy. We demonstrate that G is the union of a set of special subgraphs, named ‘bubbles’, that are themselves maximal planar graphs. The graph G is retrieved by connecting these bubbles in a tree structure where neighboring bubbles are joined together by a 3-clique. Bubbles naturally provide the subdivision of G into communities and the tree structure defines the hierarchical relations between these communities.     

Set partitions and integrable hierarchies

We demonstrate that statistics for several types of set partitions are described by generating functions arising in the theory of integrable equations.     

Decision-making by hierarchies of discordant agents

We study the following decision-making scenario: A linear program is solved by a set of agents arranged hierarchically in a tree, where each agent decides the level of certain variables, and has a distinct objective function, known to all agents. Authority is reflected in two ways: Agents higher in the tree set their variables first; and agents that are siblings in the tree resolve their game by focusing on the Nash equilibrium that is optimum for the agent above them. We give a necessary and sufficient condition for such a hierarchy to be efficient (i.e., to have perfect coordination, to ultimately optimize the objective of the firm). We study problems related to designing a hierarchy (assigning decision makers to positions in the tree) in order to achieve efficiency or otherwise optimize coordination. Received June 16, 1997 / Revised version received July 8, 1998?Published online May 12, 1999     

Vectorization hierarchies of some graph quantifiers

We give a sufficient condition for the inexpressibility of the k-th extended vectorization of a generalized quantifier in , the extension of first-order logic by all k-ary quantifiers. The condition is based on a model construction which, given two -equivalent models with certain additional structure, yields a pair of -equivalent models. We also consider some applications of this condition to quantifiers that correspond to graph properties, such as connectivity and planarity. Received: 15 October 1996