bluuebunny/crossref_metadata_2025 huggingface dataset:
Some results on polarized partion relations of higher dimension
Authors: Carnielli Walter Alexandre , Di Prisco Carlos Augusto
Published: May 2007

Several types of polarized partition relations are considered. In particular we deal with partitions defined on cartesian products of more than two factors. MSC: 03E05.
Highness and bounding minimal pairs
Authors: Downey Rodney G. , Lempp Steffen , Shore Richard A.
Published: May 2007

We show the existence of a high r. e. degree bounding only joins of minimal pairs and of a high2 nonbounding r. e. degree. MSC: 03D25.
On the predecessor relation in abstract algebras
Authors: Diener Karl‐Heinz
Published: May 2007

In this paper we generalize the Dedekind theory of order for the natural numbers N to abstract algebras with arbitrarily many finitary or infinitary operations. For any algebra 𝔜, we introduce an algebraic predecessor relation P𝔜 and its transitive hull P*𝔜 coinciding in N with the unary injective successor function' resp. the >‐relation. For some important classes of algebras 𝔜, including Peano algebras (absolutely free algebras, word algebras), the algebraic predecessor relation is well‐founded. Hence, its transitive hull, the natural ordering >𝔜 of 𝔜, is a well‐founded partial order, which turns out to be a convenient device for classifying Peano algebras with respect to the number of operations and their arities. Moreover, the property of well‐foundedness is an efficient tool for giving simple proofs of structure theorems as, e. g., that the class of all Peano algebras is closed under subalgebras and non‐void direct products. ‐ Finally, we will show how in the case of a formal language ℒ︁, i. e., the Peano algebra ℒ︁ of expressions (= terms & formulas), relations Pℒ︁, resp. P*ℒ︁ can be used to define basic syntactical notions as occurences of free and bound variables etc. without any reference to a particular representation (“coding”) of the formal language. MSC: 03B22, 03E30, 03E75, 03F35, 08A55, 08B20.
A cohesive set which is not high
Authors: Jockusch Carl , Stephan Frank
Published: May 2007

We study the degrees of unsolvability of sets which are cohesive (or have weaker recursion‐theoretic “smallness” properties). We answer a question raised by the first author in 1972 by showing that there is a cohesive set A whose degree a satisfies a' = 0″ and hence is not high. We characterize the jumps of the degrees of r‐cohesive sets, and we show that the degrees of r‐cohesive sets coincide with those of the cohesive sets. We obtain analogous results for strongly hyperimmune and strongly hyperhyperimmune sets in place of r‐cohesive and cohesive sets, respectively. We show that every strongly hyperimmune set whose degree contains either a Boolean combination of ∑2 sets or a 1‐generic set is of high degree. We also study primitive recursive analogues of these notions and in this case we characterize the corresponding degrees exactly. MSC: 03D30, 03D55.
On the structure of kripke models of heyting arithmetic
Authors: Marković Zoran
Published: May 2007

Since in Heyting Arithmetic (HA) all atomic formulas are decidable, a Kripke model for HA may be regarded classically as a collection of classical structures for the language of arithmetic, partially ordered by the submodel relation. The obvious question is then: are these classical structures models of Peano Arithmetic (PA)? And dually: if a collection of models of PA, partially ordered by the submodel relation, is regarded as a Kripke model, is it a model of HA? Some partial answers to these questions were obtained in [6], [3], [1] and [2]. Here we present some results in the same direction, announced in [7]. In particular, it is proved that the classical structures at the nodes of a Kripke model of HA must be models of IΔ1 (PA‐ with induction for provably Δ1 formulas) and that the relation between these classical structures must be that of a Δ1‐elementary submodel. MSC: 03F30, 03F55.
A proof of the normal form theorem for the closed terms of Girard's system F by means of computability
Authors: Valentini Silvio
Published: May 2007

In this paper a proof of the normal form theorem for the closed terms of Girard's system F is given by using a computability method à la Tait. It is worth noting that most of the standard consequences of the normal form theorem can be obtained using this version of the theorem as well. From the proof‐theoretical point of view the interest of the proof is that the definition of computable derivation here used does not seem to be well founded. MSC: 03F05, 03B15.
ω‐operations over partial enumerated sets
Authors: Orlicki Andrzej
Published: May 2007

In the present paper we concentrate on fundamental problems concerning ω‐operations over partial enumerated sets. The notion of “HOM‐lifts” seems to be an adequate tool for this kind of investigations. MSC: 03D45, 18A30.
Finitary algebraic logic II
Authors: Maddux Roger D.
Published: May 2007

This is a supplement to the paper “Finitary Algebraic Logic” [1]. It includes corrections for several errors and some additional results. MSC: 03G15, 03G25.
Automorphisms of Models of True Arithmetic: Subgroups which Extend to a Maximal Subgroup Uniquely
Authors: Kotlarski Henryk , Piekart Bożena
Published: May 2007

We show that ifMis a countable recursively saturated model of True Arithmetic, thenG= Aut(M) has nonmaximal open subgroups with unique extension to a maximal subgroup of Aut(M).

Mathematics Subject Classification:03C62, 03C50.
Universal Induction and True Universal Arithmetic
Authors: Bigorajska Teresa
Published: May 2007

We prove that every finitely generated (as a ring) model for induction for universal formulas without parameters satisfies also all true universal sentences.

Mathematics Subject Classification: 03C62.
A New Reducibility between Turing‐ and wtt‐Reducibility
Authors: Yuefei Sui
Published: May 2007

A new reducibility between Turing and weak truth‐table reducibility is defined, which gives an affirmative answer to the open question about the existence of such an intermediate reducibility proposed formally by M. Stob.

Mathematics Subject Classification: 03D25.
Some Aspects and Examples of Infinity Notions
Authors: Degen J. W.
Published: May 2007

Our main contribution is a formal definition of what could be called a T‐notion of infinity, for set theories T extending ZF. Around this definition we organize some old and new notions of infinity; we also indicate some easy independence proofs.

Mathematics Subject Classification: 03E25, 03E20.
Abelian‐by‐G Groups, for G Finite, from the Model Theoretic Point of View
Authors: Marcja Annalisa , Toffalori Carlo
Published: May 2007

Let G be a finite group. We prove that the theory af abelian‐by‐G groups is decidable if and only if the theory of modules over the group ring ℤ[G] is decidable. Then we study some model theoretic questions about abelian‐by‐G groups, in particular we show that their class is elementary when the order of G is squarefree.

Mathematics Subject Classification: 03C60, 03B25.
Monotonicity and the Expressibility of NP Operators
Authors: Stewart Iain A.
Published: May 2007

We investigate why similar extensions of first‐order logic using operators (that is, generalized quantifiers) corresponding to NP‐complete decision problems apparently differ in expressibility: the logics capture either NP or LNP. It had been conjectured that the complexity class captured is NP if and only if the operator is monotone. We show that this conjecture is false. However, we provide evidence supporting a revised conjecture involving finite variations of monotone problems.

Mathematics Subject Classification: 68Q15, 03D15, 03C13.
Model Companions with Finitely Many Countable Models
Authors: Burris Stanley
Published: May 2007

We present two conditions which are equivalent to having an almost χ0‐categorical model companion.

Mathematics Subject Classification: 03C35.
K‐generic Projective Planes have Morley Rank Two or Infinity
Authors: Baldwin John T. , Itai Masanori
Published: May 2007

We show that K‐generic projective planes have Morley rank either two or infinity. We also show give a direct argument that such planes are not Desarguesian.

Mathematics Subject Classification: 03C45, 05C90, 51A35.
Cut‐Elimination Theorem for the Logic of Constant Domains
Authors: Kashima Ryo , Shimura Tatsuya
Published: May 2007

The logic CD is an intermediate logic (stronger than intuitionistic logic and weaker than classical logic) which exactly corresponds to the Kripke models with constant domains. It is known that the logic CD has a Gentzen‐type formulation called LD (which is same as LK except that (→) and (⊃–) rules are replaced by the corresponding intuitionistic rules) and that the cut‐elimination theorem does not hold for LD. In this paper we present a modification of LD and prove the cut‐elimination theorem for it. Moreover we prove a “weak” version of cut‐elimination theorem for LD, saying that all “cuts” except some special forms can be eliminated from a proof in LD. From these cut‐elimination theorems we obtain some corollaries on syntactical properties of CD: fragments collapsing into intuitionistic logic. Harrop disjunction and existence properties, and a fact on the number of logical symbols in the axiom of CD.

Mathematics Subject Classification: 03B55. 03F05.
A Completeness Theorem for Certain Classes of Recursive Infinitary Formulas
Authors: Ash Christopher J. , Knight Julia F.
Published: May 2007

We consider the following generalization of the notion of a structure recursive relative to a set X. A relational structure A is said to be a Γ(X)‐structure if for each relation symbol R, the interpretation of R in A is ∑ relative to X, where β = Γ(R). We show that a certain, fairly obvious, description of classes ∑ of recursive infinitary formulas has the property that if A is a Γ(Ø)‐structure and S is a further relation on A, then the following are equivalent: (i) For every isomorphism F from A to a Γ(X)‐structure, F(S) is ∑ relative to X, (ii) The relation is defined in A by a ∑ formula with parameters.

Mathematics Subject Classification: 03D45, 03C57, 03C75.
Representation Theorems for Quantales
Authors: Valentini Silvio
Published: May 2007

In this paper we prove that any quantale Q is (isomorphic to) a quantale of suitable relations on Q. As a consequence two isomorphism theorems are also shown with suitable sets of functions of Q into Q. These theorems are the mathematical background one needs in order to give natural and complete semantics for (non‐commutative) Linear Logic using relations.

Mathematics Subject Classification: 06D05, 06D10, 06D20, 03G25.
The Elementary Classes of Direct and Boolean Products
Authors: Gluschankof Daniel
Published: May 2007

We characterize the elementary classes generated from a distinguished subclass closing by taking direct products and elementary equivalence. In the second part we give the same characterization in terms of atomic Boolean products. In the last part, we study the cases when the class of Boolean products is elementary but is not given by a discriminator.

Mathematics Subject Classification: 03C30, 08C10, 03C05, 03C60.
Recursiveness of ω‐Operations
Authors: Selivanov Victor L.
Published: May 2007

It is well known that any finitary operation is recursive in a suitable total numeration. A. Orlicki showed that there is an ω‐operation not recursive in any total numeration. We will show that any ω‐operation is recursive in a partial numeration.

Mathematics Subject Classification: 03D45.
Bounding and Dominating Number of Families of Functions on ω
Authors: Laflamme Claude
Published: May 2007

We pursue the study of families of functions on the natural numbers, with emphasis here on the bounded families. The situation being more complicated than the unbounded case, we attack the problem by classifying the families according to their bounding and dominating numbers, the traditional scheme for gaps. Many open questions remain.

Mathematics Subject Classification: 03E35, 04A20.
Effective Search Problems
Authors: Kummer Martin , Stephan Frank
Published: May 2007

The task of computing a function F with the help of an oracle X can be viewed as a search problem where the cost measure is the number of queries to X. We ask for the minimal number that can be achieved by a suitable choice of X and call this quantity the query complexity of F. This concept is suggested by earlier work of Beigel, Gasarch, Gill, and Owings on “Bounded query classes”. We introduce a fault tolerant version and relate it with Ulam's game. For many natural classes of functions F we obtain tight upper and lower bounds on the query complexity of F. Previous results like the Nonspeedup Theorem and the Cardinality Theorem appear in a wider perspective.

Mathematics Subject Classification: 03D20, 68Q15, 68R05.
Navigation Without Perception of Coordinates and Distances
Authors: Hemmerling Armin
Published: May 2007

We consider the target‐reaching problem in plane scenes for a point robot which has a tactile sensor and can locate the target ray. It might have a compass, too, but it is not able to perceive the coordinates of its position nor to measure distances. The complexity of an algorithm is measured by the number of straight moves until reaching the target, as a function of the number of vertices of the (polygonal) scene. It is shown how the target point can be reached by exhaustive search without using a compass, with the complexity exp(O(n2)). Using a compass, there is a target‐reaching algorithm, based on rotation counting, with the complexityO(n2). The decision problem, to recognize if the target cannot be reached because it belongs to an obstacle, cannot be solved by our type of robot. If the behaviour of a robot without compass is periodic in a homogeneous environment, it cannot solve the target‐reaching problem.

Mathematics Subject Classification:68Q20, 68U05, 03D15.
A Note on Relative Efficiency of Axiom Systems
Authors: Fontani Sandra , Montagna Franco , Sorbi Andrea
Published: May 2007

We introduce a notion of relative efficiency for axiom systems. Given an axiom system Aβ for a theory T consistent with S12, we show that the problem of deciding whether an axiom system Aα for the same theory is more efficient than Aβ is II2‐hard. Several possibilities of speed‐up of proofs are examined in relation to pairs of axiom systems Aα, Aβ, with Aα ⊇ Aβ, both in the case of Aα, Aβ having the same language, and in the case of the language of Aα extending that of Aβ: in the latter case, letting Prα, Prβ denote the theories axiomatized by Aα, Aβ, respectively, and assuming Prα to be a conservative extension of Prβ, we show that if Aα — Aβ contains no nonlogical axioms, then Aα can only be a linear speed‐up of Aβ; otherwise, given any recursive function g and any Aβ, there exists a finite extension Aα of Aβ such that Aα is a speed‐up of Aβ with respect to g.

Mathematics Subject Classification: 03F20, 03F30.
A Uniform Approach to Fundamental Sequences and Hierarchies
Authors: Buchholz Wilfried , Cichon Adam , Weiermann Andreas
Published: May 2007

In this article we give a unifying approach to the theory of fundamental sequences and their related Hardy hierarchies of number‐theoretic functions and we show the equivalence of the new approach with the classical one.

Mathematics Subject Classification: 03D20, 03F15, 03E10.
Discontinuity of Cappings in the Recursively Enumerable Degrees and Strongly Nonbranching Degrees
Authors: Ambos‐Spies Klaus , Decheng Ding
Published: May 2007

We construct an r. e. degree a which possesses a greatest a‐minimal pair b0, b1, i.e., r. e. degrees b0 and b1 such that b0, b1 < a, b0 ∩ b1 = a, and, for any other pair c0, c1 with these properties, c0 ≤ bi and c1 ≤ b1‐i for some i ≤ 1. By extending this result, we show that there are strongly nonbranching degrees which are not strongly noncappable. Finally, by introducing a new genericity concept for r. e. sets, we prove a jump theorem for the strongly nonbranching and strongly noncappable r. e. degrees.

Mathematics Subject Classification: 03D25.
Finite Homogeneous 3‐Graphs
Authors: Lachlan Alistair H. , Tripp Allyson
Published: May 2007

By “3‐graph” we mean a pair (V, E) such that E ⊆ [V]3. We show that the only non‐trivial finite 3‐graphs homogeneous in the sense of Fraïssé are those associated with the projective planes over GF(2) and GF(3), and with the projective lines over GF(5) and GF(9). To exclude other possibilities we use the classification of doubly transitive finite permutation groups.
On Some Complexity Characteristics of Immune Sets
Authors: Bulitko Valeriy K.
Published: May 2007

We suggest some new ways to effectivize the definitions of several classes of simple sets. On this basis, new completeness criterions for simple sets are obtained. In particular, we give descriptions of the class of complete maximal sets.
The Friedman‐Translation for Martin‐Löf's Type Theory
Authors: Palmgren Erik
Published: May 2007

In this note we show that Friedman's syntactic translation for intuitionistic logical systems can be carried over to Martin‐Löf's type theory, inlcuding universes provided some restrictions are made. Using this translation we show that the theory is closed under a higher type version of Markov's rule.
Almost Total Elementary Maps
Authors: Ikeda Koichiro , Tsuboi Akito
Published: May 2007

A partial map f of a structure M is called almost total if |M — dom(f)| = |M — ran(f)| < ω. We study a difference between an almost total elementary map and an automorphism.
Some Solved and Unsolved Remainder Equations
Authors: Hansson Sven Ove
Published: May 2007

The remainder set A⟂B of a set of sentences A modulo a set of sentences B is the set of all maximal subsets of A not implying any element of B. A remainder equation is an expression containing remainder sets, such as {A} = B⟂X, in which at least one set is unknown. Solutions to some classes of remainder equations are reported, and some unsolved problems are listed.
Loeb Measure from the Point of View of a Coin Flipping Game
Authors: Kanovei Vladimir , Reeken Michael
Published: May 2007

A hyperfinitely long coin flipping game between the Gambler and the Casino, associated with a given set A, is considered. It turns out that the Gambler has a winning strategy if and only if A has Loeb measure 0. The Casino has a winning strategy if and only if A contains an internal subset of positive Loeb measure.

Mathematics Subject Classification: 03H05, 03E15.
The Operators of Vector Logic
Authors: Mizraji Eduardo
Published: May 2007

Vector logic is a mathematical model of the propositional calculus in which the logical variables are represented by vectors and the logical operations by matrices. In this framework, many tautologies of classical logic are intrinsic identities between operators and, consequently, they are valid beyond the bivalued domain. The operators can be expressed as Kronecker polynomials. These polynomials allow us to show that many important tautologies of classical logic are generated from basic operators via the operations called Type I and Type II products. Finally, it is described a matrix version of the Fredkin gate that extends its properties to the many‐valued domain, and it is proved that the filtered Fredkin operators are second degree Kronecker polynomials that cannot be generated by Type I or Type II products.

Mathematics Subject Classification: 03B05, 03B50.
Decidability of ∀*∀‐Sentences in Membership Theories
Authors: Omodeo Eugenio G. , Parlamento Franco , Policriti Alberto
Published: May 2007

The problem is addressed of establishing the satisfiability of prenex formulas involving a single universal quantifier, in diversified axiomatic set theories. A rather general decision method for solving this problem is illustrated through the treatment of membership theories of increasing strength, ending with a subtheory of Zermelo‐Fraenkel which is already complete with respect to the ∀*∀ class of sentences. NP‐hardness and NP‐completeness results concerning the problems under study are achieved and a technique for restricting the universal quantifier is presented.

Mathematics Subject Classification: 03B25, 03E30.
The Recursively Mahlo Property in Second Order Arithmetic
Authors: Rathjen Michael
Published: May 2007

The paper characterizes the second order arithmetic theorems of a set theory that features a recursively Mahlo universe; thereby complementing prior proof‐theoretic investigations on this notion. It is shown that the property of being recursively Mahlo corresponds to a certain kind of β‐model reflection in second order arithmetic. Further, this leads to a characterization of the reals recursively computable in the superjump functional.

Mathematics Subject Classification: 03F35, 03F15, 03E70.
Remarks on Uniformly Finitely Precomplete Positive Equivalences
Authors: Yu. Shavrukov V.
Published: May 2007

The paper contains some observations on e‐complete, precomplete, and uniformly finitely precomplete r. e. equivalence relations. Among these are a construction of a uniformly finitely precomplete r. e. equivalence which is neither e‐ nor precomplete, an extension of Lachlan's theorem that all precomplete r. e. equivalences are isomorphic, and a characterization of sets of fixed points of endomorphisms of uniformly finitely precomplete r. e. equivalences.

Mathematics Subject Classification: 03D45.
The Isolated D. R. E. Degrees are Dense in the R. E. Degrees
Authors: Laforte Geoffrey
Published: May 2007

In the present paper we prove that the isolated differences of r. e. degrees are dense in the r. e. degrees.

Mathematics Subject Classification: 03D25.
Inconsistency of GPK + AFA
Authors: Esser Olivier
Published: May 2007

M. Forti and F. Honsell showed in [4] that the hyperuniverses defined in [2] satisfy the anti‐foundation axiom X1 introduced in [3]. So it is interesting to study the axiom AFA, which is equivalent to X1 in ZF, introduced by P. Aczel in [1]. We show in this paper that AFA is inconsistent with the theory GPK. This theory, which is first order, is defined by E. Weydert in [6] and later by M. Forti and R. Hinnion in [2]. It includes all general hyperuniverses as defined in [5]. In order to achieve our aim, we need to define ordinals in GPK and to study some of their properties.

Mathematics Subject Classification: 03E70, 03E10.
Intrinsically II Relations
Authors: Soskov Ivan N.
Published: May 2007

An external characterization of the inductive sets on countable abstract structures is presented. The main result is an abstract version of the classical Suslin‐Kleene characterization of the hyperarithmetical sets.

Mathematics Subject Classification: 03D70, 03D75.
A Note on Closed Degrees of Difficulty of the Medvedev Lattice
Authors: Bianchini Caterina , Sorbi Andrea
Published: May 2007

We consider some nonprincipal filters of the Medvedev lattice. We prove that the filter generated by the nonzero closed degrees of difficulty is not principal and we compare this filter, with respect to inclusion, with some other filters of the lattice. All the filters considered in this paper are disjoint from the prime ideal generated by the dense degrees of difficulty.

Mathematics Subject Classification: 03D30.
Analyse de complexité pour un théorème de Hall sur les fractions continues
Authors: Labhalla Salah , Lombardi Henri
Published: May 2007

We give a polynomial time controlled version of a theorem of M. Hall: every real number can be written as the sum of two irrational numbers whose developments into a continued fraction contain only 1, 2, 3 or 4.

Mathematics Subject Classification: 03D15, 03F60, 11A55, 68Q25.
Tense Logic Without Tense Operators
Authors: Wolter Frank
Published: May 2007

We shall describe the set of strongly meet irreducible logics in the lattice ϵLin.t of normal tense logics (in the bimodal propositional language) of weak orderings. Based on this description it is shown that all logics in ϵLin.t are independently axiomatizable. Then the description is used in order to investigate tense logics with respect to decidability, finite axiomatizability, axiomatization problems and completeness with respect to Kripke semantics. The main tool for the investigation is a translation of bimodal formulas into a language talking about partitions of general frames into intervals so that relative to both Kripke frames and descriptive frames the expressive power of both languages coincides.

Mathematics Subject Classification: 03B45, 03B25.
A Note on Boolean Algebras with Few Partitions Modulo some Filter
Authors: Huberich Markus
Published: May 2007

We show that for every uncountable regular κ and every κ‐complete Boolean algebra B of density ≤ κ there is a filter F ⊆ B such that the number of partitions of length < modulo κF is ≤2<κ. We apply this to Boolean algebras of the form P(X)/I, where I is a κ‐complete κ‐dense ideal on X.

Mathematics Subject Classification: 06E05, 03C20.
Modal Aggregation and the Theory of Paraconsistent Filters
Authors: Apostoli Peter
Published: May 2007

This paper articulates the structure of a two species of weakly aggregative necessity in a common idiom, neighbourhood semantics, using the notion of a k‐filter of propositions. A k‐filter on a non‐empty set I is a collection of subsets of I which (i) contains I, (ii) is closed under supersets on I, and (iii) contains ∪{Xi ≤ Xj : 0 ≤ i < j ≤ k} whenever it contains the subsets X0,…, Xk. The mathematical content of the proof that weakly aggregative modal logic is complete relative to k‐ary frame theory, the standard semantic idiom for weakly aggregative modal logic (see [1]) is presented in language‐independent terms as a representation theorem for k‐filters: every non‐trivial k‐filter is included in the union of ≤ k non‐trivial filters. The elementary theory of k‐filters is developed and then applied in the form of an ultrafilter extension result for k‐ary frame theory.

Mathematics Subject Classification: 03B45.
Strong Minimal Covers for Recursively Enumerable Degrees
Authors: Barry Cooper S.
Published: May 2007

We prove that there exists a nonzero recursively enumerable Turing degree possessing a strong minimal cover.

Mathematics Subject Classification: 03D30.
Modal Tree‐Sequents
Authors: Cerrato Claudio
Published: May 2007

We develop cut‐free calculi of sequents for normal modal logics by using treesequents, which are trees of sequences of formulas. We introduce modal operators corresponding to the ways we move formulas along the branches of such trees, only considering fixed distance movements. Finally, we exhibit syntactic cut‐elimination theorems for all the main normal modal logics.

Mathematics Subject Classification: 03B45, 03F05.
A Cardinal Pattern Inspired by AD
Authors: Apter Arthur W.
Published: May 2007

Assuming Con(AD), a model in which there are unboundedly many regular cardinals below Θ and in which the only regular cardinals below Θ are limit cardinals was previously constructed. Using a large cardinal hypothesis far beyond Con(AD), we construct in this paper a model in which there is a proper class of regular cardinals and in which the only regular cardinals in the universe are limit cardinals.

Mathematics Subject Classification: 03E55, 03E60.
Polymodal Lattices and Polymodal Logic
Authors: Bell John L.
Published: May 2007

A polymodal lattice is a distributive lattice carrying an n‐place operator preserving top elements and certain finite meets. After exploring some of the basic properties of such structures, we investigate their freely generated instances and apply the results to the corresponding logical systems — polymodal logics — which constitute natural generalizations of the usual systems of modal logic familiar from the literature. We conclude by formulating an extension of Kripke semantics to classical polymodal logic and proving soundness and completeness theorems.

Mathematics Subject Classification: 03G10, 06D99, 03B45.
The Maximal Closed Classes of Unary Functions in p‐Valued Logic
Authors: Renren Liu , Czukai Lo
Published: May 2007

In many‐valued logic the decision of functional completeness is a basic and important problem, and the thorough solution to this problem depends on determining all maximal closed sets in the set of many‐valued logic functions. It includes three famous problems, i.e., to determine all maximal closed sets in the set of the total, of the partial and of the unary many‐valued logic functions, respectively. The first two problems have been completely solved ([1], [2], [8]), and the solution to the third problem boils down to determining all maximal subgroups in the k‐degree symmetric group Sk, which is an open problem in the finite group theory. In this paper, all maximal closed sets in the set of unary p‐valued logic functions are determined, where p is a prime.

Mathematics Subject Classification: 03B50, 20B35.
Effectively and Noneffectively Nowhere Simple Sets
Authors: Harizanov Valentina S.
Published: May 2007

R. Shore proved that every recursively enumerable (r. e.) set can be split into two (disjoint) nowhere simple sets. Splitting theorems play an important role in recursion theory since they provide information about the lattice ϵ of all r. e. sets. Nowhere simple sets were further studied by D. Miller and J. Remmel, and we generalize some of their results. We characterize r. e. sets which can be split into two (non) effectively nowhere simple sets, and r. e. sets which can be split into two r. e. non‐nowhere simple sets. We show that every r. e. set is either the disjoint union of two effectively nowhere simple sets or two noneffectively nowhere simple sets. We characterize r. e. sets whose every nontrivial splitting is into nowhere simple sets, and r. e. sets whose every nontrivial splitting is into effectively nowhere simple sets. R. Shore proved that for every effectively nowhere simple set A, the lattice L* (A) is effectively isomorphic to ϵ*, and that there is a nowhere simple set A such that L*(A) is not effectively isomorphic to ϵ*. We prove that every nonzero r. e. Turing degree contains a noneffectively nowhere simple set A with the lattice L*(A) effectively isomorphic to ϵ*.

Mathematics Subject Classification: 03D25, 03D10.
Splittings of 0' into the Recursively Enumerable Degrees
Authors: Yi Xiaoding
Published: May 2007

Lachlan [9] proved that there exists a non‐recursive recursively enumerable (r. e.) degree such that every non‐recursive r. e. degree below it bounds a minimal pair. In this paper we first prove the dual of this fact. Second, we answer a question of Jockusch by showing that there exists a pair of incomplete r. e. degrees a0, a1 such that for every non‐recursive r. e. degree w, there is a pair of incomparable r. e. degrees b0, b2 such that w = b0 V b1 and bi for i = 0, 1.

Mathematics Subject Classification: 03D25, 03D30.
Precovers, Modalities and Universal Closure Operators in a Topos
Authors: Bell John L. , Gebellato Silvia
Published: May 2007

In this paper we develop the notion of formal precover in a topos by defining a relation between elements and sets in a local set theory. We show that such relations are equivalent to modalities and to universal closure operators. Finally we prove that these relations are well characterized by a convenient restriction to a particular set.

Mathematics Subject Classification: 03G30, 03B20, 03F55.
Decidability in Intuitionistic Type Theory is Functionally Decidable
Authors: Valentini Silvio
Published: May 2007

In this paper we show that the usual intuitionistic characterization of the decidability of the propositional function B(x) prop [x : A], i. e. to require that the predicate (∀x ∈ A) (B(x) ∨ ¬ B(x)) is provable, is equivalent, when working within the framework of Martin‐Löf's Intuitionistic Type Theory, to require that there exists a decision function ψ: A → Boole such that (∀x ∈ A) ((ψ(x) = Boole true) ↔ B(x)). Since we will also show that the proposition x = Boole true [x: Boole] is decidable, we can alternatively say that the main result of this paper is a proof that the decidability of the predicate B(x) prop [x : A] can be effectively reduced by a function ψ A → Boole to the decidability of the predicate ψ(x) = Boole true [x : A]. All the proofs are carried out within the Intuitionistic Type Theory and hence the decision function ψ, together with a proof of its correctness, is effectively constructed as a function of the proof of (∀x ∈ A)(B(x) ∨ ¬ B(x)).

Mathematics Subject Classification: 03B15, 03B20.
On the Logic of Common Belief
Authors: Bonanno Giacomo
Published: May 2007

We investigate an axiomatization of the notion of common belief (knowledge) that makes use of no rules of inference (apart from Modus Ponens and Necessitation) and highlight the property of the set of accessibility relations that characterizes each axiom.

Mathematics Subject Classification: 03B45, 68T25.
The Computation of Partial Recursive Word‐Functions Without Read Instructions
Authors: Petersen Holger
Published: May 2007

In this note we consider register‐machines with symbol manipulation capabilities. They can form words over a given alphabet in their registers by appending symbols to the strings already stored. These machines are similar to Post's normal systems and the related machine‐models discussed in the literature. But unlike the latter devices they are deterministic and are not allowed to read symbols from the front of the registers. Instead they can compare registers and erase them. At first glance it is surprising that in general these devices are as powerful as the seemingly stronger models. Here we investigate the borderline of universality for these machines.

Mathematics Subject Classification: 03D20, 68Q05, 68Q10.
The Axiom of Choice in Quantum Theory
Authors: Brunner Norbert , Svozil Karl , Baaz Matthias
Published: May 2007

We construct peculiar Hilbert spaces from counterexamples to the axiom of choice. We identify the intrinsically effective Hamiltonians with those observables of quantum theory which may coexist with such spaces. Here a self adjoint operator is intrinsically effective if and only if the Schrödinger equation of its generated semigroup is soluble by means of eigenfunction series expansions.

Mathematics Subject Classification: 03E35, 81P10, 03E25, 35Q40, 46B26, 47A60.
Expanding the phenotype of fragile X‐associated tremor/ataxia syndrome: A new female case
Authors: Horvath Judit , Morris Michael , Bottani Armand , Moix Isabelle , Delavelle Jacqueline , Burkhard Pierre R.
Published: May 2007

We report an original case of fragile X‐associated tremor/ataxia syndrome in a female carrier, who had been misdiagnosed for years because of unusual features mimicking other movement or cerebrovascular disorders. She exhibited features that have not been previously described, including voice and head tremor as well as spasmodic laryngeal dystonia. Brain MRI showed widespread leukoencephalopathy reminiscent of vascular encephalopathy, exemplifying the diversity of MRI abnormalities that could be associated with the condition. © 2007 Movement Disorder Society
Skin cancers and precancerous lesions in Parkinson's disease patients
Authors: Ferreira Joaquim , Silva João Maia , Freire Rita , Pignatelli João , Guedes Leonor Correia , Feijó Alexandra , Rosa Mário Miguel , Coelho Miguel , Costa João , Noronha Ana , Hewett Russell , Gomes A. Marques , de Castro J.L. Cirne , Rascol Olivier , Sampaio Cristina
Published: May 2007

Our objective was to evaluate the frequency of neoplastic and preneoplastic skin lesions in Parkinson's disease (PD) patients when compared with an aged‐matched population. We performed a cross‐sectional survey in PD patients and in an age‐matched control group. Patients and controls were examined by a movement disorder specialist and a dermatologist. 150 PD patients and 146 controls were included. Thirty‐five PD patients (23.3%) presented skin lesions that could be classified as neoplastic or preneoplastic vs. 20 subjects in the control group (13.7%) (OR 95%, CI 1.92 [1.05, 3.51]). However, this difference lost statistical significance when adjusted for gender (recruitment of controls was matched just for age with an over representation of males in the PD group). Twenty‐nine PD patients (19%) presented actinic keratosis and basal cell carcinoma was diagnosed in 4 patients (3%). Although nonconclusive, our results are in agreement with previous studies suggesting an increased risk of skin cancer in PD patients. The frequency of actinic keratosis in PD patients and the associated risk to develop melanoma recommends its screening in future epidemiological studies. © 2007 Movement Disorder Society
Impaired cardiovascular autonomic function in Parkinson's disease with visual hallucinations
Authors: Oka Hisayoshi , Yoshioka Masayuki , Onouchi Kenji , Morita Masayo , Mochio Soichiro , Suzuki Masahiko , Hirai Toshiaki , Urashima Mitsuyoshi , Inoue Kiyoharu
Published: May 2007

We assessed the relations of visual hallucinations (VH) to cardiovascular autonomic dysfunction in patients with Parkinson's disease (PD). The subjects were 37 patients without VH (VH(−)) and 31 with VH (VH(+)). Autonomic function was evaluated on the basis of cardiac 123‐radioiodinated metaiodobenzylguanidine (123I‐MIBG) uptake and hemodynamic testing with Valsalva maneuver. Systolic blood pressure (SBP) and plasma norepinephrine concentrations (NE) were measured by tilt‐table testing. 123I‐MIBG uptake was lower in VH(+) than VH(−). Hemodynamic studies showed that VH(−) had only cardiac sympathetic and parasympathetic dysfunction, while VH(+) additionally had reduced vasomotor sympathetic functions. The fall in SBP during tilt‐table testing was greater in VH(+) than VH(−). NE and its difference in the supine and upright positions were decreased in VH(+). We conclude that cardiac and vasomotor sympathetic dysfunction is more severe in VH(+) than in VH(−). Severe dysfunction in PD with VH is probably attributed to Lewy‐body lesions or neuronal loss in sympathetic ganglia, the central autonomic system, or both. © 2007 Movement Disorder Society
A stable energy‐conserving approach for frictional contact problems based on quadrature formulas
Authors: Hager C. , Hüeber S. , Wohlmuth B. I.
Published: May 2007

A common approach for the numerical simulation of non‐linear multi‐body contact problems is the use of Lagrange multipliers to model the contact conditions. The stability of standard algorithms is improved by introducing a modified mass matrix which assigns no mass to the potential contact nodes. By this, the spurious algorithmic oscillations in the multiplier do not occur any more, which facilitates the application of the primal–dual active set strategy to dynamical contact problems. The new mass matrix is calculated via a modified quadrature formula that needs no extra computational cost. In addition the conservation properties of the underlying algorithm are transferred to the modified mass version. Different numerical examples for frictional two‐body contact problems illustrate the improvement in the results for the contact stresses. Copyright © 2007 John Wiley & Sons, Ltd.
Dynamic selective pressure using hybrid evolutionary and ant system strategies for structural optimization
Authors: Kaveh A. , Shahrouzi M.
Published: May 2007

Genetic algorithms have already been applied to various fields of engineering problems as a general optimization tool in charge of expensive sampling of the coded design space. In order to reduce such a computational cost in practice, application of evolutionary strategies is growing rapidly in the adaptive use of problem‐specific information. This paper proposes a hybrid strategy to utilize a cooperative dynamic memory of more competitive solutions combining indirect information share in ant systems with direct constructive genetic search. Some proper coding techniques are employed to enable testing the method with various sets of control parameters. As a challenging field of interest, its application to structural layout optimization is considered while an example of a traveling salesman problem is also treated as a combinatorial benchmark. Copyright © 2007 John Wiley & Sons, Ltd.
Current approaches for risk stratification of infectious complications in pediatric oncology
Authors: Härtel Christoph , Deuster Maresa , Lehrnbecher Thomas , Schultz Christian
Published: May 2007

Infections are serious complications of cytoreductive therapy in pediatric cancer patients presenting with febrile neutropenia. It is standard of care to initiate empirical intravenous broad‐spectrum antibiotics until the fever and neutropenia resolve. However, it might be effective and safe to allow for early hospital discharge in certain subgroups of patients. Two strategies for risk stratification of pediatric cancer patients with regard to infectious complications are discussed in this review: (1) clinical risk parameters and laboratory measures to assist therapeutic management at presentation with fever in neutropenia, and (2) investigations of individual genetic susceptibility factors to tailor potential prophylactic approaches. Given the data available from a significant number of small studies, a large prospective non‐inferiority trial is essential to assess low‐risk clinical factors and additional laboratory or genetic markers for their predictive value. Pediatr Blood Cancer 2007;49:767–773. © 2007 Wiley‐Liss, Inc.
Correlation between asparaginase sensitivity and asparagine synthetase protein content, but not mRNA, in acute lymphoblastic leukemia cell lines
Authors: Su Nan , Pan Yuan‐Xiang , Zhou Mi , Harvey Richard C. , Hunger Stephen P. , Kilberg Michael S.
Published: May 2007

Background

Asparaginase (ASNase) is an essential component of most treatment protocols for childhood acute lymphoblastic leukemia (ALL). Although increased asparagine synthetase (ASNS) expression may contribute to ASNase resistance, there is conflicting data from patient samples with regard to correlation between ASNS mRNA content and ASNase sensitivity.

Procedure

Both T‐cell and B‐cell derived ALL cell lines were treated with ASNase and then monitored for cell proliferation, cell death, and ASNS mRNA and protein expression.

Results

Despite elevated ASNS mRNA following ASNase treatment, different ALL cell lines varied widely in translation to ASNS protein. Although ASNS mRNA levels did not consistently reflect ASNase sensitivity, there was an inverse correlation between ASNS protein and ASNase‐induced cell death. Expression of ASNS in an ASNase‐sensitive cell line resulted in enhanced ASNase resistance, and conversely, siRNA‐mediated inhibition of ASNS expression promoted increased drug sensitivity.

Conclusions

These observations provide an explanation for the ASNase sensitivity of ALL cells and demonstrate the importance of measuring ASNS protein rather than mRNA in predicting ASNase responsiveness. Pediatr Blood Cancer 2008;50:274–279. © 2007 Wiley‐Liss, Inc.
A novel mutation in the NF1 gene in two siblings with neurofibromatosis type 1 and bilateral optic pathway glioma
Authors: Kebudi Rejin , Tuncer Samuray , Upadhyaya Meena , Peksayar Gonul , Spurlock Gill , Yazici Hulya
Published: May 2007

We present the clinical and ophthalmological findings, genetic analysis, and therapy of two siblings with NF1 and bilateral OPG. In genetic analysis, a heteroduplex profile was detected in exon 4b of the NF1 gene for the affected patients and mother. Sequencing of the DNA samples identified a C > T nucleotide change in exon 4b (c484CAG > TAG). This nonsense mutation resulted in a change of glutamine to a stop codon (Q162X) and is a novel NF1 gene alteration. Pediatr Blood Cancer 2008;50:713–715. © 2007 Wiley‐Liss, Inc.
Prenatal demonstration of afferent vessels and progressive thrombosis in a torcular malformation
Authors: Grangé G. , LeTohic A. , Merzoug V. , Adamsbaum C.
Published: May 2007

Objectives

To elucidate a part of the prenatal natural history of dural sinus malformation of the posterior fossa.

Methods

Ultrasound and magnetic resonance imaging were performed from 31 to 32 weeks' gestation.

Results

We observed the progressive development of a thrombus that was visible as an expanding hyperechoic round area within a cystic mass of the posterior fossa. It was characterized, as expected for a vascular malformation, by the presence of blood flow into the aneurismal cavity. Color doppler identified superior sagittal and straight sinuses, and distinguished that their flow continued into the dilated torcular. Prenatal magnetic resonance imaging confirmed an arteriovenous malformation involving the dural sinus.

Conclusion

The vascular malformation had a fixed volume and preceded the thrombosis, which formed within several days. The present case is the first report with all the prenatal sonographic features of this condition. Copyright © 2007 John Wiley & Sons, Ltd.
Array‐CGH analysis of cell‐free fetal DNA in 10 mL of amniotic fluid supernatant
Authors: Lapaire Olav , Lu Xin‐Yan , Johnson Kirby L. , Jarrah Zina , Stroh Helene , Cowan Janet M. , Tantravahi Umadevi , Bianchi Diana W.
Published: May 2007

Background

Previously, we showed that analysis of amniotic fluid (AF) supernatant cell‐free fetal (cff) DNA using DNA microarrays (array‐CGH) allows for detection of whole chromosome differences between test and reference DNA. Subsequent technical advances have increased both the yield and quality of extracted cffDNA. Here we determined whether array‐CGH using smaller volumes of both fresh and frozen AF cffDNA could identify fetal aneuploidy.

Methods

CffDNA was extracted from 10 mL of residual AF supernatant. The test AF samples (n = 10) included one with a normal karyotype, and nine with the following fetal aneuploidies: trisomies 13 (n = 1), 18 (n = 3), 21 (n = 2), trisomy 9 mosaicism (47,XX,+ 9[18]/46,XX[2]), triploidy (69,XXY) and Turner syndrome (45,X).

Results

Array‐CGH using AF cffDNA from aneuploid fetuses, compared to euploid reference AF cffDNA, detected whole chromosome aneuploidy in 8 of 9 cases tested, including the case of trisomy 9 mosaicism. The case of triploidy was not detected.

Conclusions

CffDNA extracted from 10 mL AF supernatant can be analyzed using array‐CGH to correctly identify human chromosome abnormalities. This technology allows for rapid screening of AF samples for whole chromosomal changes by using routinely discarded supernatant, and may augment standard prenatal karyotyping techniques by providing additional molecular information. Copyright © 2007 John Wiley & Sons, Ltd.
Parallel tempering molecular dynamics folding simulation of a signal peptide in explicit water
Authors: Höfinger Siegfried , Almeida Benjamin , Hansmann Ulrich H. E.
Published: May 2007

Parallel temperature molecular dynamics simulations are used to explore the folding of a signal peptide, a short but functionally independent domain at the N‐terminus of proteins. The peptide has been analyzed previously by NMR, and thus a solid reference state is provided with the experimental structure. Particular attention is paid to the role of water considered in full atomic detail. Different partial aspects in the folding process are quantified. The major group of obtained structures matches the NMR structure very closely. An important biological consequence is that in vivo folding of signal peptides seems to be possible within aqueous environments. Proteins 2007. © 2007 Wiley‐Liss, Inc.